Énigmes et Cie...

Hmm zut, suis occuppe la avec l'ouverture de mon cyber,

J'en ai bien une avec des chameaux mais j'ai pas les details sous la main.

Je passe a main.

Bon alors les chameaux:

J'habite en Israel au Nord du desert du Negev(ce n'est plus un desert depuis longtemps, ca ressemble maintenant plutot a la Beauce).Il y a beaucoup de bedouins un peu partout, et voila ce que j'ai entendu:

Un Sheik etant parti rejoindre ses ancetres a laisse a ses 3 fils ;17 chameaux avec comme instructions de les partager comme suit:
A l'aine revient la Moitiee
Au puine le tiers
et au benjamin un 9eme des chameaux.

Les freres se creusent la tete et decident de faire appel au sage du village voisin

Comment celui ci a-t-il partage l'heritage?

DOUBLE POST:

Ce a quoi vous avez echappe...


La conjecture de Syracuse



Prenez un entier positif ; s’il est pair, divisez-le par 2 ; s’il est impair, multipliez-le par 3 et ajoutez lui 1… Réitérez ce processus sur plusieurs exemples : que semble-t-il se passer ?

Partons de l’entier 7, et regardons la suite alors construite : 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1…. Cette suite devient cyclique, puisque l’obtention de la valeur 1 fait « boucler » indéfiniment l’algorithme.

On conjecture que l’on finit toujours par trouver la valeur « 1 » au fil des calculs quel que soit l’entier de départ… C’est la « conjecture de Syracuse » (encore appelée « problème 3n+1 »)… qui attend toujours une preuve !





Nous sommes au début des années 1930, Lothar Collatz, un étudiant de l’université de Hambourg, s’intéresse à la théorie des nombres et à la théorie des graphes.

Il part d’un entier positif quelconque et lui fait subir des transformations itératives (voir l’encadré « la conjecture originelle de Collatz »), trace les graphes associés et se pose des questions qui hantent encore les nuits de bien des chercheurs !



Un problème aux mille visages

C’est probablement Helmut Hasse, un ami de Collatz, qui a largement diffusé le problème 3n+1, qui porte aussi le nom d’« algorithme de Hasse ».

Pendant une visite à l’université de Syracuse (proche de New York, rien à voir avec le port Sicilien ! ) dans les années 50, Hasse diffuse le problème qui a un grand succès, il propose alors de le baptiser « problème de Syracuse ».

Le mathématicien Polonais Stanislas Ulam, qui travaille, pendant la seconde guerre mondiale, à l’université de Los Alamos, fait circuler l’algorithme qui devient bien sûr le « problème de Ulam ».

10 années passent et S. Kakutani s’intéresse au problème, le répand dans plusieurs universités américaines (Yale, Chicago…), la conjecture prend alors le nom de « problème de Kakutani ».

À chaque fois, le problème absorbe l’énergie des mathématiciens qui s’y frottent. À tel point, qu’à l’époque une blague circulait, affirmant que le problème faisait partie d’une conspiration visant à ralentir la recherche mathématique aux États-Unis !



Beaucoup d’encre a coulé, et coulera sans doute encore, autour de ce problème, si bien qu’un vocabulaire métaphorique s’est construit comme souvent en mathématiques.



Reprenons l’exemple initial de l’entier 7. On appellera la suite (7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1) la trajectoire ou le vol de 7. Chaque entier de cette suite est une étape du vol, 52 est l’altitude maximale de la trajectoire. La durée d’un vol (16, ici) est le nombre d’étapes nécessaires avant l’apparition du premier ‘1’ (s’il apparaît bien sûr !).



On peut aussi définir la durée du vol en altitude de l’entier 7 comme le nombre d’étapes entre le début du vol et le moment où il passe sous la valeur de départ, 11 dans notre exemple (attention, si la conjecture est fausse, ces durées peuvent être infinies).



Le facteur d’expansion est l’altitude maximale divisée par l’entier de départ (52/7 dans notre exemple).



Voici quelques exemples de comportements de l’algorithme 3n+1 sur des entiers particuliers :





Entier initial


