Shortlist 2013, N5

Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : Italy

Concepts : Jeux et stratégies gagnantes · Divisibilité, PGCD et algorithme d'Euclide · Principe extrémal

Solution officielle : Shortlist officielle 2013 (avec solutions), p. 58 (page 58 du PDF)

Énoncé

Fix an integer \(k \geq 2\). Two players, called Ana and Banana, play the following game of numbers: Initially, some integer \(n \geq k\) gets written on the blackboard. Then they take moves in turn, with Ana beginning. A player making a move erases the number \(m\) just written on the blackboard and replaces it by some number \(m'\) with \(k \leq m' < m\) that is coprime to \(m\). The first player who cannot move anymore loses.

An integer \(n \geq k\) is called good if Banana has a winning strategy when the initial number is \(n\), and bad otherwise.

Consider two integers \(n, n' \geq k\) with the property that each prime number \(p \leq k\) divides \(n\) if and only if it divides \(n'\). Prove that either both \(n\) and \(n'\) are good or both are bad.

Indices : les idées clés

• Analyse du jeu : \(n\) est mauvais si et seulement s'il existe un coup \(n \to m\) vers un bon \(m\) ; donc deux bons nombres ne sont jamais premiers entre eux, et \(k\) est bon.
• Trois lemmes (solution 1) : un multiple d'un bon nombre est bon ; si \(rs\) est mauvais, \(r^2 s\) aussi ; si \(n\) est mauvais et \(p > k\) premier, \(np\) est mauvais.
• Contre-exemple minimal : on se ramène à un couple \((c, d)\) avec \(c \mid d\) semblables, \(d\) minimal, et l'on retire un facteur premier de \(\frac{d}{c}\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2013 (deux solutions et quatre remarques).

Solution 1

Remarquons d'abord que le nombre écrit au tableau diminue à chaque coup ; la partie s'arrête donc après au plus \(n\) coups, et l'un des joueurs a toujours une stratégie gagnante. Donc, si un \(n \geq k\) est mauvais, Ana a une stratégie gagnante dans la partie de nombre initial \(n\).

Plus précisément, si \(n \geq k\) est tel qu'il existe un bon entier \(m\) avec \(n > m \geq k\) et \(\operatorname{pgcd}(m, n) = 1\), alors \(n\) est mauvais : Ana a la stratégie gagnante suivante pour le nombre initial \(n\) : elle joue d'abord \(m\), puis utilise la stratégie de Banana pour la partie de nombre initial \(m\).

Sinon, si un entier \(n \geq k\) est tel que tout entier \(m\) avec \(n > m \geq k\) et \(\operatorname{pgcd}(m, n) = 1\) est mauvais, alors \(n\) est bon. En effet, si Ana peut jouer un premier coup dans la partie de nombre initial \(n\), elle laisse une position où le joueur qui commence a une stratégie gagnante, et Banana peut donc la battre.

En particulier, deux bons nombres ont toujours un diviseur commun non trivial. De plus, \(k\) lui-même est bon.

Pour abréger, on dit que \(n \longrightarrow x\) est un coup si \(n\) et \(x\) sont deux entiers premiers entre eux avec \(n > x \geq k\).

Affirmation 1. Si \(n\) est bon et \(n'\) est un multiple de \(n\), alors \(n'\) est bon.

Preuve. Si \(n'\) était mauvais, il y aurait un coup \(n' \longrightarrow x\) avec \(x\) bon. Comme \(n'\) est multiple de \(n\), les deux bons nombres \(n\) et \(x\) seraient premiers entre eux, ce qui est absurde. \(\square\)

Affirmation 2. Si \(r\) et \(s\) sont deux entiers strictement positifs tels que \(rs \geq k\) soit mauvais, alors \(r^2 s\) est aussi mauvais.

Preuve. Comme \(rs\) est mauvais, il existe un coup \(rs \longrightarrow x\) avec \(x\) bon. Évidemment, \(x\) est aussi premier avec \(r^2 s\), et le coup \(r^2 s \longrightarrow x\) montre que \(r^2 s\) est mauvais. \(\square\)

Affirmation 3. Si \(p > k\) est premier et \(n \geq k\) est mauvais, alors \(np\) est aussi mauvais.

Preuve. Sinon, choisissons un contre-exemple avec \(n\) minimal. En particulier, \(np\) est bon. Comme \(n\) est mauvais, il existe un coup \(n \longrightarrow x\) avec \(x\) bon. Alors \(np \longrightarrow x\) ne peut pas être un coup valide, ce qui montre que \(x\) est divisible par \(p\). On écrit donc \(x = p^r y\), avec des entiers strictement positifs \(r\) et \(y\), ce dernier non divisible par \(p\).

Le cas \(y = 1\) est impossible, car on aurait alors \(x = p^r\), et le coup \(x \longrightarrow k\) montrerait que \(x\) est mauvais. Il existe donc une plus petite puissance \(y^\alpha\) de \(y\) au moins égale à \(k\). Comme les nombres \(np\) et \(y^\alpha\) sont premiers entre eux et que le premier est bon, le second est mauvais. De plus, la minimalité de \(\alpha\) donne \(y^\alpha < ky < py = \frac{x}{p^{r-1}} < \frac{n}{p^{r-1}}\). Donc \(p^{r-1} \cdot y^\alpha < n\), et tous les nombres \(y^\alpha, py^\alpha, \ldots, p^r \cdot y^\alpha = p(p^{r-1} \cdot y^\alpha)\) sont mauvais, par le choix minimal de \(n\). Mais alors, par l'affirmation 1, le diviseur \(x\) de \(p^r \cdot y^\alpha\) ne peut pas être bon, ce qui est une contradiction et prouve l'affirmation 3. \(\square\)

Déduisons maintenant l'énoncé de ces trois affirmations. On dit que deux entiers \(a, b \geq k\) sont semblables s'ils sont divisibles par les mêmes nombres premiers au plus égaux à \(k\). Il s'agit de prouver que si \(a\) et \(b\) sont semblables, ils sont tous deux bons ou tous deux mauvais. Comme dans ce cas le produit \(ab\) est semblable à \(a\) et à \(b\), il suffit de montrer que si \(c \geq k\) est semblable à l'un de ses multiples \(d\), alors \(c\) et \(d\) sont tous deux bons ou tous deux mauvais.

Supposons que ce soit faux en général, et choisissons un contre-exemple \((c_0, d_0)\) avec \(d_0\) minimal. Par l'affirmation 1, \(c_0\) est mauvais et \(d_0\) est bon. Évidemment, \(d_0 > c_0\), et le quotient \(\frac{d_0}{c_0}\) a un facteur premier \(p\), qui divise \(d_0\). Si \(p \leq k\), alors \(p\) divise aussi \(c_0\) par similitude, donc \(d_0\) est en fait divisible par \(p^2\). Par la contraposée de l'affirmation 2, \(\frac{d_0}{p}\) est bon. Comme \(c_0 \mid \frac{d_0}{p}\), le couple \(\left(c_0, \frac{d_0}{p}\right)\) contredit la minimalité de \(d_0\). Donc \(p > k\), mais on obtient alors la même contradiction en utilisant l'affirmation 3 au lieu de l'affirmation 2. Le problème est résolu. \(\blacksquare\)

Solution 2

On utilise la même analyse du jeu que dans les cinq premiers paragraphes de la solution 1. Un nombre premier \(p\) est dit petit si \(p \leq k\) et grand sinon. Deux entiers sont à nouveau dits semblables si leurs ensembles de petits facteurs premiers coïncident.

Affirmation 4. Pour tout entier \(b \geq k\) ayant un petit facteur premier, il existe un entier \(x\) semblable à \(b\) avec \(b \geq x \geq k\) et sans grand facteur premier.

Preuve. Si \(b\) n'a pas de grand facteur premier, on prend simplement \(x = b\). Sinon, soient \(p\) et \(q\) un petit et un grand facteur premier de \(b\). Soit \(a\) le produit de tous les petits facteurs premiers de \(b\), et \(n\) le plus petit entier positif ou nul tel que \(x = p^n a\) soit au moins égal à \(k\). Il suffit de montrer que \(b > x\). C'est clair si \(n = 0\) ; supposons donc \(n > 0\). On a alors \(x < pk\) par minimalité de \(n\), \(p \leq a\) car \(p\) divise \(a\) par construction, et \(k < q\). Donc \(x < aq\), et comme le membre de droite est un produit de facteurs premiers distincts de \(b\), cela implique bien \(x < b\). \(\square\)

Supposons maintenant qu'il existe un couple \((a, b)\) de nombres semblables avec \(a\) mauvais et \(b\) bon. Prenons un tel couple avec \(\max(a, b)\) minimal. Comme \(a\) est mauvais, il existe un coup \(a \longrightarrow r\) avec \(r\) bon. Comme \(k\) et \(r\) sont tous deux bons, ils ont un facteur premier commun, nécessairement petit. L'affirmation 4 s'applique donc à \(r\), et donne un entier \(r'\) semblable à \(r\), n'ayant que de petits facteurs premiers, avec \(r \geq r' \geq k\). Comme \(\max(r, r') = r < a \leq \max(a, b)\), le nombre \(r'\) est lui aussi bon. Soit \(p\) un facteur premier commun aux bons nombres \(r'\) et \(b\). Par construction de \(r'\), ce nombre premier est petit, et par similitude il divise donc \(a\) et \(r\), ce qui contredit le fait que \(a \longrightarrow r\) est un coup. Le problème est résolu. \(\blacksquare\)

Remarques

Remarque 1. Une fois l'affirmation 4 de la solution 2 obtenue, on peut continuer de diverses façons. Par exemple, on obtient directement le fait suivant, intéressant en lui-même.

Affirmation 5. Deux bons nombres ont toujours un petit facteur premier commun.

Preuve. Sinon, il existe un couple \((b, b')\) de bons nombres avec \(b' \geq b \geq k\) dont tous les facteurs premiers communs sont grands. Choisissons un tel couple avec \(b'\) minimal. Comme \(b\) et \(k\) sont bons, ils ont un facteur premier commun \(p\). Évidemment \(p\) est petit, donc il ne divise pas \(b'\), d'où \(b' > b\). L'affirmation 4 appliquée à \(b\) donne un entier \(x\) avec \(b \geq x \geq k\), semblable à \(b\) et sans grand diviseur premier. Par hypothèse, \(b'\) et \(x\) sont premiers entre eux, et comme \(b'\) est bon, \(x\) est mauvais. Il existe donc un coup \(x \longrightarrow b^*\) avec \(b^*\) bon. Mais tous les petits facteurs premiers de \(b\) apparaissent aussi dans \(x\), donc ne divisent pas \(b^*\). Le couple \((b^*, b)\) contredit alors la minimalité de \(b'\). \(\square\)

