The Chaos Legion is an infamous criminal organization, responsible for every major disaster in history from the burning of the Library of Alexandria to the recent Sony hack. The Order of Seven is their antithesis, and have been investigating the Chaos Legion for hundreds of years with no avail. They want to determine the leader of the Chaos legion, but so far, only know that (s)he is one of 256 people.
Fortunately, the Order now have an opportunity to send two undercover agents into Chaos's upper ranks. The lucky recruits are named James and Jimmy. The plan is this: James will go very deep undercover, and will be able to determine the leader. However, he will be so entrenched that he can no longer safely communicate with the Order. That's where Jimmy comes in: Jimmy will go undercover, but not as deeply, so that he can still communicate with the Order. Jimmy's cover will afford him some information: he will be able to narrow down the list of possible leaders to only 2 people.
James needs to communicate the leader's identity to Jimmy. The problem is, the only way they will be able to safely communicate with each other is via a very crude text messaging service. Each message consists of a string of $0$'s and $1$'s, and the cost of a message is $\$1$ million per symbol! Furthermore, the time it takes to send a message is wildly unpredictable, so they can't use the timing of messages to convey extra information. An empty text can't be sent either.
They will have to agree on what these $0$'s and $1$'s mean before starting the mission. There is a way to get away with spending $\$8$ million: James sends Jimmy, in binary, the position of the leader on an alphabetical list of the 256 original suspects. This doesn't make any use of Jimmy's knowledge, so perhaps they can do better. In fact, they better be able to: the Order only has a budget of $\$4$ million!
- Both James and Jimmy know the leader is one of $256$ people.
- Some time into the operation, James will know the leader, while Jimmy will know a set of two people, one of whom is the leader. James will not know Jimmy's list.
- James needs to tell Jimmy the leader.
- Each of James and Jimmy can text the other, but sending each bit costs $\$1$ million. Once Jimmy knows the leader, he can tell the Order this for free.
- They can only spend $\$4$ million.
Can the Order succeed? Or will Chaos prevail?