一名IMO代表队的领队选择正整数 $n,k$（$n>k$），并告知了副领队和参赛者．然后，领队秘密地告诉副领队一个有 $n$ 个数码的二进制表示的数字串，于是，副领队写下与领队写的 $n$ 个数码的数字串恰有 $k$ 个数位上的数不同的所有 $n$ 个数码的二进制表示的数字串（若 $n=3,k=1$，且领队选了 $101$ 告诉了副领队，则副领队应该写出 $001,111,100$）．参赛者允许看副领队写的数字串，并去猜领队的数字串．求猜的次数的最小值（依赖于 $n,k$），保证得到正确的答案．
【难度】
【出处】
2016IMO Short List
【标注】
【答案】
设 $n=2k$ 时，猜的次数的最小值为 $2$；当 $n\neq 2k$ 时，猜的次数的最小值为 $1$．
设领队选的二进制的数字串为 $X$，$X'$ 是长度为 $n$ 的二进制的数字串，且其每个数位上的数均与 $X$ 不同．则副领队写的数字串在领队选的二进制的数字串为 $X$ 和 $X'$（将 $k$ 变为 $n-k$）时是相同的，鉴于此，假设 $k\geqslant\frac{n}{2}$．
特别地，若 $k=\frac{n}{2}$，则参赛者无法区分 $X,X'$．因此，参赛者至少要猜两次．
对于 $0<m<2k$，考虑任意的数字串 $Y$，使得 $Y$ 与 $X$ 恰有 $m$ 个数位上的数不同．不失一般性，假设 $X,Y$ 的前 $m$ 个数位上的数不同．
设 $Z$ 为一个二进制的数字串，且与 $X$ 恰有前 $k$ 个数位上的数不同．则 $Z$ 被副领队写了．由于 $Z$ 与 $Y$ 有 $|m-k|$ 个数位上的数不同，结合 $0<m<2k$，知 $|m-k|<k$．因此，参赛者知 $Y$ 不是领队写的数字串．
注意到，已经假设了 $k\geqslant \frac{n}{2}$．当 $n<2k$ 时，每个不同于 $X$ 的数字串 $Y$ 均与 $X$ 有少于 $2k$ 个数位上的数不同；当 $n=2k$ 时，除了 $X$ 和 $X'$，每个数字串均与 $X$ 有少于 $2k$ 个数位上的数不同．因此，当 $n=2k$ 时，猜的次数的最小值为 $2$；当 $n\neq 2k$ 时，猜的次数的最小值为 $1$
设领队选的二进制的数字串为 $X$，$X'$ 是长度为 $n$ 的二进制的数字串，且其每个数位上的数均与 $X$ 不同．则副领队写的数字串在领队选的二进制的数字串为 $X$ 和 $X'$（将 $k$ 变为 $n-k$）时是相同的，鉴于此，假设 $k\geqslant\frac{n}{2}$．
特别地，若 $k=\frac{n}{2}$，则参赛者无法区分 $X,X'$．因此，参赛者至少要猜两次．
对于 $0<m<2k$，考虑任意的数字串 $Y$，使得 $Y$ 与 $X$ 恰有 $m$ 个数位上的数不同．不失一般性，假设 $X,Y$ 的前 $m$ 个数位上的数不同．
设 $Z$ 为一个二进制的数字串，且与 $X$ 恰有前 $k$ 个数位上的数不同．则 $Z$ 被副领队写了．由于 $Z$ 与 $Y$ 有 $|m-k|$ 个数位上的数不同，结合 $0<m<2k$，知 $|m-k|<k$．因此，参赛者知 $Y$ 不是领队写的数字串．
注意到，已经假设了 $k\geqslant \frac{n}{2}$．当 $n<2k$ 时，每个不同于 $X$ 的数字串 $Y$ 均与 $X$ 有少于 $2k$ 个数位上的数不同；当 $n=2k$ 时，除了 $X$ 和 $X'$，每个数字串均与 $X$ 有少于 $2k$ 个数位上的数不同．因此，当 $n=2k$ 时，猜的次数的最小值为 $2$；当 $n\neq 2k$ 时，猜的次数的最小值为 $1$
【解析】
略
答案
解析
备注
