October 2000
<<September October November>>
Part A: Select a set S of 24 distinct integers between 0 and N-1, satisfying the following property:
Think of the permutation that would take the five cards in ascending order (such as (3,7,12,14,111)) and permute them to the order that is passed (such as (7,3,111,14,12)). There are 120=5! such possible permutations, and we can assign to each permutation an integer k between 1 and 120.
The blue card has a different number than any of the five white cards. So we make the convention that if the permutation corresponds to one of the white cards, we replace that permutation number with one of the integers from 121 to 125; 121 corresponding to the smallest passed card, and so on. So if the cards passed were (3,7,12,14,111) and the blue card was 121, the Host would arrange a permutation corresponding to the smallest of the five cards (3), and the Partner would recognize this and substitute 121 for 3.
Part B:
Our solution to Part B does not make use of the fact that the blue card has a different number than the others; it turned out to be harder to use that information here.
Let N=190 be the size of the range.
For ease of exposition I will say that the allowable integers range from 0 to N-1 instead of from 1 to N.
For each offset integer i,
let (S+i) denote the set of integers obtained by adding i to each element of S and reducing mod N.
Our property is that S and (S+i) overlap in at most 5 elements (except in the trivial case where i is divisible by N).
An example of such a set S is
S={7, 9, 17, 24, 26, 27, 29, 30, 34, 65, 76, 83, 106, 122, 130, 141,
142, 146, 150, 166, 168, 169, 182, 184}.
In this example, with the offset i=2 we see that S and (S+2) share the five elements {9, 26, 29, 168, 184}; no other offset gives a larger intersection, though some other offsets also give intersections of size 5.
It is easy to see that for any two offsets i and j which are not equivalent mod N, (S+i) and (S+j) also have at most five elements in their intersection.
Suppose first that four cards are passed, with values {x1, x2, x3, x4}.
As before, let their permutation (with respect to ascending order) determine an integer k between 1 and 24. Let S(k) denote the kth element of our set S. Then the Partner will predict the integer (S(k) + x1 + x2 + x3 + x4 mod N).
Notice that with the four cards {x1, x2, x3, x4}, if i=x1+x2+x3+x4, by various permutations of these four cards we can signal any element of the set (S+i).
If instead five cards are passed, we do the following.
Think of the five passed cards {x1,x2,x3,x4,x5} in ascending order.
Define T1=(S+(x2+x3+x4+x5)) to be the set of 24 integers that could have been signalled with the four cards {x2,x3,x4,x5} (i.e. all but x1).
Define T2=(S+(x1+x3+x4+x5)) to be the set of 24 integers that could have been signalled with the four cards {x1,x3,x4,x5} (i.e. all but x2).
Similarly T3, T4, T5.
Since both Host and Partner see the five passed cards, they can both compute T1, T2, T3, T4, T5, and agree on their values.
The offsets are all different mod N; for example, the offsets (x2+x3+x4+x5) and (x1+x3+x4+x5) differ by (x2-x1), which is nonzero mod N.
So T2 shares at most five elements with T1, implying that T2 has at least 19 elements that are not in T1.
T3 shares at most five elements with T1 and at most five elements with T2, so that T3 has at least 14 elements not contained in either T1 or T2.
So the union (T = T1 union T2 union T3 union T4 union T5) has at least (24 + 19 + 14 + 9 + 4) = 70 different elements.
And both Host and Partner can compute T from {x1,x2,x3,x4,x5}.
Now, among the 190 possible integers from 1 to 190, at least 70 are in T and could have been signalled with four of the given cards. Index the other (at most) 120 possibilities, and let the permutation of the five cards (x1,x2,x3,x4,x5) pick out one of these 190-|T| integers.
So the Host's strategy is: if the blue card's number is in one of the sets T1, T2, ..., T5, then pass the appropriate four cards in their appropriate order to signal it. Otherwise, we will pass all five white cards. Trust the Partner to calculate T, and arrange the five cards so that their permutation defines an index which picks out the correct element from the 190-|T| possibilities.
Olivier Miakinen submitted a solution with N=200. He uses similar techniques, but with S={0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 96, 60, 129, 186, 38, 57, 85, 127, 151, 152, 161, 190} having 22 elements, the largest overlap being of size 3, so that he achieves N=120+22+19+16+13+10=200. Congratulations, Olivier.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com