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.
Trois entiers naturels et un tableau noir
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.
Réponses
-
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. -
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)$.
-
Dans ce cas, ce n'est pas "au hasard" que l'on choisit les deux entiers...
-
Karl Tremblay 1976-2023, je t'appréciais tellement.
-
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é.
-
L'énoncé original du problème :
-
-
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. -
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.
-
Merci Pierre
-
@babsgueye juste pour noter que tu n'as pas bien lu la preuve de PierreB... ton cas est traité en a).
-
Ok, t'as raison. Merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres