Information Gain


Information Gain image from book

image from book

The well-known and always well-dressed game show host Jeff Nicholas has approached Jordan and his 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. 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. I will be holding 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 or 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. “Remember, though, that each person sees the numbers on the other people’s hats too. You may not be able to solve this puzzle. I do want that suit.”

  1. Is it possible for Jordan to design a protocol to ensure that each of his friends will raise the correct number of fingers? If so, explain it. If not, does Jordan have a high probability of winning?

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 (as in 4, 5, 6, 7, 8). Then what could Jordan do?

Solution to Warm-Up

Jordan could arrange the following protocol with his friends. Let Ariana represent 1, Bob represent 2, Caroline represent 3, David represent 4 and Ellen represent 5 and 6. If Jordan sends a ticket to Ariana, then the consecutive numbers start with 1. If to Bob, then they start with 2. If to Caroline, then 3. If to David, then 4. If a blue ticket to Ellen, then 5. If a red ticket to Ellen, then 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?




Puzzles for Programmers and Pros
Puzzles for Programmers and Pros
ISBN: 0470121688
EAN: 2147483647
Year: 2007
Pages: 81
Authors: Dennis Shasha

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net