Trois entiers naturels et un tableau noir — Les-mathematiques.net The most powerful custom community solution in the world

Trois entiers naturels et un tableau noir

Modifié (27 Mar) dans Combinatoire et Graphes
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...
  • 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.
  • 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 :
  • Modifié (27 Mar)
    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.
  • Modifié (8 Apr)
    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 :smile:
  • @Pierre, juste pour noter que tu n'a pas étudié le cas (0, 2m, 2n +1).
  • @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.
Success message!