### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,115)
- misc (2)
- project euler (2)
- puzzle (29)
- site news (43)
- tantalizer (29)
- teaser (3)

### Site Stats

- 166,357 hits

Programming Enigma Puzzles

18 September 2012

Posted by on **From New Scientist #2678, 18th October 2008**

I have a little trick with eight cards. Their backs are all white but the fronts are one each of apricot, blue, chocolate, green, orange, primrose, red and terracotta. I place them in a pile in a certain order, white sides up. Then I spell out one of the colours, moving one card from the top of the pile to the bottom as I say each letter. As I reach the last letter of the spelling I turn over that card and (lo and behold) it is that colour. I then place that card at the bottom of the pile and spell out another colour. In this way I work through all the colours, finishing with the apricot. In the course of the trick the chocolate card is turned over later than the terracotta one.

List (by their initials) the order in which I spell out the colours.

[enigma1516]

Advertisements

%d bloggers like this:

The following Python program runs in 740ms (under PyPy).

Solution:The order is P O G B T C R A.Here’s another way of looking at it: start with the spelling out order and see if it matches a feasible initial order

The puzzle (without the specific constraints on the card order) is equivalent to question 1002 posed in Mathematics Magazine, Vol. 49, No. 5 (Nov 1976), p. 253, Mathematical Association of America, http://www.jstor.org/stable/2689460, which asked:

1002. a. For which values of n is it possible to find a permutation of [0, 1,. .., n-1] so that the partial sums, when reduced modulo n, are also a permutation of [0, 1,. .., n-1]? [Bernardo Recamán, University of Warwick.]

b.* Find the number of permutations of [0, 1,. .., n – 1] for n ≤ 12 which solve part a. Can a general formula for the number of solutions be found? [John Hoyt, Indiana University of Pennsylvania.]

The answer to part a. was given in Mathematics Magazine, Vol. 51, No. 4 (Sep 1978), p. 247, http://www.jstor.org/stable/2689475. the answer being that even values of n can have such a permutation. The editor notes that part b. was not answered, but that there are 24 permutations for n=8, found with the aid of a computer.

The answer given does not help in identifying the possible permutations, but all such permutations must have 0 as the first element (i.e. 0 is permuted to itself). Using this together with the constraints of the puzzle, we can rewrite the code as:

A good bit of research, Arthur.

In my original Perl program to solve this I noted that the lengths of the colours where 0-7 (modulo 8), and I treated the pile as a circular buffer with a pointer, rather than re-arranging the pile itself. Although I do remember writing out the initials of the colours on pieces of paper to satisfy myself that the solution was indeed correct.

In my Python program above I somewhat mechanically manipulate the pile in the way described in the puzzle to attempt to give code that is more obviously solving the puzzle.

A more efficient way though is to solve the puzzle backwards, and reconstruct the initial pile starting from the last card turned over (which we are helpfully told is “Apricot”, and we know how many cards must have been moved before we got to it).

The following recursive algorithm runs in 32ms.

The script below in Matlab was used to find the solution (then submitted) to the puzzle when it was originally posed.