durée


Vol en altitude


Altitude maximale


Facteur d’expansion

7


16


11


52


»7,43

32


5


1


32


1

27


111


96


9232


»341,93

97


118


3


9232


»95,18



332


3


3377699720527876


3

871


178


57


190996


»219.28

703


170


132


250504


»356.34

100759293214567


1820


166


1180174841128253392


»11712.81



On peut vérifier facilement que, pour les entiers inférieurs à 100, 27 est celui qui donne la plus grande altitude maximale ainsi que le vol en altitude le plus long, 97 fournit la meilleure durée de vol.

Pour les entiers inférieurs à 1000, les champions sont 703 et 871.

Pour les entiers inférieurs à 100000, essayez donc de tester quelques algorithmes (n’hésitez pas à nous les faire parvenir) pour retrouver 77671, 35655 et 77031... et tant qu’à faire, poussez la machine un peu plus loin, qui sait ?

Passons en revue les records actuels (qui sont sans doute déjà dépassés à la parution de cet article) :

- La conjecture a été vérifiée pour tous les entiers inférieurs à 1015.

- Le record de l’altitude maximale est détenu (pour le moment) par 10709980568908647 qui atteint l’altitude 350589187937078188831873920282244.

- Le record de la trajectoire la plus longue est celle du vol de 1256651665537537 (1865 étapes).

- La meilleure durée en altitude appartient, jusqu’à nouvelle découverte, à 1008932249296231 (1445 étapes en altitude).



Riche de ce nouveau vocabulaire, le problème peut s’énoncer de multiples façons :

Pour tout entier naturel n :

1. Tout vol a une durée finie.

2. Tout vol est de durée en altitude finie.

3. Le nombre d’étapes paires est fini.





On peut facilement démontrer que tous ces énoncés sont équivalents.

(Par exemple, on peut justifier par récurrence que, si le vol en altitude de l’entier n a une durée finie, alors cet entier vérifie la conjecture).







La conjecture peut être démontrée pour une infinité d’entiers.



Considérons la division Euclidienne d’un entier naturel n quelconque par 4 (dont le reste ne peut-être que 0,1,2 ou 3) :



* Si le reste est nul (n est divisible par 4), n=4k, à la première itération on « descend » sous n (4k étant pair on divise n par 2, l’étape suivante est 2k). Donc, le vol en altitude de tous les multiples de 4 est à durée finie (c’est même 1), ces entiers vérifient tous la conjecture.



* Si le reste est 1, n=4k+1, qui est impair, il devient 12k+4, puis 6k+2, puis 3k+1 qui est inférieur à n. Les entiers dont le reste de la division Euclidienne par 4 est 1 vérifient tous la conjecture puisque leur vol en altitude est fini (c’est 3).


* Si n=4k+2, le vol en altitude a pour durée 1 (puisque 4k+2 est pair), ces entiers vérifient aussi la conjecture !

* n=4k+3 est le seul à résister à nos assauts ! Et cette seule démonstration suffirait à conclure, mais…

En fait, nous venons de démontrer que 75% des entiers vérifient la conjecture de Syracuse ; par des méthodes similaires, on peut même aller beaucoup plus loin, ne laissant de côté que 2 ou 3 % des entiers…

On peut aussi avoir une approche statistique de l’algorithme. Il y a autant d’entiers pairs que d’entiers impairs dans l’ensemble des entiers naturels, sachant qu’un entier pair est divisé par 2, qu’un entier impair donne naissance à un entier pair (qui sera alors divisé par 2), on peut estimer qu’un entier donné est, en moyenne, multiplié par 3/4 à chaque itération (on « tombe » deux fois plus souvent sur une étape paire, que sur une étape impaire). Ce résultat tendrait aussi à confirmer la conjecture.



Finalement, beaucoup des résultats que nous venons d’énoncer nous poussent à croire que la conjecture deviendrait bien un théorème… Cependant, méfiance, il suffirait qu’un unique entier ne vérifie pas la propriété pour que tout s’effondre !