On termine alors facilement : supposons qu'il existe deux entiers semblables \(a\) et \(b\) avec \(a\) mauvais et \(b\) bon. Comme \(a\) est mauvais, il existe un coup \(a \longrightarrow b'\) avec \(b'\) bon. Par l'affirmation 5, un petit nombre premier \(p\) divise \(b\) et \(b'\). Par similitude de \(a\) et \(b\), \(p\) divise aussi \(a\), ce qui contredit le fait que \(a \longrightarrow b'\) est un coup valide.

Remarque 2. Il y a une infinité de bons nombres, par exemple tous les multiples de \(k\). La suite croissante \(b_0, b_1, \ldots\) de tous les bons nombres se construit par récurrence : on part de \(b_0 = k\) ; si \(b_n\) est défini, \(b_{n+1}\) est le plus petit nombre \(b > b_n\) qui n'est premier avec aucun de \(b_0, \ldots, b_n\). Cette construction permet de déterminer l'ensemble des bons nombres pour tout \(k\) donné, comme expliqué dans la remarque suivante. Il est déjà clair que si \(k = p^\alpha\) est une puissance d'un nombre premier, alors un nombre \(b \geq k\) est bon si et seulement s'il est divisible par \(p\).

Remarque 3. Soit \(P > 1\) le produit de tous les petits nombres premiers. Deux entiers \(a, b \geq k\) congrus modulo \(P\) sont semblables. Le mot infini \(W_k = (X_k, X_{k+1}, \ldots)\) défini par \(X_i = A\) si \(i\) est mauvais et \(X_i = B\) si \(i\) est bon, pour \(i \geq k\), est donc périodique, de période divisant \(P\). Comme le montre l'exemple des puissances de premiers, la vraie période peut être beaucoup plus petite que \(P\). Mais il y a aussi des cas où elle est assez grande ; par exemple, pour \(k = 15\), la suite des bons nombres commence par \(15, 18, 20, 24, 30, 36, 40, 42, 45\), et la période de \(W_{15}\) vaut \(30\).

Remarque 4. La proposition d'origine contenait deux questions sur ce jeu : (a) montrer que si deux nombres ont les mêmes facteurs premiers, ils sont tous deux bons ou tous deux mauvais, et (b) montrer que le mot \(W_k\) de la remarque précédente est périodique. Le comité pense que la version ci-dessus est un peu plus facile, bien qu'elle demande de prouver un résultat plus fort.