14
$\begingroup$

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!

To summarize:

  • 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?

Source: http://math.stanford.edu/~notzeb/puzzle.html

Improve this question
$\endgroup$
4
  • $\begingroup$ Question: If Jimmy knows 2 people, cant you get away with sending 1 bit? ($0$ for the first person in Jimmy's set and $1$ for the second) $\endgroup$
    – user10203
    Commented Apr 19, 2015 at 8:13
  • $\begingroup$ @Reticality See the second bullet point: James does not know Jimmy's list. $\endgroup$
    – Mike Earnest
    Commented Apr 19, 2015 at 8:15
  • $\begingroup$ I highly recommend this puzzle. The claim seemed totally impossible until I reached a breakthrough. $\endgroup$
    – xnor
    Commented Apr 19, 2015 at 8:20
  • 2
    $\begingroup$ In the puzzle you linked, it says that if a person sends two texts, they might be delivered out of order. If you intended this to be the case here, it might be worth saying so explicitly. $\endgroup$
    – Julian Rosen
    Commented Apr 19, 2015 at 15:46

2 Answers 2

Reset to default
12
$\begingroup$

The best you can do is:

$3 million.

The proof is:

Number the suspects in binary. Suppose the binary descriptions of Jimmy's suspects differ in position $i$, where we start counting from $0$. If $i$ is between $0$ and $3$, Jimmy sends a message with two bits describing $i$, and James replies with the value of bit $i$. If $i$ is $4$ or $5$, Jimmy sends a message consisting of just the bit $0$, and James replies with the values of bits $4$ and $5$. If $i$ is $6$ or $7$, Jimmy sends a message consisting of just the bit $1$, and James replies with the values of bits $6$ and $7$. (That you can't do it with $2 million is sort of obvious.)

Improve this answer
$\endgroup$
5
  • $\begingroup$ of course, the first time I solved this puzzle it took me more than a day... $\endgroup$
    – zeb
    Commented Apr 19, 2015 at 10:10
  • 1
    $\begingroup$ If I'm reading your answer right there is a 1 bit saving in 50% of cases. . If any of the 2 bit responses from James have a leading 0 that bit could be omitted. $\endgroup$
    – Bob
    Commented Apr 19, 2015 at 10:18
  • 1
    $\begingroup$ hmm, yeah. Seems like we could deal with up to 576 suspects. $\endgroup$
    – zeb
    Commented Apr 19, 2015 at 10:22
  • 2
    $\begingroup$ Woah, I got the same solution as xnor, I didn't expect we can do it in only 3 bits! Guess you can use your $1 million left over for your vacation ;) By the way, in this solution, how would James know that the message that Jimmy sent consists of only 1 bit instead of needing to wait whether there will be second bit coming later (due to the wildly unpredictable timing)? $\endgroup$
    – justhalf
    Commented Apr 27, 2015 at 14:45
  • 3
    $\begingroup$ This seems like 4 bits from an information theory perspective. The length of the first message cam be either 1 or 2, so that conveys an additional bit of information. $\endgroup$
    – Robert Fraser
    Commented Jun 4, 2016 at 9:45
8
$\begingroup$

Yes, they can do it in 4 bits.

Naturally, James and Jimmy agree beforehand to represent each potential leader as a vector in $(0,1)^8$. Jimmy looks at his two suspects, and notes an index where their vectors differ. He conveys this index using James in 3 bits. James responds with the leader's vector entry at that index, for 1 bit. This lets Jimmy determine which of the two suspects is leader.

In general, if there's $2^{2^n}$ members, then this can be done in $n+1$ bits.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Indeed, that is perfect! Would you mind covering this in spoilers? $\endgroup$
    – Mike Earnest
    Commented Apr 19, 2015 at 8:17
  • $\begingroup$ OK, spoilered. Do you know a proof of optimality? $\endgroup$
    – xnor
    Commented Apr 19, 2015 at 8:19
  • $\begingroup$ What a pleasing eureka! Although I was almost hoping to take advantage of Jimmy having, in a way, 14 T/F questions at his disposal, namely, 8 3-bit questions (all he needs), 4 2-bit questions, and 2 1-bit questions, with chance of a second volley if he goes with a 1-bit question... Do you think this means this same method would work on a larger pool of suspects, or am I off base? $\endgroup$
    – Caleb
    Commented Apr 19, 2015 at 8:38
  • $\begingroup$ I do not as of yet. It seems like you would have to break all possible three bit protocols into cases, 3,2-1,1-2,1-1-1, then argue differently for each. $\endgroup$
    – Mike Earnest
    Commented Apr 19, 2015 at 8:39
  • 1
    $\begingroup$ They can trivially communicate the leader among 2^14 suspects (Jimmy sends a 3-bit question to refer to the last 8 indices, a 2-bit question to refer to the next 4, and a 1-bit question to refer to the first two indices.) So using this exact same setup, Jimmy can learn the identity among 16,384 suspects. He can possibly squeeze a few more out of that with a different protocol, and I'd also be interested in seeing the highest number of suspects possible if Jimmy has it whittled down to 3 suspects. $\endgroup$
    – Caleb
    Commented Apr 19, 2015 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.