Solution for March 2008

The Problem:

MP76 March 2008 Four students, Adam, Barbara, Clara, and Dan, will win a prize if all of them succeed in their task:  One by one they will be taken into a room where there are four curtains, numbered one to four.  The letters from A to D are written on four cards -- each letter on one and only one card -- and the cards are placed at random behind the curtains, one card behind each curtain.  Each student will be allowed to look behind two curtains of his choosing.  A student who finds a card with the first letter of his name behind one of his two chosen curtains succeeds.  If all four students succeed, the group wins.  If one or more does not succeed, the group loses.   The students are allowed to agree on a strategy together before the first is taken into the room.  However, once a student has been in the room, no further communication is permitted, either by words or by signal.  Additionally, students who have not been in the room have no way of knowing whether pervious students were successful or not. If each student looks behind two curtains at random, each has a probability of 50% of succeeding, and the group would have a 6.25% probability of winning.  Your challenge is to devise a strategy to give the group a probability of over 40% of winning.  Please justify any your claims.

Correct responses:

We found this month's problem in a journal of the Casualty Actuarial Society, which used the problem without referring to its source.  Fondanaiche kindly supplied a reference for the puzzle.  In a different form the puzzle was originally devised by computer scientist Peter Bro Miltersen of the University of Aarhus, Denmark.  It appears in a 2003 paper on substring searches presented at a conference on automata, languages, and programming. [See the references in Science News Online www.sciencenews.org/articles/20060819/mathtrek.asp.]  It has been popularized by Peter Winkler and will appear in Volume II of his Mathematical Puzzles: A Connoisseur's Collection (A.K. Peters).  We received correct solutions from Bojan Basic (Serbia), Gérard Billion (France), Lou Cairoli (USA), Philippe Fondanaiche (France), Jacques Mertzeisen (France), John T. Robinson (USA), and A. Teitelman (Israel).  They all proposed the same strategy:

The solution:

The students first establish a correspondence between their initials and the curtains, obtaining an unambiguous ordering of the curtains.  Each student then looks first behind the curtain that corresponds to his initial.  If the card behind that curtain matches the initial of his first name, he is successful and can leave; if it contains a different letter, he would then look behind the curtain corresponding to that letter.  For example, Adam will first look behind the curtain that corresponds to "A" and would succeed if the cards behind the four curtains had been placed in one of the 6 orders

ABCD, ABDC, ACBD, ACDB, ADBC, or ADCB.

If instead he found the letter B or C or D behind his curtain, he would win with the orders

BACD, BADC; or CBAD, CDAB; or DBCA, DCBA.

Among those 12 permutations favorable for Adam all but two, namely ACDB and ADBC, will be favorable also for Barbara.  Happily, the ten that remain will also lead to success for Clara and Dan, so that the group succeeds with 10 of the possible permutations of the letters.  Since there are 4! = 24 equally likely permutations, the probability that the group succeeds is 10/24, which is about 41.67%.

Comments.

1. This problem provides a simple illustration of the importance generally of exploiting all available information in order to improve the odds of making a correct decision.  As pointed out in the statement of the problem, if the students fail to use the information learned from their first choice, the chance of success drops from 41.67% to 6.25%.  Compare this situation to the statistician who bases his decision on averages instead of using all the information available to him.  For example, many of us wonder about such a strategy when traveling in an airplane whose seats seem designed for the average human without any regard for the distribution of human sizes; alas, the average they used was probably taken from a century when people were a lot smaller.
   
   
2. When the number of possibilities is small as in our problem, the easiest way to count the number of successful outcomes is to make a list.  Both Billion and Robinson looked at generalizations involving a greater number of participants, where a list is no longer practical.  Consider the problem with n students, each with two choices, and the same strategy.  Let N_n be the number of successful permutations of their names.  The number of successful permutations with the first student's name behind the first curtain equals the number of successful permutations for the remaining n – 1 participants, namely N_n–1.  He can also be successful if the name behind the first curtain leads him to a curtain that has his name behind it; this leads to the group's success in (n – 1)N_n–2 permutations (N_n–2 permutations for each of the n – 1 possible names behind the first curtain).  The probability that the group of n students is successful is then P_n= N_n/n!.  Since N₁ = 1 and N₂ = 2, the first few values are
               N₃ = 4      P₃ = 4/6 ≈ .67
               N₄ = 10      P₄ = 10/24 ≈ .417
               N₅ = 26      P₅ = 26/120 ≈ .217
               N₆ = 76      P₆ = 76/720 ≈ .106.
         Billion and Robinson also considered the possibility that the group of n students each could choose k curtains to look behind.  The strategy here is for each student to start with the curtain corresponding to his name, then next choosing the curtain corresponding to the name found behind the previous curtain, and continuing until finding his name (and thus be successful) or failing all k times.  We see that the group will win as long as the permutation of the names behind the curtains has no cycle of length greater than k.  Counting the number of permutations with k or fewer cycles is easily accomplished (by computer) with a recursive formula such as found in Sloan's online encyclopedia of sequences,
   http://www.research.att.com/~njas/sequences/A057693.
         Winkler's problem mentioned at the start was to find the probability of being successful when n = 100 students each get k = 50 choices.  Here it is easier to count the number of permutations that fail — that is, those permutations having a cycle of length 50 or more.  The probability of success is then
   1 – 1/51 – 1/52 – … – 1/100 ≈ .3118.
         That probability of 31% is truly remarkable when compared with the near impossibility of success with a less effective strategy.  Details concerning this version of the problem and the computation can be found in
   The College Mathematics Journa, 34:4 (September, 2006) pages 260, 285, and 289.