Shortlist 2021, N4¶
Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : non indiqué
Concepts : Congruences, théorèmes de Fermat et d'Euler · Divisibilité, PGCD et algorithme d'Euclide
Solution officielle : Shortlist officielle 2021 (avec solutions), p. 72 (page 72 du PDF)
Énoncé¶
Alice is given a rational number \(r > 1\) and a line with two points \(B \neq R\), where point \(R\) contains a red bead and point \(B\) contains a blue bead. Alice plays a solitaire game by performing a sequence of moves. In every move, she chooses a (not necessarily positive) integer \(k\), and a bead to move. If that bead is placed at point \(X\), and the other bead is placed at \(Y\), then Alice moves the chosen bead to point \(X'\) with \(\overrightarrow{YX'} = r^k \overrightarrow{YX}\).
Alice's goal is to move the red bead to the point \(B\). Find all rational numbers \(r > 1\) such that Alice can reach her goal in at most \(2021\) moves.
Indices : les idées clés
- Normaliser le jeu : avec \(R = 0\) et \(B = 1\), la distance entre les perles est toujours une puissance \(r^\ell\) ; on peut supposer que Alice alterne les perles, et le problème se ramène à l'équation \(\sum_{i=1}^{n} r^{\beta_i} = \sum_{i=1}^{n-1} r^{\gamma_i}\) avec \(n = 1011\).
- Congruences : avec \(r = a/b\), on chasse les dénominateurs et on réduit modulo \(a - b\) puis modulo \(a + b\).
- PGCD : \(\gcd(a - b, b) = \gcd(a + b, b) = 1\) donne \(a - b = 1\) et \(a + b \leq 2n - 1\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2021 (une solution et deux remarques).
Réponse : tous les \(r = \dfrac{b+1}{b}\) avec \(b = 1, 2, \ldots, 1010\).
Solution¶
Notons \(\mathcal{R}\) et \(\mathcal{B}\) les perles rouge et bleue. Munissons la droite d'un repère et identifions chaque point à son abscisse, de sorte que \(R = 0\) et \(B = 1\). Au cours du jeu, l'abscisse de \(\mathcal{R}\) reste toujours inférieure à celle de \(\mathcal{B}\) (car \(r^k > 0\)). De plus, la distance entre les perles est toujours de la forme \(r^\ell\) avec \(\ell \in \mathbb{Z}\), car elle est seulement multipliée par des nombres de cette forme. Notons \(d_m = r^{\alpha_m}\) la distance après le \(m\)-ième coup, \(m = 0, 1, 2, \ldots\) (après le coup « numéro \(0\) » on a la position initiale, donc \(\alpha_0 = 0\)).
Si une même perle est déplacée lors de deux coups consécutifs, Alice pourrait les remplacer par un seul coup (qui fait passer la distance directement de \(d_i\) à \(d_{i+2}\)) ayant le même effet. Donc, si Alice peut atteindre son but, elle peut l'atteindre en au plus autant de coups en alternant les déplacements de \(\mathcal{B}\) et \(\mathcal{R}\). Dans la suite, on suppose qu'Alice alterne et que \(\mathcal{R}\) est déplacée \(t\) fois en tout.
Si \(\mathcal{R}\) est déplacée au \(m\)-ième coup, son abscisse augmente de \(d_{m-1} - d_m\) (elle passe de \(Y - d_{m-1}\) à \(Y - d_m\), où \(Y\) est l'abscisse de \(\mathcal{B}\)). L'accroissement total de l'abscisse de \(\mathcal{R}\), qui doit valoir \(1\), est donc égal à
selon que \(\mathcal{R}\) ou \(\mathcal{B}\) est déplacée au premier coup. Dans le premier cas, il faut \(2t - 1 \leq 2021\), soit \(t \leq 1011\) ; dans le second, \(2t \leq 2021\), soit \(t \leq 1010\). Dans les deux cas, on aboutit (en écrivant \(1 = r^0\)) à une équation
pour un certain \(n \leq 1011\). Ainsi, si Alice peut atteindre son but, cette équation a une solution pour \(n = 1011\) (on peut ajouter des termes égaux aux deux membres pour augmenter \(n\)).
Réciproquement, si (1) a une solution pour \(n = 1011\), Alice peut composer une suite de distances \(d_0, d_1, d_2, \ldots, d_{2021}\) correspondante, puis la réaliser par une suite de coups. Le problème se ramène donc à la résolubilité de (1) pour \(n = 1011\).
Supposons que, pour un certain rationnel \(r\), l'équation (1) ait une solution. Écrivons \(r = a/b\) sous forme irréductible. En remplaçant dans (1), en multipliant par le dénominateur commun et en regroupant tous les termes à gauche, on obtient
pour un certain \(N \geq 0\) (les \(n\) termes de gauche de (1) portant le signe \(-\) et les \(n - 1\) termes de droite le signe \(+\)). On suppose qu'il existe des indices \(j_-\) et \(j_+\) tels que \(\mu_{j_-} = 0\) et \(\mu_{j_+} = N\).
En réduisant (2) modulo \(a - b\) (de sorte que \(a \equiv b\)), on obtient
Comme \(\gcd(a - b, b) = 1\), ce n'est possible que si \(a - b = 1\).
En réduisant (2) modulo \(a + b\) (de sorte que \(a \equiv -b\)), on obtient
pour un certain entier \(S\) impair (donc non nul), somme de \(2n - 1\) termes \(\pm 1\), avec \(|S| \leq 2n - 1\). Comme \(\gcd(a + b, b) = 1\), ce n'est possible que si \(a + b \mid S\). Donc \(a + b \leq 2n - 1\), et, comme \(a + b = 2b + 1\), on obtient \(b = a - 1 \leq n - 1 = 1010\).
Nous avons montré que tout \(r\) convenable est de la forme annoncée. Il reste à montrer que, pour tout \(b = 1, 2, \ldots, 1010\) et \(a = b + 1\), Alice peut atteindre son but. Pour cela, on prend dans (1) \(n = a\), \(\beta_1 = \beta_2 = \cdots = \beta_a = 0\) et \(\gamma_1 = \gamma_2 = \cdots = \gamma_b = 1\) : en effet \(a \cdot 1 = b \cdot \frac{a}{b}\), et \(n = a \leq 1011\). \(\blacksquare\)
Remarques¶
Remarque 1. Au lieu de réduire modulo \(a + b\), on peut réduire modulo \(a\) et modulo \(b\). La première réduction montre que le nombre (compté avec les signes) de termes de (2) avec \(\mu_i = 0\) est divisible par \(a\), et la seconde que celui des termes avec \(\mu_i = N\) est divisible par \(b\). En fait \(N > 0\), sinon (2) serait une somme alternée d'un nombre impair de termes égaux, qui est non nulle. Donc tous ces termes ont des indices différents, et il y en a au moins \(a + b\).
Remarque 2 (polynôme de Laurent). On peut aussi étudier (1) via le polynôme de Laurent
Pour un entier \(d\) assez grand, \(P(x) = x^d L(x)\) est dans \(\mathbb{Z}[x]\), et
Si \(r = p/q\) avec des entiers \(p > q \geq 1\) convient, alors \(P(p/q) = L(p/q) = 0\). Comme \(P\) est à coefficients entiers,
En faisant \(x = 1\) dans (5), \((p - q) \mid P(1) = 1\), donc \(p = q + 1\). En faisant \(x = -1\), \((p + q) \mid P(-1)\), ce qui avec (4) donne \(p + q \leq 2021\), donc \(q \leq 1010\). Ainsi \(r = (q+1)/q\) avec \(1 \leq q \leq 1010\).