Dominoes in a line
Starting with a bag containing a set of dominoes, is it possible to arrange them in a line?
More details: A domino is a 1x2 rectangular tile with each square "end" labeled with a non-negative integer. A "double-D" set of dominoes contains (D+1)(D+2)/2 dominoes, exactly one with each possible unordered pair of labels in the range 0 to D; the common "double-six" set of 28 dominoes is shown here.)
Is it possible to arrange the dominoes in a single line, end to end, so that the labels match on the adjacent ends of consecutive dominoes? For what "double-D" sets can this be done? (For example, common values of D for actual domino sets are 6, 9, 12, and 15.)
Posted Nov 17, 2022, 3:01 PM UTC · edited
76
I'm shocked this didn't get more upvotes -- I thought it was a great problem with a nice little connection to >!graph theory!<.
Thanks! I admit I agree, particularly since IMO the current posted solution is arguably oversimplified/incomplete. That is, consider counting the number of ways to do this. Then we need more than just the (hard problem of counting the) number of >!Eulerian trails in the complete graph!<, which the solution would suggest.
I personally think terranop solution is correct, even for the counting case, but I could be wrong. I originally solved it via induction without realizing the connection terranop mentioned, and then later realized the connection which was a nice aha moment.
I'm thinking of handling the >!doubles; that is, the trail isn't through K_(D+1), it's through the complete graph with loops added at each vertex. This doesn't affect parity of degrees, thus doesn't affect the correctness of the existence result, but makes the counting problem slightly more interesting.!<
Ah, yes, that makes sense.