Solution for December 2009

The Problem:

stamp-search.com   Snow White married the prince and lived happily ever after.  Eventually the mine closed and the seven dwarfs went into retirement, living scattered across the country and keeping in touch by e-mail. They still come together during the holiday season and exchange gifts, but now setting up the gift exchange list presents a problem: At the beginning of each December when they lived together, each would draw a name from a bag to decide the one person to whom they would give a present that year. They can no longer do it that way because they won't meet until Christmas, and then it will be too late. The natural idea—appointing one of them to draw the names out of the bag, and informing each participant the name of the person whose gift they are to buy—is inconvenient for at least two reasons: The dwarf making the drawing would know who buys him a gift, which would spoil the surprise. There would be no guarantee of randomness: the dwarf setting up the exchange list could fabricate it instead of making a random draw. This is a difficulty because Grumpy and Doc are prone to complain. Our December problem is to devise an e-mail equivalent of the random draw that would satisfy everybody.  Set up a way for the dwarfs and Snow White to exchange information by e-mail so that No outside help from other persons or software is used; Everybody ends up with the name of the person for whom they are to buy a gift; everybody gets a gift, and everybody gives a gift. Nobody gets to know the name of the person buying his gift, and nobody can single handedly decide that person X buys a gift for person Y. Perhaps your method may even improve on the paper bag: If a dwarf picks his own name from the bag, then they have to repeat the draw. Try to devise a method where such an occurrence is not possible. Thanks to Matthieu Dufour who sent us this problem he found from personal experience, having found himself in the position of the seven dwarfs.

Correct responses:
	Correct solutions were sent in this month by Bojan Basic (Serbia) Tom Fuzzesy (Regina) John Campbell (Alberta) Magnus Jakobsson (Sweden) Philippe Fondanaiche (France) John T. Robinson (USA) The Math 20 IB class, Archbishop MacDonald High School (Edmonton, Alberta)

The solution:

Our correspondents came up with interesting and imaginative ways to solve the problem. We will first present the solution of John Campbell, add ideas from other correspondents, and end with the solution of Magnus Jakobsson.

Campbell's solution.  Let the eight participants be D(1) through D(7), and Snow White D(8).  With the traditional gift exchange, each participant draws the name of a person to buy a gift for; in our version, participants will each select a number representing a participant unknown to them who will buy their gift.

Stage one.  They first create a column of random numbers.  D(1) starts the column by sending a random number in an email to D(2).  In turn, each participant D(i), i = 2, ..., 7, will reshuffle the column of random numbers received from D(i – 1), insert his own (new) random number on a new line somewhere in the column, and send the resulting column to D(i + 1).  Finally, Snow White (D(8)) reshuffles the column received from D(7), adds her own random number on a new line somewhere in the column, and returns the list to D(1).

Stage two.  A list of gift givers is created.  D(1) places his name next to one of the random numbers other than his own, changes his own random number, reshuffles the column and sends it to D(2).  In turn, each participant D(i), i = 2, ..., 7, will add his name next to one of the random numbers other than his own, change his own random number, reshuffle the column of random numbers received from D(i – 1), and send the result to D(i + 1).  When Snow White receives the list, she will add her name next to the last random number if it is not her own, change her own random number, and send the list back to D(1).  If the last random number is her own, she will inform everybody by email that the process has failed, and they must start over again at Stage one.

Stage three. The list is circulated.  After Stage two has succeeded, some participants will already know the recipient of their gift, but the list must be circulated again to make sure everybody knows.  In turn, each participant D(i), i = 1, ..., 7 will note the name next to his random number; this is the person he gives a gift to.  He then changes his random number and sends the list to D(i + 1).  When Snow White receives the list, everybody knows for whom to get a gift.  However, since everybody sees an entirely new list of random numbers each time it passes by, nobody can deduce any of the other pairings.

            There is a one in eight chance that in Stage two Snow White ends up with her own random number, which necessitates restarting the whole process.  To avoid this hassle, Basic and, independently, the Archbishop MacDonald High School students used the fact that 8 is even: at the end of Stage one, before returning the list to D(1), Snow White writes down "group A'' next to four of the random numbers, and ''group B'' next to the remaining four numbers.  In Stage two, the participants in Group A will write their name next to a Group B number, and vice versa.

Jakobsson's solution.
Stage one.  A list of secret givers is created. Snow White starts the list by writing to a random dwarf, "Do you want to be giver number 1?''  Next, for i = 1, ..., 7, when a dwarf or Snow White receives the message, ''Do you want to be giver number i?'', that person either can reject it — perhaps at an early point in the process by flipping a coin, or later on, by reason of having already accepted a number — and forward it to another random participant; or he can accept it and send the message "Do you want to be giver number i + 1?'' to another random participant.  Each participant accepts being a giver only once. Stage one ends when someone agrees to be giver number 8.

Stage two.  A list of secret receivers is created. Giver number 8 sends the message "Do you want to be receiver number 1?'' to a random participant. Next, for i = 1, ..., 7, when a dwarf or Snow White receives the message, ''Do you want to be receiver number i?'', that person can either reject it and forward it to another random participant, or accept it and send the message "Do you want to be receiver number i + 1?'' to another random participant.  Each participant should accept being a receiver only once, and giver number i should not agree to being receiver number i.  Also, to avoid the possibility that giver number 8 has no option other than being receiver number 8, there is a supplemental rule: nobody except giver number 8 can accept being receiver number 7 until he is certain that all seven other participants have seen the invitation to be receiver number seven (by receiving the invitation from four of them and forwarding it to the other three).  Stage two ends when somebody agrees to be receiver number 8.  Receiver number 8 then emails to everybody, "I am receiver number 8'', and at this point everybody else also circulates his receiver number.  Now everybody knows for whom to get a gift.