Aller au contenu

Shortlist 2025, A1

Domaine : Algèbre · Difficulté : ★☆☆☆☆ · Proposé par : Czech Republic

Concepts : Polynômes : racines, relations de Viète, factorisation · Invariants et monovariants

Solution officielle : Shortlist officielle 2025 (avec solutions), section A1 (livret PDF)

Énoncé

Quadratic solitaire is a single-player game. To start the game, the player chooses two distinct nonzero integers \(a\) and \(b\) and writes the equation \(x^2 + ax + b = 0\) on a blackboard. On each turn, if the equation currently written on the blackboard has two distinct nonzero integer solutions \(x = u\) and \(x = v\), then the player erases the equation and replaces it by one of the equations \(x^2 + ux + v = 0\) or \(x^2 + vx + u = 0\) of their choosing. Otherwise, the game ends.

Determine all initial choices of \(a\) and \(b\) such that quadratic solitaire can be played forever.

Indices : les idées clés
  • Relations de Viète : si \(x^2 + sx + t = 0\) a pour racines \(u, v\), alors \(s = -(u+v)\) et \(t = uv\).
  • Monovariant : \(|t|\) ne peut pas croître (solution 1), ou \(s^2 + t^2\) ne peut pas croître (solution 2), et décroît strictement sauf dans un cas très particulier.
  • Remonter le temps : l'équation \(x^2 + x - 2 = 0\) ne peut provenir que d'elle-même, donc il faut commencer avec elle.
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2025 (deux solutions et une remarque).

Réponse : le seul couple \((a,b)\) pour lequel on peut jouer indéfiniment est \((a,b) = (1,-2)\).

Solution 1

Soit \((a,b)\) un couple d'entiers non nuls distincts pour lequel le jeu peut durer indéfiniment, et fixons une suite de coups infinie. Considérons un coup où l'équation \(x^2 + sx + t = 0\) est remplacée par \(x^2 + ux + v = 0\).

Les relations de Viète donnent \(t = uv\). Comme \(u\) est un entier non nul, \(|t| = |u|\,|v| \geq |v|\), avec inégalité stricte dès que \(|u| \neq 1\). La quantité \(|v|\) (valeur absolue du terme constant) est un entier positif qui ne peut pas décroître indéfiniment (monovariant) : il n'y a donc qu'un nombre fini de coups avec \(|u| \neq 1\). Ainsi, si le jeu dure indéfiniment, on a à partir d'un certain moment \(|s| = |u| = 1\) à chaque coup. La relation \(s = -(u+v)\) conduit alors à trois cas :

  • si \(s = 1\) et \(u = 1\), alors \(v = -2\). L'équation \(x^2 + ux + v = x^2 + x - 2 = 0\) a pour solutions \(\{1, -2\}\), et à partir d'elle le joueur peut continuer indéfiniment (en réécrivant toujours \(x^2 + x - 2 = 0\)) ;
  • si \(s = -1\) et \(u = -1\), alors \(v = 2\). L'équation \(x^2 - x + 2 = 0\) n'a pas de solution entière, donc le jeu s'arrête ;
  • si \(\{s, u\} = \{1, -1\}\), alors \(v = 0\), ce qui est impossible.

En conclusion, la seule façon de jouer indéfiniment est de rencontrer l'équation \(x^2 + x - 2 = 0\) à un certain coup.

Réciproquement, si \(x^2 + x - 2 = 0\) est au tableau au début d'un coup (autre que le premier), l'équation écrite au coup précédent avait pour racines \(1\) et \(-2\), c'est-à-dire qu'elle était \((x-1)(x+2) = x^2 + x - 2 = 0\). Par conséquent, pour rencontrer l'équation \(x^2 + x - 2 = 0\), le joueur doit avoir commencé avec cette même équation, d'où \((a,b) = (1,-2)\). \(\blacksquare\)

Solution 2

On utilise un autre monovariant. Comme dans la solution 1, considérons un coup où \(x^2 + sx + t = 0\) est remplacée par \(x^2 + ux + v = 0\).

Affirmation 1. \(uv \neq -1\).

Preuve. Si \(uv = -1\), alors \(\{u, v\} = \{1, -1\}\) puisque \(u\) et \(v\) sont entiers. Au coup suivant, les équations possibles seraient \(x^2 + x - 1 = 0\) et \(x^2 - x + 1 = 0\). Aucune n'a de solution entière, donc le jeu se serait arrêté. \(\square\)

Affirmation 2. \(s^2 + t^2 \geq u^2 + v^2\), avec égalité si et seulement si \(uv = -2\).

Preuve. Comme \(u\) et \(v\) sont les deux solutions distinctes de \(x^2 + sx + t = 0\), les relations de Viète donnent \(s = -(u+v)\) et \(t = uv\). Il s'agit donc de montrer que

\[(u+v)^2 + u^2v^2 \geq u^2 + v^2,\]

ce qui équivaut à \(u^2v^2 + 2uv \geq 0\), soit \((uv + 1)^2 \geq 1\). C'est vrai car \(uv + 1\) est un entier non nul d'après l'affirmation 1. L'égalité a lieu si et seulement si \(uv \in \{0, -2\}\) ; le cas \(uv = 0\) est impossible car \(u, v\) sont non nuls. \(\square\)

Comme \(u^2 + v^2\) ne peut pas décroître en dessous de zéro, il n'y a qu'un nombre fini de coups avec \(uv \neq -2\). Il reste à étudier le cas \(uv = -2\).

Si \(uv = -2\), alors \(\{u, v\} = \{1, -2\}\) ou \(\{u, v\} = \{-1, 2\}\). On obtient quatre équations possibles pour le coup suivant :

  • \(x^2 + x - 2 = 0\) : deux solutions entières ;
  • \(x^2 - 2x + 1 = 0\) : une seule solution entière (double) ;
  • \(x^2 - x + 2 = 0\) : pas de solution entière ;
  • \(x^2 + 2x - 1 = 0\) : pas de solution entière.

Seule la première permet de continuer. On conclut alors comme dans la solution 1 : le jeu infini doit passer par \(x^2 + x - 2 = 0\), qui ne peut provenir que d'elle-même, d'où \((a,b) = (1,-2)\). \(\blacksquare\)

Remarques

Remarque 1. Certains problèmes ressemblent superficiellement à celui-ci (par exemple EGMO 2024, problème 1, ou China Girls Math Olympiad 2020, problème 5 : trouver toutes les suites réelles \((b_n)\), \((c_n)\) avec \(b_n \leq c_n\) et \(\{b_{n+1}, c_{n+1}\}\) les deux solutions de \(x^2 + b_nx + c_n = 0\) pour tout \(n \geq 1\)). Les problèmes sont néanmoins différents. Le fait que \(x^2 + x - 2\) soit le seul polynôme unitaire du second degré non trivial dont les racines sont ses coefficients est aussi un problème connu, mais il n'intervient que dans une vérification directe à la fin de la solution.