Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 27-10-2017 17:11:41

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

Un but de Syracuse

Hello!

Le fameux problème de la conjecture de Syracuse.

Je rappelle brièvement la conjecture:
Prenez n'importe quel N entier puis appliquer la procédure suivante en boucle:
-Si ce que vous avez est pair appliquez l’opération T0 = x -> x/2 (vous divisez par deux)
-Si ce que vous avez est impair appliquez l’opération T1 = x -> (3x+1)/2 (vous multipliez par 3, ajoutez 1 et divisez deux)
La conjecture dit que vous finirez par toucher 1 quelque soit l'entier de depart.

La question que je vous pose:
Considérons une suite finie des opérations de base, par exemple: T0, T1, T0, T1, T1, T1, T0 existe t il toujours un N de départ dont les itérations commencent par cette suite d’opérations?

Bonne chance!

  • |
  • Répondre

#0 Pub

 #2 - 27-10-2017 18:22:02

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,382E+3

un bout de syraxuse

Bonsoir

La réponse est oui et d'une infinité de façons . J'avais passé un petit moment là-dessus il y a quelques années smile

Vasimolo

 #3 - 27-10-2017 21:29:17

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Un bout de Syracusse

Bonjour,
notons u_n(k) la n-ième valeur prise par k en suivant la suite de syracuse.
on a par exemple u_0(5) = 5, u_1(5) = 8, u_2(5) = 4 ...
montrons que les n premières étapes de la suite de Syracuse sont communes pour k et k+2^n, et que la n+1 étape diffère:
on montre aisément par récurrence que u_i(k+2^n) = u_i(k) + 2^(n-i)*p tant que i est inférieur à n, ou p est un nombre impair (plus précisément une puissance de 3), et on à bien à chaque étape la même parité entre u_i(k+2^n) et u_i(k)
à partir de i = n, la parité n'est plus la même, la prochaine étape sera donc différente.

On peut désormais construire notre nombre simplement, un exemple sur la méthode vaudra mieux qu'un long discours:
Notons + pour T1 et - pour T2
cherchons tout les nombres commençant par la séquence d'opérations:
- - - + - + + -
0 suit la séquence - - - - - - ...
0 + 2^3 = 8 suit la séquence - - - + - + - + - ...
8 + 2^6 = 72 suit la séquence - - - + - + + + - - - ...
72 + 2^7 = 200 commence par - - - + - + + -
L'ensemble des nombres commençant par cette séquence sont tout les nombres de la forme 200 + k*2^8
En effet, à partir du lemme démontrer plus haut, on démontre très facilement que les 2^n premiers entiers ont leur n premières opérations distinctes deux à deux.


Application:
-1 donne les opérations + + + + + + ...
2^n - 1 commencera donc par n fois l'opération +

 #4 - 28-10-2017 08:03:28

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

un bput de syracuse

La réponse est oui, pour n'importe quelle suite finie. Je te dis ça de mémoire sans aucune hésitation. La preuve est simple.

Cette séquence est compatible avec tous les nombres de la forme 128n + 18, et seulement eux.

 #5 - 29-10-2017 11:41:39

Bastidol
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 152

UUn bout de Syracuse

Bonjour,


Considérons seulement les 3 premières itérations :
                     N         est pair 
Exécutons T0  N/2          doit être impair        possible
Exécutons T1 : (3N+2)/4     doit être pair        possible
Exécutons T0:  3(N/2)+1    doit être impair        impossible car 3 fois le nombre impair N/2 est impair + 1 est pair.


Je suis surpris de démontrer aussi facilement que cette suite est impossible.
Je me plante certainement hmmhmm

 #6 - 29-10-2017 22:26:51

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Un bout de Syacuse

Salut Clydevil, la réponse est oui !

Pour une suite de k opérations, l'astuce est de considérer les k derniers chiffres de la représentation binaire de N : chacune des 2^k possibilités pour ces chiffres correspond à une unique suite de k opérations parmi les 2^k suites possibles.

On peut le démontrer par récurrence sur k. Voici le point clé : si N1 et N2 terminent par les mêmes k bits et diffèrent par le (k+1)-ème bit, alors les k premières opérations issues de N1 et N2 sont identiques, et la (k+1)-ème opération diffère.

Par exemple :
...1011 donne ...001, puis ...10, puis ...1, puis ... via T1,T1,T0,T1.
...0011 donne ...101, puis ...00, puis ...0, puis ... via T1,T1,T0,T0.
On voit qu'à chaque étape, seul le bit de gauche est différent, et cette propriété est conservée jusqu'à la fin, donc seule la dernière opération diffère. C'est évident pour une opération de type T0, car on enlève juste un 0 à droite du nombre. Ça l'est moins pour une opération de type T1, mais ça s'explique en remarquant que 3*N + 1 = N + 2*N + 1 : si N1 et N2 ne diffèrent qu'à partir du k-ième chiffre, alors les k premiers chiffres de 2*N1 et 2*N2 sont identiques.

 #7 - 30-10-2017 07:18:17

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3208
Lieu: Luxembourg

Un bout de Syracusse

Je pense que répondre à ta question est équivalent à démontrer la conjecture elle-même. Bon courage.

 #8 - 30-10-2017 10:11:26

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

Un obut de Syracuse

@Bastidol: La question porte sur n'importe quelle suite, mais même pour celle donnée en exemple en effet il y a qq chose de louche dans ta démo smile
@Franky1103: Nope c'est beaucoup plus simple smile

 #9 - 30-10-2017 18:10:07

Bastidol
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 152

un bour de syracuse

j'ai trouvé ce qui cloche ((3N+2)/2 )/2 = (3N+2)/4

 #10 - 31-10-2017 07:43:25

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Un bout de Syracuuse

J'avais un temps utilisé ce procédé pour trouver le plus petit nombre d'une boucle éventuelle. J'avais alors identifié 38 nombres sur 512. Si le ratio 38/512 tend vers 0 au fur et à mesure qu'on va analyser , le nombre de survivants croît cependant presque exponentiellement. Ces données peuvent éventuellement aider à tester le plus grand nombre possible, en éliminant tous les autres.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 20ème, en quelle position êtes-vous ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete