Impossible Sandwiches

In September 1997 we published the following puzzle called Sandwiches. Paul Cockayne's delightful, simple and completely general proof about when solutions exist and when they do not exist has just been contributed by Alan Parr from his games magazine 'Hopscotch'.

If you have not tried this puzzle before you may like to have a go at it before reading Paul's solution below or referring to the other solutions in the NRICH Archive.

Here is the puzzle:

Suppose you have two 1s, two 2s and two 3s. Arrange these six digits in a list so that:

• between the two 1s there is one digit giving 1?1,
• between the two 2s there are two digits giving 2??2,
• and between the two 3s there are three digits giving 3???3.

Can you do the same if you only have 1s and 2s? Explain your answer.

Can you do the same if you include two fours, and between the two 4s there are four digits?

Here is a solution using 5s, 6s and 7s as well: 71316435724625. Find other solutions with all these digits.

Here is Paul Cockayne's stunningly simple proof that solutions only exist for n=4m or n=4m-1..... To make the terminology a bit simpler, colour digits in the "solution number" or "sandwich", alternately red and blue:.

Then all odd numbers in the solution number will be either both red or both blue. Even numbers will always be one red, one blue. Since the final solution contains an equal number of red and blue digits, the problem is only soluble if we have an even number of odd numbers.

The only n-sandwiches which have an even number of odd numbers are those where n is a multiple of 4 or 1 less than a multiple of 4. (For example 9-sandwiches don't exist because if they did they would contain 1s, 3s, 5s, 7s and 9s)

Obvious, isn't it?

Finally, just to prove that he had done it, Adam Huby gave the following solution for n = 67.

67 65 66 62 60 64 57 63 54 52 61 49 47 59 44 58 41 39 56 36 55 33 30 53 26 24 51 20 50 5 9 48 10 12 46 5 45 7 3 43 9 42 3 10 40 7 12 38 20 37 24 26 35 30 34 33 36 39 41 44 47 49 52 54 57 60 62 65 67 66 64 63 61 59 58 56 55 53 51 50 48 46 45 43 42 40 38 37 35 34 32 29 31 28 25 23 21 27 18 6 13 11 8 22 4 2 6 19 2 4 17 8 16 11 13 14 15 18 21 23 25 29 28 32 31 27 22 19 17 16 14 1 15 1