Un algorithme venu du froid

[raptor77]

Bonjour ce problème a été posé aux Olympiades de la zone baltique en 1990 :

On part de l’entier naturel N= 4 et on choisit l’une des trois règles suivantes pour déterminer un nouveau nombre entier naturel :

N est divisé par 2
N est multiplié par 10
N est multiplié par 10 et on ajoute 4 au produit
En d’autres termes il y a trois transformations possibles : N/2, 10N et 10N+4, la première ne pouvant être retenue que si N est pair.

On réitère le processus ad infinitum. Montrer que n’importe quel nombre entier peut être calculé avec cet algorithme.

Bonne chance et merci d'avance pour vos réponses (moi au moins je suis poli je dis merci et bonjour)
Cordialement
Raptor

[raptor77]

Personne ne veut esquisser une réponse? :cry: :cry: :cry:

[aviateurpilot]

Montrer que n’importe quel nombre entier peut être calculé avec cet algorithme.

montrer quelque soit x de N on peus arriver à 4 en suivant les transformations réciproque suivantes:
: la réciproque de
: la réciproque de
: la réciproque de
on travaille par ces transformations
= et puis donne
= et puis donne
= et puis donne
= donne

operation (*)
=> si
donne
=> si
et puis donne
=> si
donne
=> si
2fois et donne
=> si
donne

si on prend un x queconque de IN
et on lui fait l'operation (*)
on trouve un x'<x
soit la fonction f tel que f(x)=x'
on pose la suite avec
puisque
donc est une suite decroissante de nombres entiers naturel
alors on va surement arriver a une a tel que
alors il y a 3 cas pour :
1) on fait 2 fois et on trouve 4
2) on fait 1 fois et on trouve 4
3) c'est fini là

:++: :++: voila raptor77

[aviateurpilot]

pas de confirmation :cry:

[raptor77]

C'est bon aviateur :++: :++: :++: :++: :++: :++: :++:

[aviateurpilot]

vous avez compris ma solution?

[raptor77]

oui bien sur

[aviateurpilot]

et les autre membres

[raptor77]

je pense que c'est oui aussi

[ayanis]

oui aussi, et chapeau, j'aurai congru à 10 comme une idiote, j'avais pas vu que 5 suffisait alors que les opérations sont les mêmes pour 6 et 1 etc...

Bravo! :++:

[aviateurpilot]

merci.
mais tu n'as pas penser a une autre solution?

[ayanis]

Bonjour,

Je viens de me rendre compte qu'une partie de la question n'a pas été montrée. Tu dis que donc il existe un a pour lequel Ua=0 mais l'énoncé demandé un a tel que Ua=4!

Après c'est vrai que si on est à 0, on applique t3 et 0x10+4=4, mais il fallait rajouter cette ligne je pense...

Sinon, non, je n'ai pas d'autre méthode possible en tête.

ttyl

[aviateurpilot]

j'ai dit
mais j'ai pas travailler par ce
j'ai vu les cas possible pour puis en utilisant les transformation que j'ai consideré sur j'ai arrivé à ,(essaye de relire ma solution)

c'est vrai que si on est à 0, on applique t3 et 0x10+4=4,

non, c'est faux,car il ne faut travailler que par les transformation receproque
et pas par 10N+4 car c'est une transformation qu'on fait si on part de 4
mais moi mon depart c'est et je veux arriver à 4 (l'inverse)

[Joker62]

J'ai compris mouahahaha :)
Y'a juste une erreur
Tu dis que U(n+1) = F(U(n)) > U(n) alors U(n) est une suite décroissante.

Il est évident que c'est U(n+1) = F(U(n)) < U(n) vu que x' < x

[aviateurpilot]

J'ai compris mouahahaha
Y'a juste une erreur
Tu dis que U(n+1) = F(U(n)) > U(n) alors U(n) est une suite décroissante.

Il est évident que c'est U(n+1) = F(U(n)) < U(n) vu que x' < x

et c'est --- U(n+1) = F(U(n)) < U(n) --- ce que je voulais ecrire, just une erreur de frappe :++:

[redwolf]

Bonjour à tous.

Malheureusement, cette démonstration comporte une erreur : une transgression de la règle fixée par l'énoncé.

En effet, la transformation n'est pas légale lorsqu'on l'applique à un nombre qui se termine par un 9. Un exemple avec le nombre 9 lui même :

s'obtient en faisant .

Dans l'autre sens, celà revient à passer de 1 à 9 en divisant d'abord 1 par 2, ce qui est interdit par l'énoncé.

Il faut donc peaufiner tout ça !!....

A bientôt,

Redwolf

[Joker62]

J'fais un up pour aviateurPilot ! :)

[Imod]

Ce problème est le A124 des "Jeux mathématiques de Diophante" . La solution est surprenante mais la démonstration un peu lourde !!!

Imod

[Joker62]

Tous répertoriés ici : http://www.diophante.fr/