How is it done?
My explanation, of MK's explanation, of EB's brilliant solution of the general 'choose any n from ( n !+ n -1) '.
Like MK I will examine the case n =5 (every essential point may be seen in this case; also it's not too big to handle, and not so small that one can't see the point because so little is going on). Let C 's chosen numbers - between 0 and 123 - be . A will then pass 4 of those 5 cards to P (in a certain order), allowing P to declare the hidden 5th number.
How is it done? First A calculates 2 important numbers ' i ' and ' s ', both of which P may later calculate after the 4 cards are passed:
Thus the hidden card satisfies (the vital congruence; 'vital' for reasons that will only be apparent later)
(mod 5) ... (1)
(If you're not fluent with congruences, do a few examples to fix that last important detail: suppose the c 's were 17, 38, 62, 116 and 120. Then
Now, imagine removing the 4 cards
from the original 124 numbers (0, 1, 2, 3, ... , 123), and renumber the remaining 120 (=5!) by shifting to the left. In our example
Thus 116 (=
, the
hidden
card) gets shifted 3 (=
i
) places to the left, and thus
's
new location
is congruent to (-
s
) (mod 5). In the
general
case where '
i
' and '
s
' are defined by
after renumbering
's
new
number will be (
), giving
(mod
n
). If
i
=0 then
does not get shifted to the left, and its new location - after removing the other (
n
-1)
c
's - is the same as its earlier one; otherwise
gets shifted 1 or 2 or ... or (
n
-1) places to the left.
Question . Which numbers (between 0 and 119) are congruent to (- s ) (mod 5)?
Answer, and the point of it all :
In both cases (and P , knowing the value of s upon receipt of the 4 cards, will know which case is happening) there are exactly 24 (=4!) unknown (to P ) numbers, and A has exactly 24 (=4!) ways in which to pass the 4 cards. THAT'S IT!! All that A and P have to agree upon in advance is a precise correlation between the 4! numbers 0 , 1 , 2 , ... , 23 and the 4! different signals that can be passed with 4 cards, and finally make a use of the congruence (1) above, in order to determine the value of ' i '. The detail is almost an anti-climax: