题目
Tristan和Isolde预计将处于一种通信极其受限的情形。
到那时，Tristan知道\(16\)支篮球队中究竟是哪两支打了一场比赛，而Isolde知道获胜的是哪一支队。
问：为了让Tristan最终知道谁赢了，他们之间最少需要传递多少比特的信息？
分析
把\(16\)支球队分别编成一个\(4\)位二进制数，从\(0000\)到\(1111\)。
Tristan知道参赛的两支队，所以他手里有两个不同的4位二进制串。既然它们不同，就至少有一位不同；当然，它们也可能有两位、三位甚至四位都不同，但这都不要紧，Tristan只需任选其中一位不同的位置即可。
于是他可以这样做：
- 选出这两个编号中某一位不同的位置；
- 把“看第几位”告诉Isolde。
因为一共只有\(4\)个位，所以这一步只需要\(2\)比特。
然后Isolde只需回传赢家在这一位上的值，是\(0\)还是\(1\)。这只需要\(1\)比特。
Tristan本来就知道那两支队在这一位上一个是\(0\)、一个是\(1\)，所以收到这个回答以后，立刻就能确定赢家。
因此，\(2+1=3\)比特足够。
例子
假设参赛的是\(0010\)和\(0110\)，而且\(0110\)赢了。这两个编号在从左数第二位不同，一个是0，一个是1。
所以Tristan把“看从左数第二位”这件事告诉Isolde。
Isolde知道赢家是\(0110\)，于是她回传这一位的值：\(1\)。
Tristan一看就知道，赢家只能是\(0110\)，因为\(0010\)在这一位上是\(0\)，而\(0110\)在这一位上是\(1\)。
为什么\(2\)比特不够
如果总共只有\(2\)比特，那么最有利的情形也不过是：
- Tristan先发\(1\)比特；
- Isolde再回\(1\)比特。
Tristan先发的这\(1\)比特，只能表示他在两种问题里选一种来问。
而每一种问题，本质上都可以看成：
“赢家是否属于某个球队集合\(S\)？”
也就是说，事先最多只能准备两个集合\(S_0,S_1\)。
于是每支球队都会对应一个两位身份码：
\[ (\text{是否在 }S_0\text{ 中},\ \text{是否在 }S_1\text{ 中}).\]
但两位二进制码最多只有\(4\)种，而球队有\(16\)支，所以一定有两支不同的球队身份码完全一样。
如果这两支球队正好比赛，那么不管Tristan问哪一个问题，Isolde的回答都会完全一样。这样Tristan就无法分辨到底是谁赢了。
所以\(2\)比特不可能总是够用。
综上，最少需要传递的比特数是\(3\)。
思考
这题本质上是在做“编码”。
Tristan知道候选者是哪两个，Isolde知道答案是哪一个；他们只需要找到一种极短的方式，把这两个候选者区分开。
对\(16=2^4\)支球队来说，用\(4\)位二进制编号正好最自然，而“先指出看哪一位，再回答这一位是\(0\)还是\(1\)”就是最省通信量的做法。
C++程序
下面这个程序不是用来“计算答案是\(3\)”，而是把题目里的通信协议做成一个小训练器。
程序会随机生成两支不同球队，再随机决定赢家。程序只显示球队编号\(0\)到\(15\)，不直接显示对应的\(4\)位二进制串；因此使用者需要自己先把编号转换成二进制，再分两步输入：
- 先扮演Tristan，输入\(2\)比特，表示“看哪一位”；
- 再扮演Isolde，输入\(1\)比特，表示赢家在这一位上的值。
如果你想直接下载源码，可以点击这里：players_and_winners_trainer.cpp.txt。由于GRAV通常不会直接提供.cpp文件，这里使用可下载的文本版本；下载后把文件名改回players_and_winners_trainer.cpp即可。
#include <iostream>
#include <random>
#include <string>
using namespace std;
bool isValidTwoBits(const string& code)
{
return code.size() == 2 &&
(code[0] == '0' || code[0] == '1') &&
(code[1] == '0' || code[1] == '1');
}
int decodePosition(const string& code)
{
if (code == "00") return 0;
if (code == "01") return 1;
if (code == "10") return 2;
return 3;
}
int bitAtFromLeft(int team, int position)
{
return (team >> (3 - position)) & 1;
}
int main()
{
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<int> teamDist(0, 15);
uniform_int_distribution<int> winnerDist(0, 1);
int teamA = teamDist(gen);
int teamB = teamDist(gen);
while (teamB == teamA)
{
teamB = teamDist(gen);
}
int winner = winnerDist(gen) == 0 ? teamA : teamB;
cout << "Players and Winners 训练器\n\n";
cout << "本轮两支参赛队是：\n";
cout << "A = " << teamA << '\n';
cout << "B = " << teamB << "\n\n";
cout << "注意：请你先把它们各自转换成 4 位二进制。\n\n";
cout << "现在请你扮演 Tristan。\n";
cout << "请输入 2 比特，表示你要看哪一位：\n";
cout << "00 -> 第1位（从左到右）\n";
cout << "01 -> 第2位\n";
cout << "10 -> 第3位\n";
cout << "11 -> 第4位\n";
string tristanCode;
cin >> tristanCode;
if (!isValidTwoBits(tristanCode))
{
cout << "输入无效：Tristan 必须输入 2 比特。\n";
return 0;
}
int position = decodePosition(tristanCode);
int bitA = bitAtFromLeft(teamA, position);
int bitB = bitAtFromLeft(teamB, position);
cout << "\nTristan 选择看第" << position + 1 << "位。\n";
if (bitA == bitB)
{
cout << "这一步无效，因为两支队在这一位上相同，无法区分赢家。\n";
cout << "A 的该位是 " << bitA << "，B 的该位也是 " << bitB << "。\n";
cout << "真实赢家其实是编号：" << winner << '\n';
return 0;
}
cout << "可以，这一位上两支队不同。\n\n";
cout << "现在请你扮演 Isolde。\n";
cout << "请输入 0 或 1，表示赢家在第" << position + 1 << "位上的值：";
char isoldeBit;
cin >> isoldeBit;
if (isoldeBit != '0' && isoldeBit != '1')
{
cout << "输入无效：Isolde 必须输入 0 或 1。\n";
return 0;
}
int correctBit = bitAtFromLeft(winner, position);
int guessedWinner = (bitAtFromLeft(teamA, position) == (isoldeBit - '0')) ? teamA : teamB;
cout << "\n本轮总结：\n";
cout << "参赛队编号：" << teamA << " 和 " << teamB << '\n';
cout << "Tristan 发送：" << tristanCode << '\n';
cout << "Isolde 回复：" << isoldeBit << '\n';
cout << "按这个回复，Tristan 判断赢家编号是：" << guessedWinner << "\n\n";
if (isoldeBit - '0' == correctBit)
{
cout << "你的回复是正确的。真实赢家确实是编号：" << winner << '\n';
}
else
{
cout << "你的回复不对。\n";
cout << "真实赢家是编号：" << winner << '\n';
cout << "所以第" << position + 1 << "位的正确回复应为：" << correctBit << '\n';
}
return 0;
}