Shortlist 2016, C1¶
Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : non indiqué
Concepts : Bijections et dénombrement
Solution officielle : Shortlist officielle 2016 (avec solutions), p. 29 (page 32 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
The leader of an IMO team chooses positive integers \(n\) and \(k\) with \(n > k\), and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an \(n\)-digit binary string, and the deputy leader writes down all \(n\)-digit binary strings which differ from the leader's in exactly \(k\) positions. (For example, if \(n = 3\) and \(k = 1\), and if the leader chooses \(101\), the deputy leader would write down \(001\), \(111\) and \(100\).) The contestant is allowed to look at the strings written by the deputy leader and guess the leader's string. What is the minimum number of guesses (in terms of \(n\) and \(k\)) needed to guarantee the correct answer?
Indices : les idées clés
- Symétrie par complémentation : remplacer la chaîne \(X\) par sa complémentaire \(X'\) et \(k\) par \(n - k\) ne change pas la liste écrite ; d'où \(k \geq \frac{n}{2}\) sans perte de généralité, et l'impossibilité de distinguer \(X\) de \(X'\) quand \(n = 2k\).
- Éliminer les candidats (solution 1) : une chaîne \(Y\) à distance \(m\) de \(X\) avec \(0 < m < 2k\) est exclue par une chaîne écrite située à distance \(|m - k| \neq k\) de \(Y\).
- Dénombrement (solution 2) : compter les chaînes écrites commençant par \(0\) ou par \(1\) fait apparaître \(\binom{n-1}{k}\) et \(\binom{n-1}{k-1}\), différents si \(n \neq 2k\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2016 (deux solutions).
Réponse. Le nombre minimal d'essais est \(2\) si \(n = 2k\), et \(1\) si \(n \neq 2k\).
Solution 1¶
Soit \(X\) la chaîne choisie par le chef d'équipe, et \(X'\) la chaîne de longueur \(n\) dont chaque chiffre diffère de celui de \(X\) (sa complémentaire). Les chaînes écrites par l'adjoint sont exactement celles qu'il écrirait si la chaîne du chef était \(X'\) et si \(k\) était remplacé par \(n - k\) (différer de \(X\) en \(k\) positions, c'est différer de \(X'\) en \(n - k\) positions). On peut donc supposer \(k \geq \frac{n}{2}\). De plus, dans le cas particulier \(k = \frac{n}{2}\), cet argument montre que \(X\) et \(X'\) ne peuvent pas être distinguées : le candidat doit alors faire au moins deux essais.
Montrons que le nombre d'essais annoncé suffit. Soit \(Y\) une chaîne qui diffère de \(X\) en \(m\) positions, avec \(0 < m < 2k\). Sans perte de généralité, les \(m\) premiers chiffres de \(X\) et \(Y\) sont différents. Soit \(Z\) la chaîne obtenue à partir de \(X\) en changeant ses \(k\) premiers chiffres. Alors \(Z\) figure dans la liste de l'adjoint. Or \(Z\) diffère de \(Y\) en \(|m - k|\) positions, et \(|m - k| < k\) car \(0 < m < 2k\). Si \(Y\) était la chaîne du chef, toutes les chaînes écrites différeraient de \(Y\) en exactement \(k\) positions ; le candidat sait donc que \(Y\) n'est pas la bonne chaîne.
Comme \(k \geq \frac{n}{2}\) :
- si \(n < 2k\), toute chaîne \(Y \neq X\) diffère de \(X\) en moins de \(2k\) positions, donc elle est éliminée : un seul essai suffit ;
- si \(n = 2k\), toute chaîne autre que \(X\) et \(X'\) diffère de \(X\) en moins de \(2k\) positions, donc il reste au plus deux candidats : deux essais suffisent.
La réponse est donc celle annoncée. \(\blacksquare\)
Solution 2¶
Cas \(n \neq 2k\). Sans perte de généralité, le premier chiffre de la chaîne du chef est \(1\). Parmi les \(\binom{n}{k}\) chaînes écrites par l'adjoint, \(\binom{n-1}{k}\) commencent par \(1\) (le premier chiffre n'est pas modifié) et \(\binom{n-1}{k-1}\) commencent par \(0\). Comme \(n \neq 2k\), on a \(k + (k - 1) \neq n - 1\), donc
Ainsi, en comptant les chaînes écrites qui commencent par \(0\) et par \(1\), le candidat détermine le premier chiffre de la chaîne du chef (c'est celui dont l'effectif est \(\binom{n-1}{k}\), les deux effectifs étant connus de lui). On procède de même pour chaque chiffre : un seul essai suffit.
Cas \(n = 2k\). Pour \(n = 2\) et \(k = 1\), la réponse est clairement \(2\). Dans les autres cas, \(n = 2k > 2\), l'adjoint écrirait les mêmes chaînes si la chaîne \(X\) du chef était remplacée par sa complémentaire \(X'\) : il faut donc au moins \(2\) essais. Montrons que \(2\) essais suffisent. Supposons que les deux premiers chiffres de la chaîne du chef soient égaux. Alors, parmi les chaînes écrites, les préfixes \(01\) et \(10\) apparaissent chacun \(\binom{2k-2}{k-1}\) fois, tandis que les préfixes \(00\) et \(11\) apparaissent chacun \(\binom{2k-2}{k}\) fois. Ces deux nombres sont échangés si les deux premiers chiffres du chef sont différents. Comme \(\binom{2k-2}{k-1} \neq \binom{2k-2}{k}\), le candidat sait si les deux premiers chiffres sont égaux ou non. Il détermine de même la relation (égal ou différent) entre le premier chiffre et chacun des autres, ce qui réduit la chaîne du chef à \(2\) possibilités. \(\blacksquare\)