Shortlist 2012, C6¶
Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : non indiqué
Concepts : Jeux et stratégies gagnantes · Invariants et monovariants · Bijections et dénombrement
Solution officielle : Shortlist officielle 2012 (avec solutions), p. 26 (page 26 du PDF)
Problème 3 de l'OIM 2012
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2012, où il était le problème 3 (jour 1).
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Let \(k\) and \(n\) be fixed positive integers. In the liar's guessing game, Amy chooses integers \(x\) and \(N\) with \(1 \leq x \leq N\). She tells Ben what \(N\) is, but not what \(x\) is. Ben may then repeatedly ask Amy whether \(x \in S\) for arbitrary sets \(S\) of integers. Amy will always answer with yes or no, but she might lie. The only restriction is that she can lie at most \(k\) times in a row. After he has asked as many questions as he wants, Ben must specify a set of at most \(n\) positive integers. If \(x\) is in this set he wins; otherwise, he loses. Prove that:
a) If \(n \geq 2^k\) then Ben can always win.
b) For sufficiently large \(k\) there exist \(n \geq 1.99^k\) such that Ben cannot guarantee a win.
Indices : les idées clés
- Réponses incohérentes : une réponse est incohérente avec \(i\) si elle serait fausse pour \(x = i\) ; une réponse incohérente avec \(x\) est un mensonge.
- Stratégie de Ben (a) : tant que \(\lvert T \rvert > 2^k\), il exclut un élément en interrogeant sur \(2^k\) puis sur les \(k\) chiffres binaires de \(x\) : les \(k + 1\) réponses sont toutes incohérentes avec un même \(y\).
- Potentiel pour Amy (b) : \(\varphi = \sum_i \lambda^{m_i}\), où \(m_i\) compte les réponses consécutives incohérentes avec \(i\) ; en minimisant \(\varphi\), Amy garde \(\varphi < \lambda^{k+1}\), donc jamais plus de \(k\) réponses incohérentes de suite.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2012 (une solution et une remarque).
Solution¶
Considérons une réponse \(A \in \{\textit{oui}, \textit{non}\}\) à une question du type « \(x\) est-il dans l'ensemble \(S\) ? ». On dit que \(A\) est incohérente avec un nombre \(i\) si \(A = \textit{oui}\) et \(i \notin S\), ou si \(A = \textit{non}\) et \(i \in S\). Une réponse incohérente avec le nombre cible \(x\) est un mensonge.
a) Supposons que Ben ait déterminé un ensemble \(T\) de taille \(m\) contenant \(x\). C'est vrai au départ avec \(m = N\) et \(T = \{1, 2, \ldots, N\}\). Pour \(m > 2^k\), montrons comment Ben peut trouver un nombre \(y \in T\) différent de \(x\). En répétant cette étape, il peut réduire \(T\) à une taille \(2^k \leq n\), et donc gagner.
Comme seule la taille \(m > 2^k\) de \(T\) compte, supposons \(T = \{0, 1, \ldots, 2^k, \ldots, m - 1\}\). Ben commence par demander de façon répétée si \(x\) vaut \(2^k\). Si Amy répond non \(k + 1\) fois de suite, l'une de ces réponses est vraie, donc \(x \neq 2^k\). Sinon, Ben arrête de demander à propos de \(2^k\) à la première réponse oui. Il demande alors, pour chaque \(i = 1, \ldots, k\), si l'écriture binaire de \(x\) a un \(0\) en \(i\)-ème position. Quelles que soient les \(k\) réponses, elles sont toutes incohérentes avec un certain nombre \(y \in \{0, 1, \ldots, 2^k - 1\}\). La réponse oui précédente à propos de \(2^k\) est aussi incohérente avec \(y\). Donc \(y \neq x\) : sinon, les \(k + 1\) dernières réponses seraient toutes des mensonges, ce qui est impossible.
Dans tous les cas, Ben trouve un nombre de \(T\) différent de \(x\), ce qui prouve l'affirmation.
b) Montrons que si \(1 < \lambda < 2\) et \(n = \left\lfloor (2 - \lambda)\lambda^{k+1} \right\rfloor - 1\), alors Ben ne peut pas être sûr de gagner. Pour conclure, il suffit alors de prendre \(\lambda\) tel que \(1.99 < \lambda < 2\) et \(k\) assez grand pour que
Considérons la stratégie suivante pour Amy. Elle choisit d'abord \(N = n + 1\) et \(x \in \{1, 2, \ldots, n + 1\}\) arbitrairement. Après chacune de ses réponses, Amy détermine, pour chaque \(i = 1, 2, \ldots, n + 1\), le nombre \(m_i\) de réponses consécutives qu'elle a données jusque-là et qui sont incohérentes avec \(i\). Pour choisir sa prochaine réponse, elle utilise la quantité
Quelle que soit la question suivante de Ben, Amy choisit la réponse qui minimise \(\varphi\).
Montrons qu'avec cette stratégie, \(\varphi\) reste toujours inférieure à \(\lambda^{k+1}\). Par conséquent, aucun exposant \(m_i\) de \(\varphi\) ne dépassera jamais \(k\), donc Amy ne donnera jamais plus de \(k\) réponses consécutives incohérentes avec un même \(i\). C'est vrai en particulier pour le nombre cible \(x\), donc elle ne mentira jamais plus de \(k\) fois de suite. Sous réserve de cette affirmation, la stratégie d'Amy est donc légale. Comme elle ne dépend pas de \(x\), Ben ne peut rien en déduire sur \(x\), et il ne peut pas être sûr de gagner.
Il reste à montrer que \(\varphi < \lambda^{k+1}\) à tout moment. Au départ, tous les \(m_i\) sont nuls, donc la condition est vraie, grâce à \(1 < \lambda < 2\) et \(n = \left\lfloor (2 - \lambda)\lambda^{k+1} \right\rfloor - 1\). Supposons \(\varphi < \lambda^{k+1}\) à un moment donné, et que Ben vienne de demander si \(x \in S\). Selon qu'Amy répond oui ou non, la nouvelle valeur de \(\varphi\) devient
Comme Amy choisit l'option qui minimise \(\varphi\), la nouvelle valeur est \(\min(\varphi_1, \varphi_2)\). Or
Comme \(\varphi < \lambda^{k+1}\), les hypothèses \(\lambda < 2\) et \(n = \left\lfloor (2 - \lambda)\lambda^{k+1} \right\rfloor - 1\) donnent
L'affirmation suit, ce qui achève la solution. \(\blacksquare\)
Remarque¶
Pour \(k\) fixé, notons \(f(k)\) la plus petite valeur de \(n\) pour laquelle Ben peut être sûr de gagner. Le problème demande de prouver que, pour \(k\) grand,
Une recherche par ordinateur montre que \(f(k) = 2, 3, 4, 7, 11, 17\) pour \(k = 1, 2, 3, 4, 5, 6\).