3
$\begingroup$

Given 18 cards with numbers 1 .. 9 on them (two cards with each digit), arrange them sequentially so that the distance between the identically marked cards is equal to the number written on the card.

E.g., the $\boxed 1$ cards should be next to each other and there should be exactly one card between the $\boxed 2$ cards.

PS. I did come up with an answer, but I would like to know if there is some interesting math behind this.

$\endgroup$
1
$\begingroup$

Here is a simple proof that any solution with $n$ pairs of cards must have $n$ equal to $0$ or $1$ modulo $4$.

Suppose you have a solution with $n$ pairs of cards laid out in a row. Colour the cards alternating black and white, like a chess board. Since there row has an even length, there will be the same number of white as black cards.

Any card pair with an odd number on them will be opposite colours, so uses up the same number of black as white.
Any card pair with an even number on them will be the same colour. All together these even cards must also use up the same amount of each colour, so we need half of the pairs to be one colour and the other half to be the other colour. We therefore need an even number of pairs that have even numbers on them.

This restricts $n$ to being either a multiple of $4$, or one more than that.

These sequences have been studied. They are called Skolem Sequences. A better known term is Langford Pairing, but those are slightly different as they leave out the pair that is adjacent. Of course you can create a Skolem Sequence from a Langford Pairing by adding the adjacent pair at either end. There are Skolem Sequences where the adjacent pair is not at one end.

$\endgroup$
2
$\begingroup$

Here is Python code to get all solutions:

from itertools import permutations
from math import factorial

def pool2arrangement(pool):
    answer = 2*size*[None]
    pos = 0                     # 1st unfilled position
    for n in pool:
        while answer[pos]:
            pos += 1
        # print(pos,n)
        if pos + n >= 2*size or answer[pos+n]:
            return None
        answer[pos] = answer[pos+n] = n
    return answer

for size in range(12):
    answers = [a for a in map(pool2arrangement,permutations(range(1,size+1))) if a]
    print(size,": found",len(answers),"answers out of",factorial(size))

Findings:

there are many solutions when size is 0 or 1 $\mod 4$, e.g., 6 for size 4, 2,656 for size 9 (the original problem as stated) and 455,936 for size 12, and none otherwise.

E.g.:

[1, 1, 3, 4, 2, 3, 2, 4]
[8, 9, 5, 6, 2, 7, 2, 5, 8, 6, 9, 3, 7, 4, 3, 1, 1, 4]
[1, 1, 2, 6, 2, 9, 4, 12, 10, 6, 4, 5, 11, 8, 9, 7, 5, 3, 10, 12, 3, 8, 7, 11]

$\endgroup$

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.