Fun Brain Teaser
Alice and Bob are both very interested in the results of a tournament held between 256 contestants. They have spent the past few weeks learning everything about the contestants, their strengths and weaknesses, etc. They don’t know what the match-ups are going to be before the tournament begins (it is decided by lottery). Alice manages to get a ticket to watch the tournament, and watches all the way until the final match between the last two contestants, but unfortunately has to leave to go to work before the outcome is decided. While Alice is at work, Bob listens to the radio and hears the name of the final winner of the tournament, but he doesn’t know who the runner-up was. Bob wants to tell Alice who the final winner was, but since this puzzle takes place in the future, the only method of communication is text messaging. The text messaging company charges 100 dollars per bit sent in a text message, and refuses to deliver empty messages. Although a text message is usually delivered within a second of being sent, occasionally it is delayed by a minute, sometimes by a day, rarely by a week, and once (according to rumor) by an entire century. If two text messages are sent, it is possible that they will be delivered out of order. Alice and Bob anticipated this situation beforehand, and devised a strategy to let Alice know the identity of the final winner while spending the least possible amount of money between the two of them. What is it?
Seems like a typical brain-teaser at first, but it won’t be easy unless we breakdown this problem. What kind of smaller (broken-down) questions do we need to answer to solve the problem?
If you want to solve it yourself, stop reading now.
1. Knowledge of contestants: what do the contestants actually know.
Alice: Knows the last two contestants.
Bob: Knows the final winner.
2. The question: what is the problem actually asking for?
We need Alice to know who the winner winner is from the last two contestant. This means Bob just needs to let Alice know the winner. We should also take into the fact that they “devised a strategy” beforehand, so sending an 8-bit identifier of the winner is definitely not the solution, as that wouldn’t be a strategy but rather a solution.
3. The ACTUAL question: 8-bit identifier
How can we minimize the 8-bit identifier so that Bob can let Alice know the winner, in the minimum possible bits??
There seems to be a trick to this and if you’re familiar with bit manipulations then the solution should be familiar. First, we can assume that the two of them identified each and every player with 8-bit identifier codes beforehand (Since the question says they learned everything about the contestants, this is not a far-stretched assumption). This means that Bob knows the winner’s 8-bit identifier code and Alice knows the 8-bit identifier code of the last two contestants.
The strategy could be that Alice can send Bob the 3-bit code of the FIRST position of the codes that the two finalists differ in (since there are 8 positions, a 3-bit identifier is enough). When Bob receives this, he can send Alice the bit of the winner of that specific position. This means they spend AT MOST $400 (4 bits total).
Please let me know if you know a better way to solve this issue!