Comments on Comment piéger un David Madore

Bravo !

Et bien ces fourmis elles m'auront bien usé aussi ces derniers temps. J'ai finalement une solution, originellement probablement la même que celle de Hugues R. à base d'indice de Hopf, puis qui s'est laissé transformer en purement combinatoire. Allez je la poste à l'usage de votre maman. Remarque en passant : si vous passez gare de Waterloo obnubilé par un problème que vous n'arrivez pas à résoudre, aller s'asseoir quelques jours plus tard gare d'Austerlitz mène à la solution.

Remarque supplémentaire : après une nuit de sommeil, ça s'est encore simplifié ; je recommence donc et effacerai à la fin la version précédente.

C'est une preuve par l'absurde : je suppose qu'il y a une façon de faire tourner les fourmis sans collisions. Comme le fait remarquer Hugues R. dans un commentaire précédent, il n'est pas très difficile de voir qu'on peut supposer que chaque fourmi fait exactement un tour. Je suppose enfin que la période du mouvement des fourmis est 1. Je note selon l'usage f le nombre de faces, a le nombre d'arêtes, s le nombre de sommets du polyèdre. Accessoirement, on interdit aux fourmis de se reposer exactement aux sommets.

Pour chaque couple (A,S), avec S extrémité de l'arête A, je noterai :

t_1(A,S) le temps de parcours de A par la fourmi y pénétrant par le sommet S ;
t_2(A,S) le temps qui s'écoule entre le passage en S de la fourmi y arrivant par l'arête A et le passage en S de la fourmi quittant S par l'arête A ;
t_3(A,S) le temps qui s'écoule entre le passage en S de la fourmi y arrivant par l'arête A et le passage suivant d'une fourmi en S.

On va estimer de deux façons différentes le nombre Sigma, somme sur (A,S) des t_1(A,S)+t_2(A,S).

La première façon est de regrouper la somme en sommant d'abord les quatre nombres qui concernent une même A, puis en sommant toutes les A. La somme pour A fixé est égale à la somme du parcours de A dans un sens, puis de la première durée d'inoccupation de A, puis du parcours de A dans l'autre sens, puis de la deuxième durée d'inoccupation de A. Cette somme vaut donc 1. La somme sur tous les A vaut finalement a. Donc Sigma = a.

Dans une deuxième optique, on sépare Sigma en Sigma_1 (somme des t_1) et Sigma_2 (somme des t_2).
Regroupons les sommants de Sigma_1 par fourmi. Pour chaque fourmi, la somme des t_1 qui la concernent est le temps total qu'elle passe sur les arêtes du polyèdre : c'est donc 1. La valeur totale de Sigma_1 est donc le nombre de fourmis : Sigma_1=f.
Pour Sigma_2, on se contente d'une inégalité. On remarque que par définition, t_3(A,S) <= t_2(A,S). Donc Sigma_3 <= Sigma_2, en appelant Sigma_3 la somme des t_3. En regroupant les sommants de Sigma_3 par même S puis en sommant sur tous les sommets, on voit que Sigma_3 = s. Donc s <= Sigma_2. Donc f + s <= Sigma.

En synthétisant f + s <= a.

Or (Euler-Poincaré), f - a + s = 2. Contradiction !

Hughes, merci!
j'avais des idées plutôt confuses et ce qui me gênait était qu'une fourmi puisse ressortir du cycle immédiatement mais c'est impossible sur une sphère.

