Le problème du professeur Ducci
2 participants
Page 1 sur 1
Le problème du professeur Ducci
1) On choisit 4 entiers naturels quelconques `a_1`, `a_2`, `a_3` et `a_4`.
Ensuite on calcule les valeurs absolues des différences entre deux nombres successifs : `b_1=│a_1-a_2│`, `b_2=│a_2-a_3│`, `b_3=│a_3-a_4│` et `b_4=│a_4-a_1│`.
On obtient donc 4 nouveaux entiers naturels. Si l'on répète ce procédé assez souvent, on obtient 4 zéros. Démontrez cette affirmation !
2) Cela est-il vrai également si l'on prend seulement 3 entiers ?
Ensuite on calcule les valeurs absolues des différences entre deux nombres successifs : `b_1=│a_1-a_2│`, `b_2=│a_2-a_3│`, `b_3=│a_3-a_4│` et `b_4=│a_4-a_1│`.
On obtient donc 4 nouveaux entiers naturels. Si l'on répète ce procédé assez souvent, on obtient 4 zéros. Démontrez cette affirmation !
2) Cela est-il vrai également si l'on prend seulement 3 entiers ?
Dernière édition par G. Lorang le Jeu 16 Juin - 16:10, édité 2 fois
2)
Non, ceci n' est plus vrai pour 3 entiers.
Si on prend les trois entiers 2, 3 et 5, alors on reçoit ensuite les entiers 1, 2 et 3 avant d' obtenir 1, 1 et 2. Puis on aura 0, 1 et 1.
Or on ne peut pas obtenir la constellation 0, 0 et 0 avec ce triplet, car seul le zéro peut changer de place!
Si on prend les trois entiers 2, 3 et 5, alors on reçoit ensuite les entiers 1, 2 et 3 avant d' obtenir 1, 1 et 2. Puis on aura 0, 1 et 1.
Or on ne peut pas obtenir la constellation 0, 0 et 0 avec ce triplet, car seul le zéro peut changer de place!
carole- Expert
- Messages : 181
Date d'inscription : 11/05/2010
Age : 31
1)
D' abord il peut être utile de remarquer que si on est en présence de 4 entiers tous multiples d' un même naturel, on peut diviser les nombres par ce naturel pour simplifier nos calculs. On obtiendrait toujours des différences qui sont également multiples de ce naturel.
Si on veut obtenir un quadruple de la forme `(0;0;0;0)`, il faut essayer d' obtenir un quadruple de la forme `(a;a;a;a)` car seul avec un tel quadruple on peut obtenir cette combinaison. En effet: `a-a=0`.
Or obtient un tel quadruple à partir de ces formes (entre autre):
`(0;0;0;a)=>(0;0;a;a)=>(0;a;0;a)
`(a;0;a;2a)
`(a;b;a;b)=> (a-b:a-b:a-b:a-b)
`(a;a;a;b)
`(a;a;b;b)
`(a;b;a;c)
`(a;a;b;c)=>(0;a-b;b-c;a-c)=(0;a-b;b-c;(a-b)+(b-c))=>(a-b;a-c;a-b;a-c)
(On peut faire tourner les éléments en respectant l' ordre sans changer les calculs)
Si on est en présence d' une suite arithmétique, on obtient facilement une de ces combinaisons:
`(a;a+r;a+2r;a+3r)=>(r;r;r;3r)=>(1;1;1;3)=>(0;0;2;2)=>(0;0;0;0)
Il suffit donc qu' on obtient quelque part un quadruple dont 2 éléments sont égaux afin d' obtenir le quadruple `(0;0;0;0)`!
Or, en calculant assez longtemps on obtient un tel quadruple, mais on devra encore le démontrer...
Si on veut obtenir un quadruple de la forme `(0;0;0;0)`, il faut essayer d' obtenir un quadruple de la forme `(a;a;a;a)` car seul avec un tel quadruple on peut obtenir cette combinaison. En effet: `a-a=0`.
Or obtient un tel quadruple à partir de ces formes (entre autre):
`(0;0;0;a)=>(0;0;a;a)=>(0;a;0;a)
`(a;0;a;2a)
`(a;b;a;b)=> (a-b:a-b:a-b:a-b)
`(a;a;a;b)
`(a;a;b;b)
`(a;b;a;c)
`(a;a;b;c)=>(0;a-b;b-c;a-c)=(0;a-b;b-c;(a-b)+(b-c))=>(a-b;a-c;a-b;a-c)
(On peut faire tourner les éléments en respectant l' ordre sans changer les calculs)
Si on est en présence d' une suite arithmétique, on obtient facilement une de ces combinaisons:
`(a;a+r;a+2r;a+3r)=>(r;r;r;3r)=>(1;1;1;3)=>(0;0;2;2)=>(0;0;0;0)
Il suffit donc qu' on obtient quelque part un quadruple dont 2 éléments sont égaux afin d' obtenir le quadruple `(0;0;0;0)`!
Or, en calculant assez longtemps on obtient un tel quadruple, mais on devra encore le démontrer...
Dernière édition par carole le Mer 15 Juin - 19:14, édité 1 fois
carole- Expert
- Messages : 181
Date d'inscription : 11/05/2010
Age : 31
Début très bon !
Tu dois exploiter ta 1re idée ...
Montre que tu obtiens forcément une suite avec 4 entiers pairs après quelques étapes !
Cordialement, G. Lorang
Montre que tu obtiens forcément une suite avec 4 entiers pairs après quelques étapes !
Cordialement, G. Lorang
Re: Le problème du professeur Ducci
`a_1<a_2<a_3<a_4`
Si l' ordre est un des suivants `(a_1;a_3;a_2;a_4)` ou `(a_1;a_4;a_2;a_3)`, alors après la deuxième étape on reçoit un des couples mentionnés en haut:
1er cas:
`b_1=a_3-a_1
`b_2=a_3-a_2
`b_3=a_4-a_2
`b_4=a_4-a_1
`c_1=a_2-a_1
`c_2=a_4-a_3
`c_3=a_2-a_1=c_1
`c_4=a_4-a_3=c_2
2e cas:
`b_1=a_4-a_1
`b_2=a_4-a_2
`b_3=a_3-a_2
`b_4=a_3-a_1
`c_1=a_2-a_1
`c_2=a_4-a_3
`c_3=a_2-a_1=c_1
`c_4=a_4-a_3=c_2
Si on la forme suivante: `(a_1;a_2;a_4;a_3)`, alors
`b_1=a_2-a_1
`b_2=a_4-a_2
`b_3=a_4-a_3
`b_4=a_3-a_1
`c_1=a_4+a_1-2a_2
`c_2=a_3-a_2
`c_3=a_4+a_1-2a_3
`c_4=a_3-a_2=c_2
Si l' ordre est un des suivants `(a_1;a_3;a_2;a_4)` ou `(a_1;a_4;a_2;a_3)`, alors après la deuxième étape on reçoit un des couples mentionnés en haut:
1er cas:
`b_1=a_3-a_1
`b_2=a_3-a_2
`b_3=a_4-a_2
`b_4=a_4-a_1
`c_1=a_2-a_1
`c_2=a_4-a_3
`c_3=a_2-a_1=c_1
`c_4=a_4-a_3=c_2
2e cas:
`b_1=a_4-a_1
`b_2=a_4-a_2
`b_3=a_3-a_2
`b_4=a_3-a_1
`c_1=a_2-a_1
`c_2=a_4-a_3
`c_3=a_2-a_1=c_1
`c_4=a_4-a_3=c_2
Si on la forme suivante: `(a_1;a_2;a_4;a_3)`, alors
`b_1=a_2-a_1
`b_2=a_4-a_2
`b_3=a_4-a_3
`b_4=a_3-a_1
`c_1=a_4+a_1-2a_2
`c_2=a_3-a_2
`c_3=a_4+a_1-2a_3
`c_4=a_3-a_2=c_2
carole- Expert
- Messages : 181
Date d'inscription : 11/05/2010
Age : 31
Re: Le problème du professeur Ducci
Pour l' ordre `a_1;a_3;a_4;a_2` on trouve:
`b_1=a_3-a_1
`b_2=a_4-a_3
`b_3=a_4-a_2
`b_4=a_2-a_1
et
`c_1=|a_4+a_1-2a_3|
`c_2=a_3-a_2
`c_3=|a_4+a_1-2a_2|
`c_4=a_3-a_2=c_2
On a donc bien une des formes cherchées!
Pour les ordres `a_1;a_2;a_3;a_4` et `a_1;a_4;a_3;a_2` on reçoit les mêmes valeurs après la première étape (sauf que `b_1` de l' un sera `b_2` de l' autre etc.)
En effectuant des rotations on obtient par après toutes les autres ordres possibles.
`b_1=a_3-a_1
`b_2=a_4-a_3
`b_3=a_4-a_2
`b_4=a_2-a_1
et
`c_1=|a_4+a_1-2a_3|
`c_2=a_3-a_2
`c_3=|a_4+a_1-2a_2|
`c_4=a_3-a_2=c_2
On a donc bien une des formes cherchées!
Pour les ordres `a_1;a_2;a_3;a_4` et `a_1;a_4;a_3;a_2` on reçoit les mêmes valeurs après la première étape (sauf que `b_1` de l' un sera `b_2` de l' autre etc.)
En effectuant des rotations on obtient par après toutes les autres ordres possibles.
carole- Expert
- Messages : 181
Date d'inscription : 11/05/2010
Age : 31
Re: Le problème du professeur Ducci
carole a écrit:
Il suffit donc qu' on obtient quelque part un quadruple dont 2 éléments sont égaux afin d' obtenir le quadruple `(0;0;0;0)`!
Je n'ai pas totalement saisi le raisonnement correspondant : tu raisonnes sans valeur absolue et il me semble que tu n'écris pas tous les cas.
Il faudrait analyser les cas (a,a,b,c), (a,b,a,c) et (a,b,c,a), non ? Et pour ne pas avoir de problèmes avec la valeur absolue, il faut encore discuter suivant l'ordre ...
Donc c'est plus compliqué ... ?
(Il faudrait rédiger une solution sans avoir à distinguer trop de cas ...
Je vais te donner une solution plus claire après, mais je te laisse encore un peu essayer, Ok ?)
Cordialement, G. Lorang
Dernière édition par G. Lorang le Mer 15 Juin - 19:15, édité 1 fois
Re: Le problème du professeur Ducci
J' avoue que mon raisonnement est compliqué. J' ai montré quelque part dans ces exemples pour chaque possibilité de deux éléments égaux que le théorème est vérifié (on peut faire des rotations en respectant l' ordre sans modifier les valeurs obtenues par après).
En tout cas je n' arrive pas a démontrer le reste avec mes calculs (peut-être trop longs).
En tout cas je n' arrive pas a démontrer le reste avec mes calculs (peut-être trop longs).
carole- Expert
- Messages : 181
Date d'inscription : 11/05/2010
Age : 31
J'avais encore réfléchi ...
et j'ai légèrement modifié ma réponse pendant que tu tapais déjà la suivante ...
J'avais compris ton idée, mais il faut que la démonstration soit impeccable !
Cordialement, G. Lorang
J'avais compris ton idée, mais il faut que la démonstration soit impeccable !
Cordialement, G. Lorang
Solution
Soit `delta` la fonction qui associe au quadruplet `(a_1,a_2,a_3,a_4)` le quadruplet `(b_1,b_2,b_3,b_4)` défini dans l'énoncé.
1) Si les 4 entiers `a_1`, `a_2`, `a_3` et `a_4` sont pairs, il en est de même pour `b_1`, `b_2`, `b_3` et `b_4`.
Plus précisément : `delta(2a_1,2a_2,a_3,a_4)=2delta(a_1,a_2,a_3,a_4)`
2) Après au plus 4 itérations de l'opération `delta`, tous les nombres sont pairs.
En effet : notons `i` des entiers impairs et `p` des entiers pairs. Dans la suite ces nombres ne sont pas forcément égaux.
C'est uniquement leur parité qui nous intéresse.
a) Partons d'un quadruplet avec uniquement des nombres impairs : `delta(i,i,i,i)=(p,p,p,p)`. Donc après une seule itération on obtient déjà des nombres pairs.
b) Si l'on part de 3 nombres impairs : `delta(i,i,i,p)=(p,p,i,i)`, `delta(p,p,i,i)=(p,i,p,i)`, `delta(p,i,p,i)=(i,i,i,i)` et `delta(i,i,i,i)=(p,p,p,p)` (4 itérations !)
c) Si l'on part de 2 nombres impairs, il faut distinguer deux cas :
c1) `delta(p,i,p,i)=(i,i,i,i)` et `delta(i,i,i,i)=(p,p,p,p)` (vu déjà sous b)
c2) `delta(p,p,i,i)=(p,i,p,i)`, `delta(p,i,p,i)=(i,i,i,i)` et `delta(i,i,i,i)=(p,p,p,p)` (également déjà traité)
d) Le dernier cas à regarder est celui où on part d'un seul nombre impair :
`delta(i,p,p,p)=(i,p,p,i)`, ensuite il y a encore itérations pour obtenir un quadruplet pair. (voir c2)
3) En appliquant la fonction `delta`, le maximum des 4 entiers est une fonction décroissante :
`b_1<=max(a_1,a_2)`, `b_2<=max(a_2,a_3)`, `b_3<=max(a_3,a_4)`, `b_4<=max(a_4,a_1)`
Donc : `max(b_1,b_2,b_3,b_4)<=max(a_1,a_2,a_3,a_4)`
4) En itérant aussi souvent que l'on veut l'opération `delta`, et en utilisant les points 1 et 2 de la démonstration, les entiers du quadruplet image deviennent des multiples de 2, puis de 4, puis de 8, etc. donc deviennent un multiple de toute puissance de 2. D'après le point 3, cela n'est possible que si tous les entiers s'annulent à un certain moment, car les entiers rencontrés au cours des itérations successives sont bornés et seulement 0 est divisible par toutes les puissances de 2.
Cordialement, G. Lorang
1) Si les 4 entiers `a_1`, `a_2`, `a_3` et `a_4` sont pairs, il en est de même pour `b_1`, `b_2`, `b_3` et `b_4`.
Plus précisément : `delta(2a_1,2a_2,a_3,a_4)=2delta(a_1,a_2,a_3,a_4)`
2) Après au plus 4 itérations de l'opération `delta`, tous les nombres sont pairs.
En effet : notons `i` des entiers impairs et `p` des entiers pairs. Dans la suite ces nombres ne sont pas forcément égaux.
C'est uniquement leur parité qui nous intéresse.
a) Partons d'un quadruplet avec uniquement des nombres impairs : `delta(i,i,i,i)=(p,p,p,p)`. Donc après une seule itération on obtient déjà des nombres pairs.
b) Si l'on part de 3 nombres impairs : `delta(i,i,i,p)=(p,p,i,i)`, `delta(p,p,i,i)=(p,i,p,i)`, `delta(p,i,p,i)=(i,i,i,i)` et `delta(i,i,i,i)=(p,p,p,p)` (4 itérations !)
c) Si l'on part de 2 nombres impairs, il faut distinguer deux cas :
c1) `delta(p,i,p,i)=(i,i,i,i)` et `delta(i,i,i,i)=(p,p,p,p)` (vu déjà sous b)
c2) `delta(p,p,i,i)=(p,i,p,i)`, `delta(p,i,p,i)=(i,i,i,i)` et `delta(i,i,i,i)=(p,p,p,p)` (également déjà traité)
d) Le dernier cas à regarder est celui où on part d'un seul nombre impair :
`delta(i,p,p,p)=(i,p,p,i)`, ensuite il y a encore itérations pour obtenir un quadruplet pair. (voir c2)
3) En appliquant la fonction `delta`, le maximum des 4 entiers est une fonction décroissante :
`b_1<=max(a_1,a_2)`, `b_2<=max(a_2,a_3)`, `b_3<=max(a_3,a_4)`, `b_4<=max(a_4,a_1)`
Donc : `max(b_1,b_2,b_3,b_4)<=max(a_1,a_2,a_3,a_4)`
4) En itérant aussi souvent que l'on veut l'opération `delta`, et en utilisant les points 1 et 2 de la démonstration, les entiers du quadruplet image deviennent des multiples de 2, puis de 4, puis de 8, etc. donc deviennent un multiple de toute puissance de 2. D'après le point 3, cela n'est possible que si tous les entiers s'annulent à un certain moment, car les entiers rencontrés au cours des itérations successives sont bornés et seulement 0 est divisible par toutes les puissances de 2.
Cordialement, G. Lorang
Sujets similaires
» OMB-Maxi Finale 2011
» THIRD BENELUX MATHEMATICAL OLYMPIAD : BxMO 2011
» OMB-Maxi Finale 2012
» Algèbre : Recherche d'un polynôme (OMB Maxi Finale 1978)
» Arithmétique : Un problème de Paul Erdös
» THIRD BENELUX MATHEMATICAL OLYMPIAD : BxMO 2011
» OMB-Maxi Finale 2012
» Algèbre : Recherche d'un polynôme (OMB Maxi Finale 1978)
» Arithmétique : Un problème de Paul Erdös
Page 1 sur 1
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum