Une hyper souris qui mange un hyper fromage

[Médiat]

Dans un univers à 17 dimensions d'espace, une hypersouris se trouve au centre (vide) d'un hypercube de gruyère (suisse) constitué de 3^17 hypercubes de taille 1/3 de la taille global.

L'hypersouris peut se déplacer en mangeant un "petit" hypercube de fromage, à condition que celui-ci partage une face avec l'hypercube où se trouve la souris, et, bien sûr, qu'il ne soit pas déjà mangé.

L'hypersouris peut-elle manger tout le fromage, et si oui en suivant quel chemin (on peut facilement repérer un des petits hypercubes à l'aide de coordonnées dont chaque composante peut prendre les valeurs -1, 0 et 1)
-----

[toothpick-charlie]

C'est un problème de parcours hamiltonien. Le graphe ayant beaucoup de sommets et relativement peu d'arêtes (on est très loin des conditions du théorème de Dirac par exemple) je dirais que ça doit être impossible (mais la deuxième question m'inquiète, à moins que ça soit un piège...)

[Amanuensis]

On peut voir cela aussi comme la recherche d'un code de Gray en ternaire.

La méthode "par réflexion", utilisée en binaire, ne s'adapte pas immédiatement...

[Médiat]

Bonsoir,

Le graphe ayant beaucoup de sommets et relativement peu d'arêtes (on est très loin des conditions du théorème de Dirac par exemple) je dirais que ça doit être impossible

Je ne vois pas bien l'argument, un graphe linéaire a peu d'arêtes mais on peut le parcourir en passant une et une seule fois par tous les sommets.

(Ce n'est pas un cycle qui est recherché, c'est une chaîne hamiltonienne et pas un graphe hamiltonien)

[A voir en vidéo sur Futura]

[toothpick-charlie]

c'est juste un argument heuristique. Plus un graphe a d'arêtes plus on a de chances d'y trouver un parcours hamiltonien. Les théorèmes qui donnent des conditions suffisantes pour l'existence d'un tel chemin supposent beaucoup d'arêtes.

[Amanuensis]

Ce que je connais sur ce sujet ne fait pas de 17 une valeur remarquable. L'est-elle néanmoins, ou cette valeur a été choisie sur d'autres critères?

[Thomas markley]

sans difficulté... puisque la souris et le fromage sont élément de cet univers, ils sont donc définie en 17 dimension d'espace eux-même... bref guère plus complexe que pour nous en 3 dim d'espace, et les n-autres pouvant-etre définie pour notre univers

[ansset]

il me semble que 17 n'est pas choisi par hasard .

[toothpick-charlie]

La souris 1D ne peut pas manger le fromage, la souris 2D peut, la souris 3D ne peut pas... (je sais j'ai une manière pédestre d'aborder les problèmes).

[Médiat]

La souris 1D ne peut pas manger le fromage, la souris 2D peut, la souris 3D ne peut pas... (je sais j'ai une manière pédestre d'aborder les problèmes).

C'est un bon début.

Pour répondre à ansset, 17 n'est pas choisi au hasard, dans le sens où toutes les valeurs ne conviennent pas, mais est choisi au hasard, dans le sens où plusieurs valeurs conviennent.

[toothpick-charlie]

je pense avoir une démonstration par récurrence (un peu informelle) du fait que c'est possible de manger un fromage de dimension n si n est une puissance de 2. Mais ça ne résoud nullement le cas n=17.

[Médiat]

Bonjour,

je pense avoir une démonstration par récurrence (un peu informelle) du fait que c'est possible de manger un fromage de dimension n si n est une puissance de 2. Mais ça ne résoud nullement le cas n=17.

Pour ma curiosité, pourriez-vous poster votre démonstration (même informelle) ?

[toothpick-charlie]

C'est l'idée que le fromage de dimension 2^(n+1) est le produit de deux copies du fromage de dimension 2^n, qu'on peut construire en partant d'un fromage de dimension 2^n, dans lequel on remplace chaque petit cube par une copie du fromage de dimension 2^n, en liant chaque sommet d'un petit fromage au sommet homologue du fromage adjacent dans la même rangée ou colonne (etc) . Alors si on sait manger entièrement un petit fromage (ce qui est vrai dans la récurrence), on peut ensuite en sortir pour manger le suivant. Il suffit de décrire les petits fromage composants du grand dans l'ordre de dégustation du fromage, qui existe par hypothèse de récurrence (j'avais bien dit que c'était informel!)

[Amanuensis]

Pour les longueurs paires, suffit de remarquer qu'on peut, pour tout mot X, faire un parcours passant par les neufs points:

X00 <-> X++

On peut donc enchaîner à partir de X00 -> X++ -> Y++ -> Y00 -> Z00 ->, etc., en alternant la direction de la séquence, ce qui donne un parcours complet si X, Y, Z, ... est lui-même un parcours (donc pour un longueur de 2 crans plus petite).

Pour 2 cela donne 00 0+ -+ -0 -- 0- +- +0 ++

Pour 4 on a 00(00 0+ -+ -0 -- 0- +- +0 ++) 0+(++ +0 +- 0- -+ 0+ 00) -+(00 0+ -+ -0 -- 0- +- +0 ++) -0(++ +0 +- 0- -+ 0+ 00) ... jusqu'à ++(++ +0 +- 0- -+ 0+ 00)

[C'est une variante d'un algo connu pour les codes de Gray k-aire de longueur quelconque. L'algo connu commence dans un coin (le mot tout +, par exemple), ce qui ne répond pas à la question.]

[Amanuensis]

Commentaire: Quand j'ai lu l'énoncé, ma première réaction a été, c'est juste un code de Gray, l'un des algos connus doit donné la solution.

Après examen, non. Le problème a l'air original. Les deux questions usuelles pour un code k-aire de longueur n sont:

A) - Un code en acceptant la transition cyclique sur les k valeurs (passer de + à - en ternaire écrit 0 + -, ou passant de 0 à k-1 si on écrit les valeurs de 0 à k-1).

Il y a alors une solution cyclique, donc pouvant démarrer à n'importe quel endroit.

B) - Un code sans accepter la transition cyclique.