J. Conway nous fournit une raison supplémentaire de rester prudent : il a réussi à démontrer qu’une simple généralisation de la conjecture était algorithmiquement indécidable (voir l’encadré « Indécidabilité d’une généralisation »).

Alors tout ce travail pour rien ?

Non, bien sûr. Même si ce problème est indécidable, les avancées qu’il a suscitées autant dans la théorie des nombres que dans d’autres domaines des mathématiques, ne sont pas négligeables.

Peut-être que, comme le disait Paul Erdös, « Les Mathématiques ne sont pas encore prêtes pour de tels problèmes ».







ERIC MERCIER











La conjecture originelle de Collatz.

On trouve, dans les notes de Collatz datées du 1 juillet 1932, un problème similaire à la conjecture de Syracuse, aujourd’hui appelé « conjecture originelle de Collatz ».

Si n est un multiple de 3, on le multiplie par 2 puis le divise par 3.

Si n a pour reste 1 dans la division Euclidienne par 3, on le multiplie par 4, lui retranche 1 et divise le tout par 3,

Si n a pour reste 2 dans la même division, on le multiplie par 4, lui ajoute 1 et divise le tout par 3.

Ce qui revient à considérer la fonction :

La question est de connaître la nature de la suite obtenue en itérant ces transformations sur un entier naturel quelconque. La suite diverge-t-elle, devient elle cyclique… ?

Pour les entiers 1,2,3,4,5,6,7 et 9, on vérifie sans trop de peine que les suites deviennent cycliques sur le modèle (4,5,7,9,6,4,5,7,9,6,4...).

Une question, encore ouverte aujourd’hui, est celle de l’avenir de la suite commençant tout simplement par 8 ! Les 50 premiers termes de la suite engendrée par 8 sont [8, 11, 15, 10, 13, 17, 23, 31, 41, 55, 73, 97, 129, 86, 115, 153, 102, 68, 91, 121, 161, 215, 287, 383, 511, 681, 454, 605, 807, 538, 717, 478, 637, 849, 566, 755, 1007, 1343, 1791, 1194, 796, 1061, 1415, 1887, 1258, 1677, 1118, 1491, 994, 1325, 1767] finit-elle par boucler ou diverge-t-elle vers l’infini ? Avis aux amateurs…





ENCART : Le vol de l’entier 7 a une durée de 16 étapes, l’altitude maximale atteinte est 52. Le vol en altitude est de 11 étapes

[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]



ENCART : Un problème - deux énoncés.

Un autre énoncé de l’algorithme parfois utilisé aujourd’hui (légèrement différent de l’énoncé de l’article) est le suivant :

Si l’entier n est pair, on le divise par 2.

Si n est impair, on le multiplie par 3, lui ajoute 1 puis on divise le résultat par 2.

Ce qui revient à l’utilisation de la fonction S définie par :

Cet énoncé permet de réduire le nombre d’étapes, puisque 3n+1 est toujours pair lorsque n est impair. Attention alors, certains des records (en durée, en vol en altitude, en altitude maximale), ne sont plus les mêmes qu’avec l’énoncé utilisé ici.

heuh ... rdv sur le chan pour zigouiller qqs uber plutot lol

rofl, j ai deja la flemme de lire ton charabia, alors pour ce qui est d y comprendre qq chose je repasserai

Pfff petits joueurs

9 6 2 sans compter les chamelles pleines...

Exact mais comment a-il fait?
17/2 =9.5 ...

Guibor a écrit:Exact mais comment a-il fait?
17/2 =9.5 ...

17/2 = 8.5 chez moi..mais bon xD

a moi donc...
une plus littéraire :
qu'est ce que le SODOKU hormis un jeu?

Le sodoku est une infection du rat transmissible à l'homme par des morsures ou griffures. Le sodoku est traité par Pénicilline et tétracyclines. Alors pour éviter le sodoku, évitez les grilles, oui mais les grilles des égouts !

Merci google

mais avec google c'est trop facile donc ce n'est pas vraiment une énigme.

arf c vrai, trop facile avec google..
on peuy dire le nom de la bêbête spirillum morsus muri, je me sents un peu moins C..

Pour les histoires de chameau :

