Trois entiers naturels et un tableau noir

yan2 · March 2022

Bonjour,

le problème suivant me résiste, j'aimerais bien avoir des idées de résolution. Une variante de cet exercice a été proposée à la 53ème Olympiade de mathématiques en Pologne (année 2002, problème 3).

Trois entiers naturels $a,b$ et $c$ sont écrits sur un tableau noir. On choisit, au hasard, deux d'entre eux, disons $a$ et $b$, on les efface et on les remplace par $a+b$ et $\vert a-b\vert$, l'entier $c$ reste inchangé et est toujours écrit au tableau. On répète ces transformations plusieurs fois. Pour quels triplets $(a,b,c)$ d'entiers naturels choisis au départ, peut-on arriver au triplet $(2022,0,0)$ après un certain nombre de ces transformations.

Dom · March 2022

Idée j’imagine déjà explorée…

On part de (2022,0,0) et on essaye de décrire les triplets antécédents avec les transformations décrites.

Peut-être seulement quand on manipule les deux premiers d’abord.

yan2 · March 2022

Il est clair qu'en partant de $(1011,1011,0)$ on arrive, dès la première transformation, à $(2022,0,0)$. Mais la question c'est de trouver tous les triplets $(a,b,c)$ qui permettent d'arriver à $(2022,0,0)$.

JLapin · March 2022

Dans ce cas, ce n'est pas "au hasard" que l'on choisit les deux entiers...

zeitnot · March 2022

La question est "peut-on". Donc si on choisit au hasard avec la proposition de yan2, on peut tout à fait arriver au triplet escompté dès la première transformation, avec une probabilité de 1/3.

Dom · March 2022

Je crois que le « au hasard » est fait pour romancer l’exercice, c’est presqu’une figure de style.

Les matheux (tous ?) n’aiment pas ça, mais c’est comme ça.

Laissons cet écueil de côté.

yan2 · March 2022

L'énoncé original du problème :

Image: https://les-mathematiques.net/vanilla/uploads/editor/t8/2yffpj57g0xx.png

JLapin · March 2022

Rare problème sans solution sur AOPS

https://artofproblemsolving.com/community/c6h65229p386508

raoul.S · March 2022

Je crois bien que les uniques triplets qui permettent d'aboutir à (2022,0,0) sont (1011,0,0) et (1011,1011,0) à permutation près des composantes.

En effet les uniques triplets qui aboutissent en une étape à (2022,0,0) sont (2022,0,0) lui-même et (1011,1011,0). Et le seul triplet qui aboutit à (1011,1011,0) en une seule étape est (1011,0,0) et (1011,0,0) n'a pas de triplet qui le précède.

PierreB · March 2022

Par contre, concernant le problème polonais, tout triplet $(a,b,c)$ peut se transformer en $(x,0,0)$ (je considère par ailleurs que la position du $x$ est sans importance) en une suite finie d'opérations.

On note tout d'abord que l'on peut facilement transformer $(a,b,c)$ en $(2a,2b,c)$ en deux opérations.

De plus, toute suite finie d'opérations qui transforme $(a,b,c)$ en $(x,0,0)$, transforme $(da,db,dc)$ en $(dx,0,0)$, et réciproquement.

On prouve alors le résultat par récurrence sur $s=a+b+c$.

- Si $s = 0$, c'est que $a=b=c$ et il n'y a rien à faire.

De même si $s=1$, c'est qu'à l'ordre près, on a $a=b=0$ et $c=1$ et il n'y a toujours rien à faire.

- Si le résultat est supposé vrai pour tout $s'$ vérifiant $s'< s$ alors :

a) Si l'un des nombres $a$, $b$, $c$ est pair et non nul, par exemple $a=2m$ avec $m>0$, on passe de $(2m,b,c)$ à $(2m,2b,2c)$. Mais $m+b+c < 2m + b+c = s$ et, d'après l'hypothèse de récurrence, il existe une suite finie d'opérations qui transforme $(m,b,c)$ en $(x,0,0)$. La remarque ci-dessus assure alors que l'on peut transformer $(2m,2b,2c)$ en $(2x,0,0)$, ce qui conclut dans ce cas.

b) Si le seul nombre pair parmi $a$, $b$ et $c$ est $0$, par exemple $a=0$. On a donc $b=2p+1$ et $q=2q+1$, où l'on peut supposer que $p \geq q$. On transforme alors $(0,2p+1,2q+1)$ en $(0,2p-2q,2p+2q+2)$. Or $0+(p-q)+(p+q+1) = 2p+1 < 0+(2p+1)+(2q+1) = s$ donc, d'après l'hypothèse de récurrence, il existe une suite finie d'opérations qui transforme $(0,p-q,p+q+1)$ en $(x,0,0)$. La remarque ci-dessus assure alors que l'on peut transformer $(0,2(p-q),2(p+q+1))$ en $(2x,0,0)$, ce qui conclut dans ce cas.

c) Les nombres $a$, $b$ et $c$ sont tous impairs. Le principe des tiroirs assure que deux, disons $a$ et $b$, ont le même reste modulo $4$. On pose donc $a=4p+r$, $b=4q+r$, avec $r \in \{1,3\}$ et $p \geq q$. On transforme alors $(4p+r,4q+r,c)$ en $(4(p-q), 4(p+q)+2r,c)$, puis en $(4(p-q), 2(4(p+q)+2r),2c)$, en $(4(p-q), 4(4(p+q)+2r),4c)$, puis en $(8(p-q), 4(4(p+q)+2r),8c)$. Comme ci-dessus, il suffit de prouver l'existence d'une suite finie d'opérations à partir de $(p-q, 2(p+q)+r,c)$. Mais, on a $(p-q)+(2(p+q)+r)+c < (4p+r)+(4q+r)+c =s$, et l'hypothèse de récurrence assure la conclusion dans ce dernier cas.

Pierre.