Au fait, si je puis me permettre une question, que pensent les personnes compétentes de ce que dit (l'ami de) Gao Xingjian?

Pour phi:

Je ne suis pas sûr de comprendre ta question ; le graphe "instantané" dont je parle n'est pas un sous graphe du polyèdre, mais un sous-graphe du graphe dual (ses sommets sont les centres des faces). Ce graphe est construit de façon à contenir un cycle avec la propriété que toutes les fourmis qui le traversent se dirigent vers l'intérieur du secteur qu'il délimite. Ensuite, lorsque le temps avance, ce cycle se casse ; on peut même supposer qu'une seule arête est responsable de cette cassure ; alors, puisque les fourmis se dirigent vers l'intérieur du cycle, l'arête qui s'est déplacée l'a fait elle aussi vers l'intérieur ; ce faisant, elle aura créé un nouveau cycle qui se trouvera à l'intérieur du cycle précédent (à ce stade, il vaut mieux faire un dessin pour comprendre) ; et ce nouveau cycle aura encore la propriété que toutes les fourmis qui le croisent y entrent, sans qu'aucune n'en sorte. Ainsi un certain nombre de fourmis sont "piégées" dans des secteurs de plus en plus petits, et donc vont forcément devoir entrer en collision.

L'idée de base est que, si, par exemple, d'un certain sommet du polyèdre partent n arètes, et que les n fourmis des faces correspondantes se trouvent toutes sur ces arètes à un même moment et se dirigent vers ce sommet, alors forcément il y aura une collision (selon la description du paragraphe précédent, on peut dessiner un petit disque autour du sommet, et toutes les fourmis se dirigent vers l'intérieur de ce disque). C'est cela que la construction de Klyachko généralise.

Je ne pense pas pouvoir expliquer mieux, pour plus de détails je t'invite à consulter l'article klyachko.ps cité dans les commentaires de David et de Denis F. (très clair, il y a même des dessins pour illustrer !)

Ce commentaire n'est pas forcément passionnant mais bon…

A propos de la beauté des mathématiques, j'ai lu dernièrement un petit livre de Gao Xingjian qui reprend son très intéressant discours de Stockholm et des entretiens un peu inégaux qu'il a eus avec Denis Bourgeois (dont j'ignore tout), et je suis tombé sur ces propos de G.X. qui m'ont immédiatement, à tort ou à raison, fait penser à David:

"Une fois, j'ai eu une discussion avec un ami, mathématicien, il m'a dit: On croit que les mathématiques, c'est ce qu'il y a de plus logique, de plus scientifique, en fait c'est une création de l'imagination, avec même un caractère esthétique".

Hugues:
Sur la preuve de Klyachko, je suis d'accord, même, que les arêtes vont former des cycles ("instantanés") et le graphe dual permet de se rendre compte plus facilement, en essayant, de ce que les les arêtes ne peuvent pas être déplacées "continûment" (à chaque étape, l'arête avance sur le sommet adjacent suivant, ou bien reste immobile), mais jene vois pas comment appliquer la suite de l'explication pour conclure…

ok désolé :)

Ok je viens de me rendre compte que j'avais pas compris le pb, maintenant le but c'est de monter au dessus de n, en gros? :o)

Ruxor & le même individu> Heu je vais surement dire une connerie, mais dans les matrices 2x2, si on fait l'ensemble des matrices [[X, Y];[-Y, X]], qui forme bien un sous-espace vectoriel de M2,2, et dont les déterminants s'écrivent X^2+Y^2 (qui ne peut être nul que si X=Y=0) bien un ensemble de la forme voulue.
Comme ce sous-espace est de dimension 2, j'ai de gros doutes sur un maximum à 1 (à moins que j'aie mal compris vos commentaires?)
Sachant qu'on peut étendre ce résultat à n'importe quelles matrices nxn avec n pair en faisant des blocs 2x2 sus-mentionnés sur la diagonale (ce qui donne un sous espace de dimension n), je dirais qu'il n'y a pas de maximum.

J'ai dit une connerie?
Je n'en ai pas l'impression.

Elementaire. Multi-imbiter la n-Z scarface polycubique et lui appliquer l'application bi-dérivationnelle de collision fractale de l'opérateur merdouillant Zéta. Le reste est trivial et intuitif : le torscheur collisionnel du mytho-graph fictionnel de Levsourtschorty réduit à sa projection bi-diagonalique sur la matrice elle-même différantiante de Lishphephiyzsckyrscksi et s'apercevoir que son indice fusionnel en structure psychanalytique est aussi multi-imbitable.

Pour le problème des fourmis ("Klyachko's car crash theorem" pour les intimes), l'énoncé original ne posait aucune condition d'intégralité sur le nombre de tours : on demandait juste que, le temps tendant vers l'infini, le nombre de tours parcourus par chaque fourmi soit aussi infini.

La preuve de Klyachko est en effet complètement élémentaire. A tout instant, considérons le graphe orienté dont les sommets sont les centres des faces, et dans lequel une arète joint le sommet correspondant à la face i à celui correspondant à la face j lorsque la fourmi de la face i se trouve à la frontière de la face j. Ainsi, dans ce graphe dual instantané, de chaque sommet part une et une seule arète, et puisque ce graphe est fini, certaines de ces arètes vont former un chemin fermé. Par construction, les fourmis se dirigent alors vers l'intérieur du secteur délimité par ce chemin fermé, de sorte qu'en faisant avancer le temps, lorsqu'une des fourmis passera un sommet, ce chemin fermé se cassera pour reconstruire un chemin délimitant un secteur plus petit, ce qui ne peut durer infiniment.