Le sage pretre un chameau au pere, cela fait donc 18 chameau, il donne 9 chameau a l'ainé, 6 au l'autre et 2 a l'autre et il reprend son chameau.

18/2 + 18/3 + 18/9 = 17
9+6+2 = 17

bravo

des fois rien ne sert de discourir longtemps, le but il faut atteindre jeune palawoa lol

Eh m*r*e j'aurais jamais cru que vous vous mettriez dans les énigmes dont la solution seule prends plus de 4 pages

Pour tout les autres qui préfèrent allé ce faire buter par des PK (Dsl je l'ai mal digéré celle la ) voici une énigme plus simple

La pesée impossible
On dispose d'une balance juste, de quatre masses (3g, 5g, 7g, 8g) et de 18 pièces de 1 à 18g (une de 1g, une de 2g, ... , une de 18g). Une seule de ces pièces ne peut pas être équilibrée avec les masses dont on dispose. Laquelle ?

Oui bah j'ai décidé de rester dans les maths ^^

T'es sur que ton énnoncé est correct?
Il ne manque pas une masse?
Car dans ce cas, tu ne peux déjà pas equilibrer la pièce de 1 et de 2 juste avec les masses.

+ 1 ploplo on peut pas mesurer les deux premières

Voici le post le plus long du forum !!
Obliger fallait que j'le quote pour faire chier le monde ^^

Guibor a écrit:DOUBLE POST:

Ce a quoi vous avez echappe...


La conjecture de Syracuse



Prenez un entier positif ; s’il est pair, divisez-le par 2 ; s’il est impair, multipliez-le par 3 et ajoutez lui 1… Réitérez ce processus sur plusieurs exemples : que semble-t-il se passer ?

Partons de l’entier 7, et regardons la suite alors construite : 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1…. Cette suite devient cyclique, puisque l’obtention de la valeur 1 fait « boucler » indéfiniment l’algorithme.

On conjecture que l’on finit toujours par trouver la valeur « 1 » au fil des calculs quel que soit l’entier de départ… C’est la « conjecture de Syracuse » (encore appelée « problème 3n+1 »)… qui attend toujours une preuve !





Nous sommes au début des années 1930, Lothar Collatz, un étudiant de l’université de Hambourg, s’intéresse à la théorie des nombres et à la théorie des graphes.

Il part d’un entier positif quelconque et lui fait subir des transformations itératives (voir l’encadré « la conjecture originelle de Collatz »), trace les graphes associés et se pose des questions qui hantent encore les nuits de bien des chercheurs !



Un problème aux mille visages

C’est probablement Helmut Hasse, un ami de Collatz, qui a largement diffusé le problème 3n+1, qui porte aussi le nom d’« algorithme de Hasse ».

Pendant une visite à l’université de Syracuse (proche de New York, rien à voir avec le port Sicilien ! ) dans les années 50, Hasse diffuse le problème qui a un grand succès, il propose alors de le baptiser « problème de Syracuse ».

Le mathématicien Polonais Stanislas Ulam, qui travaille, pendant la seconde guerre mondiale, à l’université de Los Alamos, fait circuler l’algorithme qui devient bien sûr le « problème de Ulam ».

10 années passent et S. Kakutani s’intéresse au problème, le répand dans plusieurs universités américaines (Yale, Chicago…), la conjecture prend alors le nom de « problème de Kakutani ».

À chaque fois, le problème absorbe l’énergie des mathématiciens qui s’y frottent. À tel point, qu’à l’époque une blague circulait, affirmant que le problème faisait partie d’une conspiration visant à ralentir la recherche mathématique aux États-Unis !



Beaucoup d’encre a coulé, et coulera sans doute encore, autour de ce problème, si bien qu’un vocabulaire métaphorique s’est construit comme souvent en mathématiques.



Reprenons l’exemple initial de l’entier 7. On appellera la suite (7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1) la trajectoire ou le vol de 7. Chaque entier de cette suite est une étape du vol, 52 est l’altitude maximale de la trajectoire. La durée d’un vol (16, ici) est le nombre d’étapes nécessaires avant l’apparition du premier ‘1’ (s’il apparaît bien sûr !).



On peut aussi définir la durée du vol en altitude de l’entier 7 comme le nombre d’étapes entre le début du vol et le moment où il passe sous la valeur de départ, 11 dans notre exemple (attention, si la conjecture est fausse, ces durées peuvent être infinies).



Le facteur d’expansion est l’altitude maximale divisée par l’entier de départ (52/7 dans notre exemple).



Voici quelques exemples de comportements de l’algorithme 3n+1 sur des entiers particuliers :





Entier initial


durée


Vol en altitude


Altitude maximale


Facteur d’expansion

7


16


11


52


»7,43

32


5


1


32


1

27


111


96


9232


»341,93

97


118


3


9232


»95,18



332


3


3377699720527876


3

871


178


57


190996


»219.28

703


170


132


250504


»356.34

100759293214567


1820


166


1180174841128253392


»11712.81



On peut vérifier facilement que, pour les entiers inférieurs à 100, 27 est celui qui donne la plus grande altitude maximale ainsi que le vol en altitude le plus long, 97 fournit la meilleure durée de vol.

Pour les entiers inférieurs à 1000, les champions sont 703 et 871.

Pour les entiers inférieurs à 100000, essayez donc de tester quelques algorithmes (n’hésitez pas à nous les faire parvenir) pour retrouver 77671, 35655 et 77031... et tant qu’à faire, poussez la machine un peu plus loin, qui sait ?

Passons en revue les records actuels (qui sont sans doute déjà dépassés à la parution de cet article) :

- La conjecture a été vérifiée pour tous les entiers inférieurs à 1015.

- Le record de l’altitude maximale est détenu (pour le moment) par 10709980568908647 qui atteint l’altitude 350589187937078188831873920282244.

- Le record de la trajectoire la plus longue est celle du vol de 1256651665537537 (1865 étapes).

- La meilleure durée en altitude appartient, jusqu’à nouvelle découverte, à 1008932249296231 (1445 étapes en altitude).



Riche de ce nouveau vocabulaire, le problème peut s’énoncer de multiples façons :

Pour tout entier naturel n :

1. Tout vol a une durée finie.

2. Tout vol est de durée en altitude finie.

3. Le nombre d’étapes paires est fini.





On peut facilement démontrer que tous ces énoncés sont équivalents.

(Par exemple, on peut justifier par récurrence que, si le vol en altitude de l’entier n a une durée finie, alors cet entier vérifie la conjecture).







La conjecture peut être démontrée pour une infinité d’entiers.



Considérons la division Euclidienne d’un entier naturel n quelconque par 4 (dont le reste ne peut-être que 0,1,2 ou 3) :



* Si le reste est nul (n est divisible par 4), n=4k, à la première itération on « descend » sous n (4k étant pair on divise n par 2, l’étape suivante est 2k). Donc, le vol en altitude de tous les multiples de 4 est à durée finie (c’est même 1), ces entiers vérifient tous la conjecture.



* Si le reste est 1, n=4k+1, qui est impair, il devient 12k+4, puis 6k+2, puis 3k+1 qui est inférieur à n. Les entiers dont le reste de la division Euclidienne par 4 est 1 vérifient tous la conjecture puisque leur vol en altitude est fini (c’est 3).


* Si n=4k+2, le vol en altitude a pour durée 1 (puisque 4k+2 est pair), ces entiers vérifient aussi la conjecture !

* n=4k+3 est le seul à résister à nos assauts ! Et cette seule démonstration suffirait à conclure, mais…

En fait, nous venons de démontrer que 75% des entiers vérifient la conjecture de Syracuse ; par des méthodes similaires, on peut même aller beaucoup plus loin, ne laissant de côté que 2 ou 3 % des entiers…

On peut aussi avoir une approche statistique de l’algorithme. Il y a autant d’entiers pairs que d’entiers impairs dans l’ensemble des entiers naturels, sachant qu’un entier pair est divisé par 2, qu’un entier impair donne naissance à un entier pair (qui sera alors divisé par 2), on peut estimer qu’un entier donné est, en moyenne, multiplié par 3/4 à chaque itération (on « tombe » deux fois plus souvent sur une étape paire, que sur une étape impaire). Ce résultat tendrait aussi à confirmer la conjecture.



Finalement, beaucoup des résultats que nous venons d’énoncer nous poussent à croire que la conjecture deviendrait bien un théorème… Cependant, méfiance, il suffirait qu’un unique entier ne vérifie pas la propriété pour que tout s’effondre !

J. Conway nous fournit une raison supplémentaire de rester prudent : il a réussi à démontrer qu’une simple généralisation de la conjecture était algorithmiquement indécidable (voir l’encadré « Indécidabilité d’une généralisation »).

Alors tout ce travail pour rien ?

Non, bien sûr. Même si ce problème est indécidable, les avancées qu’il a suscitées autant dans la théorie des nombres que dans d’autres domaines des mathématiques, ne sont pas négligeables.

Peut-être que, comme le disait Paul Erdös, « Les Mathématiques ne sont pas encore prêtes pour de tels problèmes ».







ERIC MERCIER











La conjecture originelle de Collatz.

On trouve, dans les notes de Collatz datées du 1 juillet 1932, un problème similaire à la conjecture de Syracuse, aujourd’hui appelé « conjecture originelle de Collatz ».

Si n est un multiple de 3, on le multiplie par 2 puis le divise par 3.

Si n a pour reste 1 dans la division Euclidienne par 3, on le multiplie par 4, lui retranche 1 et divise le tout par 3,

Si n a pour reste 2 dans la même division, on le multiplie par 4, lui ajoute 1 et divise le tout par 3.

Ce qui revient à considérer la fonction :

La question est de connaître la nature de la suite obtenue en itérant ces transformations sur un entier naturel quelconque. La suite diverge-t-elle, devient elle cyclique… ?

Pour les entiers 1,2,3,4,5,6,7 et 9, on vérifie sans trop de peine que les suites deviennent cycliques sur le modèle (4,5,7,9,6,4,5,7,9,6,4...).

Une question, encore ouverte aujourd’hui, est celle de l’avenir de la suite commençant tout simplement par 8 ! Les 50 premiers termes de la suite engendrée par 8 sont [8, 11, 15, 10, 13, 17, 23, 31, 41, 55, 73, 97, 129, 86, 115, 153, 102, 68, 91, 121, 161, 215, 287, 383, 511, 681, 454, 605, 807, 538, 717, 478, 637, 849, 566, 755, 1007, 1343, 1791, 1194, 796, 1061, 1415, 1887, 1258, 1677, 1118, 1491, 994, 1325, 1767] finit-elle par boucler ou diverge-t-elle vers l’infini ? Avis aux amateurs…





ENCART : Le vol de l’entier 7 a une durée de 16 étapes, l’altitude maximale atteinte est 52. Le vol en altitude est de 11 étapes

[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]



ENCART : Un problème - deux énoncés.

Un autre énoncé de l’algorithme parfois utilisé aujourd’hui (légèrement différent de l’énoncé de l’article) est le suivant :

Si l’entier n est pair, on le divise par 2.

Si n est impair, on le multiplie par 3, lui ajoute 1 puis on divise le résultat par 2.

Ce qui revient à l’utilisation de la fonction S définie par :

Cet énoncé permet de réduire le nombre d’étapes, puisque 3n+1 est toujours pair lorsque n est impair. Attention alors, certains des records (en durée, en vol en altitude, en altitude maximale), ne sont plus les mêmes qu’avec l’énoncé utilisé ici.

haaan le vilain quoteur xD

Merde, pour la premère fois que je prends une énigme sur le net, ça marche pas ^^ mais bon dans leur solution, il acceptait les soustration....

8-7=1
7-5=2
3=3
5+7-8=4
5=5
5+7-8=6
7=7
8=8
7+5-3=9
7+3=10
8+3=11
7+5=12
8+5=13
Donc 14 ???
7+8=15
3+5+8=16
7+8+5-3=17
7+8+3=18

A ba oui on peut soustraire...