### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 178,002 hits

Advertisements

Programming Enigma Puzzles

10 November 2013

Posted by on **From New Scientist #2534, 14th January 2006**

Using a standard set of dominoes, I laid out a row end-to-end such that (in typical domino style) touching ends were the same (e.g. 6-3, 3-5, 5-5, 5-1 etc). I started with 0-0 and then added dominoes so that the total number of pips in the row equalled 1, then 4, then 9, working my way though each perfect square and continuing as far as possible. My row could not have been shorter at any stage.

Having reached the highest square possible I was left with five dominoes, four of which were doubles.

What were those five dominoes?

[enigma1374]

Advertisements

%d bloggers like this:

I adapted my solution to Enigma 1450 (which is a similar problem, but with triangular numbers instead of square numbers) to give a constructive solution. This is a Python 3 program that runs in 66ms.

Solution:The five remaining dominoes are: 0-2, 1-1, 2-2, 3-3, 5-5.There are two chains that achieve the maximum possible square with five dominoes remaining, of which four are doubles. These are:

0-0, 0-1, 1-2, 2-3, 3-4, 4-5, 5-6, 6-1, 1-5, 5-2, 2-6, 6-3, 3-5, 5-0, 0-4, 4-6, 6-6, 6-0, 0-3, 3-1, 1-4, 4-4, 4-2 (unused: 0-2, 1-1, 2-2, 3-3, 5-5).

0-0, 0-1, 1-2, 2-3, 3-4, 4-5, 5-6, 6-3, 3-1, 1-4, 4-6, 6-0, 0-5, 5-1, 1-6, 6-6, 6-2, 2-0, 0-3, 3-5, 5-5, 5-2, 2-4 (unused: 0-4, 1-1, 2-2, 3-3, 4-4).

But the puzzle requires that the chain “could not have been shorter at any stage”. To do this I examine the indices at the chain at which square totals are achieved and choose the smallest tuple. For the two cases above the indices are:

(0, 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22)

(0, 1, 2, 3, 4, 5, 6, 8, 10, 13, 15, 19, 22)

and so the first chain is the answer to the puzzle, as each index is ≤ the corresponding index in the other solution(s).

But it’s not guaranteed that there would be a solution. If the second sequence went …, 10, 13, 14, 19, … then each sequence would be the shortest at different indices so there would be no overall solution that is the shortest at every stage. However given that there is a solution, it will be the smallest when they are lexicographically ordered.