La preuve que j'avais trouvée se plaçait, elle, dans un cas très particulier, celui où les fourmis font toutes exactement un tour dans un même intervalle de temps donné (ou, ce qui revient au même, en supposant que les trajectoires des fourmis sont périodiques, de même période fondamentale). L'esprit en relève plus de la topologie algébrique. Ca va faire un mois que je m'étais promis (et que j'avais promis à d'autres) de la rédiger proprement, mais je ne l'ai toujours pas fait -- je suis certainement encore pire que David pour ce genre de choses ; j'espère que le fait de faire ce genre de déclarations publiques va finir par m'obliger à m'exécuter.

Je viens de lire la démo à <URL: http://www.maths.warwick.ac.uk/~cpr/ftp/klyachko.ps > (oui, il est 5h, Paris s'éveille, tout ça) et je confirme : c'est élémentaire. Mais tu va quand même avoir un peu de mal à l'expliquer à ta maman…L'idée essentielle, c'est d'introduire le graphe de collision (le sous-graphe du dual du complexe, joignant les centres des faces aux fourmis), et de montrer qu'en fonction du temps, certaines cellules de ce graphe se contractent…

non on peut pas atteindre n !
pour n=3 la dimension maximale est 1 (a verifier)

dans l'idée d'une solution maman-acceptable j'ai pensé à un raisonnement par récurrence (la raison inavouable est que c en gros la seule méthode à ma portée). Avec 2 faces, c'est évidemment impossible. Supposant qu'on a une solution avec n faces et p arêtes, n p minimaux, on pourrait engendrer une solution pour n-1 faces en fusionnant deux d'entre elles ou en en supprimant une. Si les faces n'ont pas plus de 4 côtés, il y a au plus 2 fois plus d'arêtes et il semble (du moins sur le cube) qu'il y ait deux faces dont les fourmis (alors sur deux arêtes contigües) ont "failli" se croiser. Il semble vraisemblable qu'on puisse fusionner ces deux faces et raccorder les trajectoires des deux fourmis. Si on a des faces avec beaucoup de côtés, et qu'à aucun moment les fourmis n'ont failli se croiser, on pourrait peut-être supprimer une arête en fusionnant deux sommets.
Bof, c'est au mieux des maths-fiction…

Et pour l'histoire de la fourmi sur le polyèdre, c'est quoi la solution avec le théorème de l'indice ?

Un indice: le carré de l'hypoténuse. Ca devrait suffire au plus forts

bon en fait c'est trop compliqué pour moi, ça me rassure en un sens …

Ces mots sonnent dans mes oreilles comme un air déjà entendu, comme plusieurs entrées précédentes ;)

Oups j'ai compris ma boulette ;-)
bon alors le majorant est clairement n, peut-on l'atteindre? j'y réfléchis les enfants…

ce que je dirais:
- si on prend toutes les matrices dont la première ligne est nulle, on obtient un espace constitué exclusivement de matrices singulières, et de dimension n^2-n: on a donc déjà un majorant pour la dimension considérée, qui est n.
- si on prend la matrice compagnon A d'un polynôme unitaire de degré n, et l'espace vectoriel engendré par (I,A,…A^(n-1)), on obtient bien un espace de dimension n qui a la bonne propriété, non?
j'avoue que ça fait longtemps que j'ai pas fait d'algèbre linéaire, donc j'ai peut-être dit une connerie (ou plus)…
Ca paraît un peu trop simple pour faire sécher l'élite de la nation ;-)

Au s'couuuuuuuuuuuuuurs Père Doduuuuuuue !

Hé ben c'est pas comme ça qu'on va conserver la médaille fields

Considerons un espace quadratique anisotrope (V,q) de
dimension quelconque sur les reels R. Comme (V,q) est
anisotrope, les elements de V (a part 0)
sont inversibles dans l'algebre de Clifford C(V,q)
ceci dit la dimension en question peut etre arbitraire.

C'est marrant comme question. Bon mettons que ton espace V est de dimension d et composé de matrices n x n. On a d inferieur ou égal à n et on peut peut etre se ramener à d=n? Dans ce cas considérons l'application c_i de V dans R^n qui à M associe la i-ème colonne de M. Les applications c_1 … c_n sont n champs de vecteurs linéairement indépendants sur V\{0}. Ceci dit grosso modo que le fibré tangent de ce truc est parallélisable et il me semble que cela ne se produit que pour n = 2,4 ou 8.

J'ai bien une solution mais la case de la réponse est trop petite pour la contenir.

A qui fais tu allusion Ruxor?