Il y a une solution publiée, mais l'algo démarre "dans un coin", et le code n'est pas cyclique pour k impair.

(Note: en binaire, k=2, il n'y a pas de différence entre les deux questions...)

La question posée dans ce fil est la question B avec la contrainte supplémentaire, le départ est le mot central.

Je n'ai pas trouvé trace d'un problème C, qui serait un code sans la transition cyclique, et démarrant en un mot imposé.

L'algo du message précédent donne (enfin, j'espère!) une solution pour k=3, n pair (si on sait résoudre le départ au centre, une variante permet de démarrer de n'importe où...). Je n'ai pas étudié si elle se généralise à tout k impair.

Comme il n'y a pas de solution pour k=3, n=1, on sait qu'il n'y a pas de solution générale. Resterait (si l'algo du message précédent est correct) à voir si tous les impairs sont impossibles ou non...

(Note: Sauf erreur de ma part, il suffit qu'il y ait une solution pour un impair pour qu'il y en ait une pour tout impair plus grand...)

[toothpick-charlie]

en y repensant je me dis que mon approche marche pour les dimensions paires. En fait si on peut parcourir le fromage de dimension p et le fromage de dimension q on peut parcourir le fromage de dimension p+q (le produit). Comme on peut voir facilement qu'on peut parcourir le fromage de dimension 2, on a toutes les dimensions paires. Tout ça n'aide pas pour n=17. Est-ce que c'est possible que ça ne marche jamais en dimension impaire? ou bien 2^n+1 ? ou pour les dimensions qui sont des nombres de Fermat?

[Médiat]

En fait si on peut parcourir le fromage de dimension p et le fromage de dimension q on peut parcourir le fromage de dimension p+q

