[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

2017.0. "Domino squares" by CHEFS::STRANGEWAYS (Andy Strangeways@REO DTN 830-3216) Mon Dec 04 1995 09:14

    Take a normal set of 28 dominos. Choosing four appropriate dominos (say
    1:2, 2:3, 3:4 and 4:1) to make a square with numbers matching in the
    normal way:
    
    1:2|2
    -   3
    1   -
    4|4:1
    
    In fact, you can make seven squares of four out of the 28 dominos. How
    many different ways can you do this?
    
    (I'm particularly interested to see if anyone can come up with an
    elegant or "aha" type solution. I've worked out the answer by a very
    problem-specific enumeration of cases, but I feel the obvious
    symmetries in the problem should lead to a neat answer. For instance,
    if anyone knows a neat way to count the number of ways the 28 edges of
    the graph K7 can be partitioned into 7 edge-disjoint triangles, that
    would lead to an answer)
    
    Andy.
T.RTitleUserPersonal
Name
DateLines
2017.2mistake Mr. Strangeways ????HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Mon Dec 04 1995 13:4720
You wrote

 
   Take a normal set of 28 dominos. Choosing four appropriate dominos (say
    1:2, 2:3, 3:4 and 4:1) to make a square with numbers matching in the
    normal way:
    
    1:2|2
    -   3
    1   -
    4|4:1
 


I don't understand your "4:1", since the "3" above the "1" I assume is supposed to
be a matching digit.


/Eric
2017.3Total failure to communicateCHEFS::STRANGEWAYSAndy Strangeways@REO DTN 830-3216Mon Dec 04 1995 14:0117
    Re .2:
    
    The "|" and "-" symbols represent boundaries between dominos. I have
    used the symbol ":" to mark the separation between the two halves of a
    single domino so as to avoid writing (for instance) 12 which might look
    like "twelve" rather than "one and two".
    
    Re .1:
    
    Sorry, I seem to have been unclear (or I've failed to undertand your
    answer). I'll restate the problem:
    
    How many ways can you spilt a standard set of 28 dominos into exactly
    7 groups of 4 dominos such that each group can be arranged into a
    square with matching numbers at each join?
    
    Andy.
2017.4errataCHEFS::STRANGEWAYSAndy Strangeways@REO DTN 830-3216Mon Dec 04 1995 14:4619
    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.
2017.5OK, I get it...FLOYD::YODERMFYMon Dec 04 1995 14:507
I see I misinterpreted, so I deleted .1.

It can be shown that each of the 7 groups of 4 must contain exactly one double
domino (of the form a:a), since each square must have either 0 or 1 such domino,
and there are 7 in all.  This in turn means that the splitting is determined by
the function with domain 0..6 which maps a into the domino that occurs opposite
the a:a domino in its square of 4.
2017.6YupCHEFS::STRANGEWAYSAndy Strangeways@REO DTN 830-3216Mon Dec 04 1995 15:149
    Re .5:
    
    Exactly.
    
    And the range of that function, the 21 dominos with different numbers
    on the two halves, corresponds in a natural way to the edges of a
    suitably labelled copy of K7.
    
    Andy.
2017.7Aha indeedFLOYD::YODERMFYMon Dec 04 1995 17:5924
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.)
2017.8More along the lines of .7FLOYD::YODERMFYMon Dec 04 1995 19:5742
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.
2017.9typo in .8DECADA::YODERMFYTue Dec 05 1995 12:291
"123 is meant to be an equilateral triangle" should be "012 is meant to be...".
2017.10ThanksCHEFS::STRANGEWAYSAndy Strangeways@REO DTN 830-3216Tue Dec 05 1995 12:4456
    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.