Vous pouvez retrouver cette question au format pdf.

Question du jeudi #14 : Alice et Bob jouent à un jeu : Bob pense à un polynôme P à coefficients entiers positifs et Alice doit le deviner. À chaque tour, Alice demande la valeur de P en un nombre entier, et Bob la lui donne. En combien de tours Alice pourra-t-elle deviner P ?
(Précisons qu'Alice sait que les coefficients de P sont des entiers positifs, mais qu'elle n'en sait pas plus. En particulier, elle n'a aucune information sur son degré.)

Alice peut déterminer le polynôme avec seulement deux questions.

Pour cela, remarquons que si $P = \sum_{k=0}^d a_k X^k$, avec $a_k \in \mathbb N$ et qu'un entier $n$ est strictement plus grand que tous les $a_k$, la donnée de $P(n)$ détermine le polynôme $P$ :
\[P(n) = \sum_{k=0}^d a_k n^k\]
et les $a_k$ sont simplement les « chiffres » de l'écriture de $P(n)$ en base $n$.

Ainsi, Alice peut poser la première question « Combien vaut $P(1)$ ? » La réponse de Bob est $P(1) = \sum_{k=0}^d a_k$, qui est évidemment plus grand (au sens large) que les coefficients $a_k$.

Alice n'a alors plus qu'à prendre n'importe quel entier $n > P(1)$ et à demander la valeur de $P(n)$.