The well-known and always well-dressed game show host Jeff Nicholas has approached Jordan and five of his mathematically inclined friends–Ariana, Bob, Caroline, David and Ellen–with a contest proposition. Jordan and the five are the leading lights of the omniheurist club, a group of outstanding puzzle solvers. “Our contest is live,” Jeff explains. “I will blindfold your friends, then put a hat on each of them bearing a number between 1 and 10 (more than one person may have the same number) and lead them into a televised game room. Once they have arrived, I will arrange them in a circle in an order that I choose and then replace each blindfold by very dark but non-reflecting sunglasses to eliminate the possibility of eye signals. “You and the audience will see them in the game room and the numbers on their heads via the television monitor, but they won’t be able to see you. You will be given one blue ticket and one red ticket. You can ask me to deliver one ticket to one of the five. That’s all you can do. No knocking on the window or your team will be disqualified. “The mathematicians may not speak nor signal one another in any way or the entire team will be disqualified. (Obviously, I won’t help them in any way other than delivering the ticket). They will however see to whom the ticket is being delivered and the color of the ticket as well as the number on each other person’s hat. There is no way they can see the numbers on their own heads. “At my signal each person will put up a certain number of fingers. If the number of fingers matches the number on that person’s hat, then he or she will receive that many thousands of dollars. If all of them win, then you Jordan will receive $5,000. If any lose, then you have to buy me a new Armani suit.” “That’s it?” Jordan replied. “The only information they receive from the outside is who gets a ticket and the color of that ticket?” “That’s right,” said Nicholas. “Also remember that each person sees the numbers on the other people’s hats too. It’s not that easy, though, I admit, and I do want that suit.” Problem: Is it possible for Jordan to design a protocol such that each of his mathematician friends can be certain to raise the correct number of fingers? If so, explain it. Otherwise, can Jordan and his friends win with high probability? Warm-Up: Here’s a much easier problem to give you an idea of the kind of protocol Jordan might design. Suppose Jeff Nicholas were required to put consecutive numbers on the five hats (e.g. 4, 5, 6, 7, 8). Then what could Jordan do? Solution to Warm-Up: Jordan could arrange the following protocol with the mathematicians. Before the game begins, the group agrees that Ariana will represent 1, Bob will represent 2, Caroline will represent 3, David will represent 4 and Ellen will represent 5 and 6. (These prearranged numbers have nothing to do with which numbered hats Jeff will later give them, as you will see.) It is also agreed that if Jordan sends a ticket to Ariana, then the consecutive numbers on the five hats start with 1. If he sends a ticket to Bob, they start with 2. If to Caroline, they start with 3. If to David, they start with 4. And if Jordan sends the blue ticket to Ellen, they start with 5 but if he sends the red ticket, they start with 6. (Since there are five consecutive numbers and the highest possible one is 10, the sequence can’t start with anything higher than 6.) Thus, when Jordan sends in a ticket, each mathematician will know the first number in the sequence. And by looking at the numbers on his or her fellow players’ hats, that mathematician can work out by process of elimination which number appears on his or her own hat. In the Jeff Nicholas challenge, however, the numbers are not necessarily consecutive or even all distinct. Do you think it can be done? Hint: think carefully about the information that all of the mathematicians share.
“Our contest is live,” Jeff explains. “I will blindfold your friends, then put a hat on each of them bearing a number between 1 and 10 (more than one person may have the same number) and lead them into a televised game room. Once they have arrived, I will arrange them in a circle in an order that I choose and then replace each blindfold by very dark but non-reflecting sunglasses to eliminate the possibility of eye signals.
“You and the audience will see them in the game room and the numbers on their heads via the television monitor, but they won’t be able to see you. You will be given one blue ticket and one red ticket. You can ask me to deliver one ticket to one of the five. That’s all you can do. No knocking on the window or your team will be disqualified.
“The mathematicians may not speak nor signal one another in any way or the entire team will be disqualified. (Obviously, I won’t help them in any way other than delivering the ticket). They will however see to whom the ticket is being delivered and the color of the ticket as well as the number on each other person’s hat. There is no way they can see the numbers on their own heads.
“At my signal each person will put up a certain number of fingers. If the number of fingers matches the number on that person’s hat, then he or she will receive that many thousands of dollars. If all of them win, then you Jordan will receive $5,000. If any lose, then you have to buy me a new Armani suit.”
“That’s it?” Jordan replied. “The only information they receive from the outside is who gets a ticket and the color of that ticket?”
“That’s right,” said Nicholas. “Also remember that each person sees the numbers on the other people’s hats too. It’s not that easy, though, I admit, and I do want that suit.”
Problem: Is it possible for Jordan to design a protocol such that each of his mathematician friends can be certain to raise the correct number of fingers? If so, explain it. Otherwise, can Jordan and his friends win with high probability?
Warm-Up: Here’s a much easier problem to give you an idea of the kind of protocol Jordan might design. Suppose Jeff Nicholas were required to put consecutive numbers on the five hats (e.g. 4, 5, 6, 7, 8). Then what could Jordan do?
Solution to Warm-Up: Jordan could arrange the following protocol with the mathematicians. Before the game begins, the group agrees that Ariana will represent 1, Bob will represent 2, Caroline will represent 3, David will represent 4 and Ellen will represent 5 and 6. (These prearranged numbers have nothing to do with which numbered hats Jeff will later give them, as you will see.) It is also agreed that if Jordan sends a ticket to Ariana, then the consecutive numbers on the five hats start with 1. If he sends a ticket to Bob, they start with 2. If to Caroline, they start with 3. If to David, they start with 4. And if Jordan sends the blue ticket to Ellen, they start with 5 but if he sends the red ticket, they start with 6. (Since there are five consecutive numbers and the highest possible one is 10, the sequence can’t start with anything higher than 6.) Thus, when Jordan sends in a ticket, each mathematician will know the first number in the sequence. And by looking at the numbers on his or her fellow players’ hats, that mathematician can work out by process of elimination which number appears on his or her own hat.
In the Jeff Nicholas challenge, however, the numbers are not necessarily consecutive or even all distinct. Do you think it can be done? Hint: think carefully about the information that all of the mathematicians share.
