| re .2 again:
Sorry, Eric, you're absolutely right. As Dan has just pointed out to
me, 3 does not match 1. The diagram should of course read:
1:2|2
- 3
1 -
4|4:3
And also, K7 has 21 edges, not 28 - which is what I though I had
written!
I guess everyone's blind to their own typos some of the time, but I
seem more prone to it than most.
Apologies to anyone who was confused.
Andy.
|
| Ignore the doubles for the moment, and consider the triangles. Let me instead
call them "lines", and note that two lines can intersect in at most one "point"
(using "point" for 0..6).
If there are 2 parallel lines A and B, then every other line can have at most
one point from A and from B, and so must contain the single leftover point (call
it X). But then there are 5 such lines, each of which contain a point from A,
so some two must have two points in common (X and a point from A). This is a
contradiction, so we have that every two lines intersect in *exactly* one point.
So... the lines form a projective plane on 7 points; all such planes are
isomorphic.
The number of ways to arrange this is 7! divided by the order of the symmetry
group of such a plane; the symmetry group is doubly transitive, and the
stabilizer of 2 points x,y fixes also the (unique) 3rd point which is collinear
with x and y and is exactly transitive on the remaining 4 points. So its order
is 7*6*4, and the number of distinct arrangements for the plane is 7!/(7*6*4) =
30.
Thus the answer is 30N, where N is the number of ways to choose one point from
each line in the 7-plane in such a way that you never choose the same point
twice. (N is the number of ways to assign which domino is a double, having
figured out what the "triangles" or "lines" are.)
|
| I believe the number N is 3*4*2=24, making the answer 720.
First let's show N isn't 0. Consider this arrangement, where 123 is meant to be
an equilateral triangle, with 345 its midpoints and 6 its center:
0
3 4
6
1 5 2
The lines of the projective plane are the 3 sides and 3 bisectors, plus 345
(which will look like a circle when drawn).
Take 0 from 031
1 from 152
2 from 042
3 from 362
4 from 164
5 from 345
6 from 065
and you have a solution.
To count solutions, take any line; there are 3 symmetric choices for its point.
Call the line L and the point p; let the other two points of L be xy. The two
lines associated with x and y intersect in some point q not on L, and there are
4 equivalent ways of choosing q; the line associated with q isn't qx or qy, so
it must be qp.
Let u be the third point of qx, v the third point of qy, w the third point of
pq. Since these 3 distinct lines intersect in q, the points p,x,y,u,v,w,q are
all distinct and so exhaust the plane.
Now the third line through p must be puv, and there are two choices (u or v) for
the point associated with it. These are equivalent because there is still a
symmetry swapping x and y but fixing p and q (it swaps xy and uv but fixes the 3
points pwq). So we get another factor of 2 and may assume u is chosen; and the
choice for v now cannot be either puv or uvq, so it is determined, and having
determined the choices for 6 points the choice for the last one must also be
determined.
So N=3*4*2=24.
|
| Great! That may not have been any shorter than my "direct" counting, but
it's a lot more satisfying. It also agrees with my own answer, which
the original poser of the question didn't. :)
Here's my original answer:
Paul,
Good problem - the dominos, remember?
The reason I've taken so long in replying is that I've been looking for the
"aha", or at least an elegant answer. I'm sure there must be one, but I'm
ashamed to say I've been reduced to doing it "by hand".
I get the answer as 720, which is 6!, and I'm sure that's no coincidence, but
my proof is not excatly enlightening as to why.
Anyway, here's my logic:
Clearly each square has to contain exactly one double. The rest of the square
is completely determined by the domino opposite the double. We can therefore
use the notation a;bc to denote the square aa|ab|bc|ca.
Looking at the square with double blank, we can use any of the 6*5/2 = 15
blank-free non-doubles to complete it, giving a square 0;ab. Consider the
square a;xy. Neither x nor y can be blank or a or b, so we have 4*3/2 = 6 ways
of filling this square, giving a square a;cd.
Denote two as yet unmentioned numbers e and f. The square b;?? must be filled
by cd, ce, cf, de, df or ef. But cd has already been used, and ef won't work:
0;ab and a;cd => ea touches af => e;af or f;ae, both of which use ef which is
not available.
Therefore, we must have b;ce, b;cf, b;de or b:df. These posibilities are all
equivalent under relabeling of the undiferentiated pairs c,d and e,f, so the
grand total is 15*6*4 times the number of ways of completing the puzzle from
one of these positions, say 0;ab, a;cd, b;ce.
Now,
a;cd, b;ce => c;0f
0;ab, c;0f => Either (p) d;0e or (q) e;0d
0;ab, a;cd => Either (r) e;af or (s) f:ae
But (q) and (r) are obviously incompatible, and (p) and (s) together would
leave double-e unconnected, so we have just two choices:
(p) and (r) => 0;ab, a;cd, b;ce, c;0f, d;0e, e;af and f;bd
(q) and (s) => 0;ab, a;cd, b;ce, c;0f, d;bf, e;0d and f;ae
These are both seen to be valid solutions, so the total is 15*6*4*2 = 720.
Now tell me how it ought to be done!
Andy.
|