Il manque quelque chose : le point de départ ce qui est important.
Une petite récurrence donne le résultat facilement. L'hypothèse de récurrence c'est (j'espère que mes notations sont claires) :
On peut parcourir le cube de dimension en partant de et en finissant en

Pour le cube de dimension , il suffit de parcourir le cube de dimension de à ce qui permet de passer à , puis à (ce chemin est le chemin inverse du chemin existant par hypothèse de récurrence), il reste à démontrer que pour le cube de dimension 2 c'est ok (trivial), et que l'on peut passer de (0, 0) à (1, 0) ... à (1, 1) (facile, même si on doit ajouter que l'on termine bien en ).

Mais, comme vous l'avez bien remarqué, cela ne dit rien du cas 17.

[Amanuensis]

Le message précédent est juste une redite, sous une autre forme, de ce qui est message #15... (Sauf la terminaison, j'ai dû me tromper sur la parité du décompte...)

----

Pour les longueurs impaires, il y a peut-être moyen de montrer l'impossibilité par décompte.

Si on prend le cas n=3, et en prenant le langage des éléments de cubes, on voit qu'il y a un centre, 6 faces, 12 arêtes et 8 sommets. Les transitions sont nécessairement entre deux catégories contiguës (en termes de mots, chaque classe correspond à un nombre de 0, et ce nombre change de parité à chaque transition). Comme on part du centre, l'élément suivant est une face, et on ensuite alternance (face ou sommet) et (arête). Comme on a seulement 12 arêtes, on peut avoir au max 12+1 (face ou sommet) dans le chemin, il en manque nécessairement un puisque le total est de 14.

Pour le n-cube, il y a C(n,p)2^(n-p) mots avec p zéros. Faut donc comparer la somme des C(n,p)2^(n-p) pour p impair avec la somme des C(n,p)2^(n-p) pour p pair...

Je verrai cela demain, si personne n'a conclu cette ligne de raisonnement avant...

[Amanuensis]

Bon, reprenons.

On s'intéresse aux codes de Gray sur l'ensemble des mots de longueurs n, à caractères dans un alphabet de k symboles, k=3. Le problème posé est équivalent à l'existence d'un tel code, en démarrant à une position particulière.

En notant les symboles par les entiers de -(k-1)/2 à (k+1)/2, on dira qu'un mot est "pair" s'il est composé d'un nombre pair de symboles pairs et d'un nombre impair de symboles impairs ; les autres mots sont "impairs". Dans le cas k=3, c'est équivalent à avoir un nombre pair de 0.

La contrainte implique que la parité change à chaque étape, et donc qu'un chemin hamiltonien présente une alternance de parité.

Dans le cas k=3, il y a par simple dénombrement mots ayant p 0.

À partir du développement de , on démontre que le nombre de mots pairs est égal à 1 de plus que le nombre de mots impairs.

Un code Gray (un chemin hamiltonien dans le graphe décrit dans l'énoncé) n'est donc possible qu'en commençant et finissant à un mot pair.

Si n est impair, dont le cas n=17, le mot de départ est un mot impair, et il n'y a donc pas de solution.

---------------------

L'algorithme "usuel" partant d'un "coin", c'est à dire d'un mot sans 0, et donc d'un mot pair, et marche dans les cas n impair.

L'algorithme présenté dans ce fil peut être modifié de façon à construire une solution étant donnés un mot pair de départ et un mot pair d'arrivée.

La généralisation à tout k impair doit être aisée. Le nombre de mots ayant p symboles pairs est , et le développement de montre la différence de 1 entre le nombre de mots pairs et le nombre de mots impairs.

[Amanuensis]

PS: Merci à l'animateur, c'était un problème intéressant.

[Médiat]

Pour compléter le message précédent, sans avoir à compter le nombre de position paires (la somme des coordonnées est paire) et le nombre de positions impaires (la somme des coordonnées est impaire), ce qui n'est, effectivement, pas très compliqué avec le développement de , on peut aussi remarquer que si dans une dimension il y a 1 position paire (resp. impaire) de plus que de positions impaires (resp. paires), en dimension (n+1) c'est le contraire (et le cas de la dimension 1 est trivial).

Une façon plus ludique (mais qui n'économise pas la démonstration) de voir les choses (en dimension 3, on peut effectivement le voir) est de colorier le cube central en blanc, de colorier en noir les cubes adjacents à un cube blanc, et en blanc les cubes adjacents à un cube noir (ce n'est qu'une façon de traduire que somme des coordonnées est paire (blanc) ou impaire (noir)), chaque mouvement fait passer d'une couleur à une autre, et comme en dimension impaire, il y a un cube noir de plus que de cube blanc (c'est là qu'on ne peut économiser une démonstration), on ne peut pas parcourir tous les cubes en commençant par un blanc.

PS: Merci à l'animateur, c'était un problème intéressant.

J'en suis ravi.

[toothpick-charlie]

j'aurais dû penser à cette solution, elle ressemble au traitement du problème des dominos sur l'échiquier qui est dans le livre de Claude Berge...

[Amanuensis]

Après coup, cela paraît presque évident (http://spikedmath.com/557.html, penser à passer le pointeur sur le psi).

Mais aurait-on indiqué l'idée de la coloration d'entrée, l'algo pour générer un chemin hamiltonien étant données les deux cases extrêmes ne serait peut-être pas apparu...