Ponder This Challenge - October 2000 - One+five(four) cards trick

Ponder This Challenge:

This puzzle is due to a suggestion by Denis Borris.
(Thanks, Denis.)

Part A:
There are three participants: a Host, a Partner, and a Volunteer.
The Partner is in a soundproof room.
The Host gives the Volunteer six blank cards, five white and one blue.
The Volunteer writes a different integer from 1 to 125 on each card, as the Host is watching.
The Volunteer keeps the blue card.
The Host arranges the five white cards in some order and passes them to the Partner.
The Partner then announces the number on the blue card.
How?

Part B:
Same set-up, except:
The integers now range from 1 to N, where N=190.
The Host can either pass all five white cards, as before, or discard one and just pass four cards.

Part B is much harder than Part A. Special mention will be given to the first person to give a justifiable procedure that works when N is at least 190; and to the first person to give a justifiable procedure for the largest value of N submitted (even if that's smaller than 190).

Notes:
There are no tricks like upside-down cards; the only information that the Partner gets is the cards and their ordering.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  Part A:

  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.

  Select a set S of 24 distinct integers between 0 and N-1, satisfying the following property:
  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.

Solvers

• Part A: (None)
• Olivier Miakinen (10.02.2000 @ 12:42 PM EDT)
• Mat Newman (10.02.2000 @ 1:23 PM EDT)
• Ether Jones (10.02.2000 @ 2:23 PM EDT)
• Ravishankar Arunachalam (10.02.2000 @ 2:30 PM EDT)
• Michael Malak (10.02.2000 @ 3:26 PM EDT)
• Prithu (10.03.2000 @ 9:14 AM EDT)
• David J McKee (10.03.2000 @ 9:14 AM EDT)
• Muralidhar Seshadri (10.03.2000 @ 7:47 AM EDT)
• Guenter Mair (10.03.2000 @ 7:55 AM EDT)
• Daniel Li (10.03.2000 @ 2:05 PM EDT)
• Ashish Kadakia (10.03.2000 @ 2:05 PM EDT)
• Ming Song (10.03.2000 @ 4:10 PM EDT)
• Alec Spiegelman (10.03.2000 @ 4:14 PM EDT)
• Joseph DeVincentis (10.03.2000 @ 5:10 PM EDT)
• Alexey Vorobyov (10.03.2000 @ 9:56 PM EDT)
• Amos Guler (10.04.2000 @ 2:43 AM EDT)
• Ashutosh Misra (10.04.2000 @ 7:44 AM EDT)
• Thomas Rohr (10.04.2000 @ 10:45 AM EDT)
• Alexis Megas (10.04.2000 @ 2:44 PM EDT)
• Manikantan Srinivasan (10.04.2000 @ 5:35 AM EDT)
• Jim Schnelker (10.04.2000 @ 11:07 PM EDT)
• Simon Andersson (10.05.2000 @ 12:07 AM EDT)
• Tim Edmonds (10.05.2000 @ 10:50 AM EDT)
• Khaled Fayed (10.05.2000 @ 11:11 AM EDT)
• Gustavo Durand (10.05.2000 @ 2:59 PM EDT)
• Vic Monell (10.05.2000 @ 4:43 PM EDT)
• William Mather (10.05.2000 @ 8:55 PM EDT)
• Trevor Strohman (10.05.2000 @ 11:11 PM EDT)
• Ian Lovely (10.06.2000 @ 9:14 AM EDT)
• Bhuvan Urgaonkar (10.06.2000 @ 5:35 PM EDT)
• Dmitri Asonov (10.07.2000 @ 1:43 PM EDT)
• Jessica Jo Lang (10.10.2000 @ 2:26 PM EDT)
• Philip Nanni (10.08.2000 @ 3:41 AM EDT)
• Eduard Tita (10.09.2000 @ 4:33 AM EDT)
• Jonathan Wildstrom (10.09.2000 @ 4:36 PM EDT)
• Murali Prakash (10.11.2000 @ 9:26 AM EDT)
• Francis Golding (10.11.2000 @ 5:52 PM EDT)
• Mohit Sauhta (10.12.2000 @ 12:25 PM EDT)
• Shmuel Spiegel (10.12.2000 @ 9:28 PM EDT)
• Christie Bolton (10.14.2000 @ 12:20 PM EDT)
• Samy Tawab (10.14.2000 @ 10:37 PM EDT)
• Robert Danek (10.15.2000 @ 1:47 PM EDT)
• Subrahmanyam Devulapalli (10.16.2000 @ 9:31 PM EDT)
• Senthil Nathan G (10.17.2000 @ 2:49 AM EDT)
• Paul Gover (10.20.2000 @ 11:19 AM EDT)
• Robin Munn (10.22.2000 @ 5:20 PM EDT)
• Jonathan Hayward (10.22.2000 @ 5:20 AM EDT)
• Stephen Merriman (10.23.2000 @ 10:55 AM EDT)
• Anand Rangarajan (10.23.2000 @ 2:44 AM EDT)
• George Tolley (10.24.2000 @ 11:47 AM EDT)
• Dieter Verhofstadt (10.26.2000 @ 6:21 AM EDT)
• Laura Apostoloiu (10.27.2000 @ 1:26 PM EDT)
• Bernd Beimel (10.28.2000 @ 5:04 PM EDT)
• Sujith Vijay (10.31.2000 @ 7:50 AM EDT)
• Nagendra (10.31.2000 @ 8:08 AM EDT)
• Part B: (None)
• Eureka! (We have a correct respondent @ N=200)
• (We have a correct respondent @ N=200)
• Olivier Miakinen (None)
• Prithu (None)
• Muralidhar SeshadriDaniel LiThomas RohrMichael Malak & Brian Murphy (None)
• Ming Song (None)
• Jim Schnelker (None)
• Simon Andersson (None)
• Manikantan Srinivasan (None)
• Alexey Vorobyov (None)
• Tim Edmonds (None)
• Vic Monell (None)
• Trevor Strohman (None)
• "&" (None)
• Ian Lovely (None)
• Dmitri Asonov (None)
• Jessica Jo Lang (None)
• Jonathan Wildstrom (None)
• Francis Golding (None)
• Mohit Sauhta (None)
• Christie Bolton (None)
• Samy Tawab (None)
• Senthil Nathan G (None)
• Paul Gover (None)
• Jonathan Hayward (@ N=147)
• Stephen Merriman (None)
• Dieter Verhofstadt (None)
• Bernd Beimel (None)