# Solution Shortlist problem of Combinatorics in IMO 2016 (Solution Problem 1)

Problem combinatoric 1 :

The minimum number of guesses is 2 if n = 2k and 1 if $\neq 2k$.

Solution 1.

Let X be the binary string chosen by the leader and let X’ be the binary string of length n every digit of which is different from that of X. The strings written by the deputy leader are the same as those in the case when the leader’s string is X’ and k is changed to n – k. In view of this, we may assume $k\geqslant \frac{n}{2}$. Also, for the particular case $k=\frac{n}{2}$, this argument shows that the strings X and X’ cannot be distinguished, and hence in that case the contestant has to guess at least twice.

It remains to show that the number of guesses claimed suffices. Consider any string Y which differs from X in m digits where 0 < m < 2k. Without loss of generality, assume the first m digits of X and Y are distinct. Let Z be the binary string obtained from X by changing its first k digits. Then Z is written by the deputy leader. Note that Z differs from Y by |m – k| digits where |m – k| < k since 0 < m < 2k. From this observation, the contestant must know that Y is not the desired string.

As we have assumed $k\geqslant \frac{n}{2}$, when n < 2k, every string $Y\neq X$ differs from X in fewer than 2k digits. When n = 2k, every string except X and X’ differs from X in fewer than 2k digits. Hence, the answer is as claimed.

Solution 2

Firstly, assume $n\neq 2k$. Without loss of generality suppose the first digit of the leader’s string is 1. Then among the $\begin{pmatrix}n\\k\end{pmatrix}$ strings written by the deputy leader, $\begin{pmatrix}n-1\\k\end{pmatrix}$ will begin with 1 and $\begin{pmatrix}n-1\\k-1\end{pmatrix}$ will begin with 0. Since $n\neq 2k$, we have $k+(k-1)\neq n-1$ and so $\begin{pmatrix}n-1\\k\end{pmatrix}\neq \begin{pmatrix}n-1\\k-1\end{pmatrix}$. Thus, by counting the number of strings written by the deputy leader that start with 0 and 1, the contestant can tell the first digit of the leader’s string. The same can be done on the other digits, so 1 guess suffices when $n\neq 2k$.

Secondly, for the case n = 2 and k = 1, the answer is clearly 2. For the remaining cases where n = 2k > 2, the deputy leader would write down the same strings if the leader’s string X is replaced by X’ obtained by changing each digit of X. This shows at least 2 guesses are needed. We shall show that 2 guesses suffice in this case. Suppose the first two digits of the leader’s string are the same. Then among the strings written by the deputy leader, the prefaces 01 and 10 will occur $\begin{pmatrix}2k-2\\k-1\end{pmatrix}$ times each, while the prefaces 00 and 11 will occur $\begin{pmatrix}2k-2\\k\end{pmatrix}$ times each. The two numbers are interchanged if the first two digits of the leader’s string are different. Since $\begin{pmatrix}2k-2\\k-1\end{pmatrix}\neq \begin{pmatrix}2k-2\\k\end{pmatrix}$, the contestant can tell whether the first two digits of the leader’s string are the same or not. He can work out the relation of the first digit and the other digits in the same way and reduce the leader’s string to only 2 possibilities. The proof is complete.