6
$\begingroup$

Given a Double Twelves Domino Set, prove that the dominos can be arranged in a valid formation such that placement follows the domino placement rules, namely:

  • A domino can be placed with the short end touching the short end of another domino, provided that the short end of both dominos match in number of pips.
  • A domino with the same number of pips both ends can be placed horizontally perpendicular to another domino, simply for conservation of space, and placing the domino this way does not permit any additional connections.
  • A domino can be rotated 90 degrees in either direction to change the direction of the train of dominoes, only for conservation of space.

An image of a Double Twelves Domino Set: it includes, 91 tiles and 1092 pips.

doubletwelves

I will accept the best answer, but for extra consideration, provide proof that this works for dominoes going up to size N, or also provide an image of the solution, additional extra consideration will be awarded if the final solution is arranged in a creative, organized shape.

Please use spoilers to hide mathematical proofs, or key answers. Good luck!

$\endgroup$
8
$\begingroup$

The generalization of this problem is already known: https://en.wikipedia.org/wiki/De_Bruijn_sequence. A De Bruijn sequence given an alphabet and a word-length is a string containing, as substrings, all words of that word length with letters from that alphabet exactly once.

We can apply the existing knowledge on De Bruijn sequences (which can be found on the wikipedia page) to this problem. If we set our alphabet to {0, ..., 12} and our word-length to 2, a De Bruijn sequence is exactly a solution to this problem (a word is a domino). There are $\frac{(13!)^{13^1}}{13^2} = 1.25\times10^{125}$ possible solutions for a Double Twelves Domino Set.

There are also algorithms on the wikipedia page that calculate example De Bruijn sequences given alphabet-size and word-length.

EDIT: Note that De Bruijn sequences are cyclic. This is fine however, we can just tack the beginning character onto the end (or beginning $n-1$ characters in the case of word-length $n$).

$\endgroup$
  • $\begingroup$ Excellent, very good. One small flaw is that the alphabet would need to contain entries for zero as well, since portions of the dominoes can have no pips. $\endgroup$ – Sam Weaver Oct 5 '15 at 23:33
  • $\begingroup$ @SamWeaver, Oh, correct. I'll edit. $\endgroup$ – Ben Frankel Oct 5 '15 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.