Official solution:
SOLUTION: Romeo and Juliet can, in advance, label the 16 teams (in alphabetic order, perhaps) by the binary numbers 0000 through 1111. Then, when the time comes, Romeo can send Juliet eight bits: the four bits corresponding to one team, and the four bits corresponding to the other one. Juliet can then send back a 0 if the winning team was the one with the smaller number, and a 1 otherwise. That comes to nine bits, and we can trim that to 8 by noting that the number of unordered pairs of teams is only 16 x 15/2 = 120 which is less than 2 to the seventh power, thus Romeo can code the matchup with only seven bits.
But an easier and faster solution is to just have Juliet send Romeo the four bits corresponding to the winning team. Surely, we can't do any better than four bits, right?
Amazingly, we can! We can name those four positions in the team codes (leftmost, next-to-left, next-to-right, rightmost) by, say, 00, 01, 10, and 11 respectively. The codes of the two playing teams must differ in at least one of the four positions; Romeo picks such a position and sends its name (two bits) to Juliet. She now only needs to look at the value of the bit in that position of the winning team and send it to Romeo. Three bits total!
For example, suppose the playing teams are 0010 and 0110, and 0110 won. The only position where the playing teams differ is the next-to-left, the "01" position, so Romeo must send "01" to Juliet. She checks the next-to-left position of the winning team — it is a "1" — and sends that "1" to Romeo. Done.
It can be shown that three bits is unbeatable. Note that in the most efficient communication scheme, more information is passed from the student to the teacher than vice-versa. Is there a lesson to be learned from that?
[Devised and communicated to me by Alon Orlitsky, of the University of California, San Diego.]
