Forum de mathématiques - Bibm@th.net

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Des araignées et des hommes ...

Une petite énigme que me posa un ami il y a quelques années :

Sur un mur se trouve 5 trous, disposés de façon quelconque, et autant d'araignées.
A cet instant, chaque trou est occupé par une araignée.
A midi, au zénith, chaque araignée change de place et se rend dans le trou le plus proche ;

Question : à chaque mouvement, tous les trous sont ils remplis d'araignées ?

Dernière modification par freddy (18-04-2009 11:32:09)

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 348

Re : Des araignées et des hommes ...

Salut,

  Je crois que j'ai une configuration où ca ne marche pas....

Fred.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Des araignées et des hommes ...

Je reformule : est il possible qu'à chaque mouvement, aucun trou ne soit vide ?

Dernière modification par freddy (18-04-2009 18:57:04)

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Des araignées et des hommes ...

Question subsidiare : et si il y avait 6 trous et 6 araignées ?

Barbichu

Membre actif

Inscription : 15-12-2007

Messages : 405

Re : Des araignées et des hommes ...

Salut,
Pour, 5 trous, je peux prouver que c'est impossible.
Pour 6 trous, la configuration où on a 3 paires de trous séparés par une distance suffisamment grande (ie strictement supérieure à chacune des distances qui séparent les 2 trous de chaque paire) convient.
++

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Des araignées et des hommes ...

Bonjour Barbichu,

j'achète la démonstration !

Barbichu

Membre actif

Inscription : 15-12-2007

Messages : 405

Re : Des araignées et des hommes ...

Hello,

Méthode longue mais sans pré-requis.
====================
supposons qu'il existe une configuration telle qu'à chaque moment aucun trou ne soit vide (H0)

I/ Montrons que pour tout trou A, il existe exactement un trou B tel que la distance AB soit minimale.
Supposons le contraire, il existe donc un trou A, tel qu'il y ait au moins deux trous à distance minimale. (H1)
Comme la configuration est telle qu'après le zenith, aucun trou soit vide (par H0), cela signifie qu'il y aura exactement une araignée par trou. L'araignée située dans le trou A ira donc dans un trou, noté B, et y sera seule. Par hypothèse H1, il existe C tel que AB = AC. L'araignée originellement logée dans A pourrait très bien aller dans C, ce qui laisserait le trou B vide. Contradiction : cette configuration n'est pas valide.

Rq : on utilisera désormais I/ implicitement dans la suite, chaque fois qu'on dira que X est le point le plus proche de Y.

II/ Montrons que: pour tout trou A, si B est le trou le plus proche de A, alors A est le trou le plus proche de B.
Par l'absurde, supposons qu'il existe A et B tel que :
* (H2) B est le trou le plus proche de A,
* (H2') A n'est pas le trou le plus proche de B.
Il existe donc, par (H2')  un trou C, tel que BC < AB (noté (I1))

L'araignée dans A ira dans B, celle dans B ira dans C.
Comme la configuration est correcte, il existe un trou X, tel que l'araignée dans X ira dans A, ie tel que :
(H2'') A est le trou le plus proche de X.

Par (H2'') et (H2') on sait que X n'est pas B.
Par (H2) on sait alors que AB<AX (noté (I2))

Il y a deux cas:
* Soit X=C, par (H2'') on sait que AX<XB (noté I3) et alors AB<AC (I2), AC<CB (I3) et  BC<AB (I1)
   ==> contradiction
* Soit X!=C, par (H2'') on sait que AX<XC (noté (I3')) et alors AB<AX (I2), AX<XC (I3'), et BC<AB (I1)
  ce qui donne : BC<XC, autrement dit l'araignée qui part de C n'ira pas dans X. Celle de A et B non plus. Il existe donc D, tel que l'araignée dans D aille dans X, et la seule possibilité pour que D ne se retrouve pas vide est que celle de C aille dans D. Les araignées suivent donc le circuit A -> B -> C -> D -> X -> A.
Cela signifie que AX<XD<DC<CB<AB, donc AX<AB, contradiction avec (I2)

III/
1/ Prenons un trou quelconque, notons le A et notons B le trou le plus proche de A. Par II/ A est aussi le plus proche de B.
2/ Soit C un trou distinct de A et B, et D le trou le plus proche de C, D est donc distinct de C. Par II/ C est le trou le plus proche de D, donc D n'est ni A ni B. Donc D est distinct de A B et C.
3/ On a un dernier trou E, soit X le trou le plus proche de E. Comme il n'y a que 5 trous, X est forcement A, B, C ou D. Mais par II/ le trou le plus proche de X est E. Or le trou le plus proche de A, B C ou D n'est jamais E.
=> Contradiction.

Conclusion : il n'y a pas de configuration qui convienne.
====================

On peut raccourcir beaucoup le raisonnement en utilisant ses connaissances sur les permutations :
Il suffit de remarquer que I/ rend unique le déplacement des araignées pour une configuration donnée. De plus le fait que la configuration soit correcte fait que ce déplacement est une permutation. On connait le théorème de décomposition des permutations en cycles. Il n'y a pas de 1-cycles car une araignée doit se déplacer. Et il suffit de montrer que lorsqu'on a un k-cycle avec k>2, on a une incohérence (facile : on a une suite d'inégalités strictes). Ainsi cette permutation ne peut être constituée que de 2-cycles, ce qui n'est pas possible pour [tex]\mathfrak{S}_5[/tex]

Cette dernière méthode est d'ailleurs généralisable au cas de  [tex]\mathfrak{S}_{n}[/tex] et permet de montrer que si n impair, on n'a pas de solution, et d'exhiber une solution dans le cas où n est pair.

Bon allez, je retourne bosser.

++

Dernière modification par Barbichu (21-04-2009 13:20:39)

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Des araignées et des hommes ...

Très fort Babichu ... Et chapeau bas pour la qualité de la démonstration.

Perso, je m'étais dit que,  sauf à disposer les 5 points sur un pentagogne, dans tous les autres cas, il y avait sûrement deux araignées dans le même trou  ... et donc un trou vide !

Du coup, avec 6 araignées et 6 trous, je suis sûr qu'elle permutent  toujours entre elles.

++

PS : je fais le lien entre ce petit sujet et celui des 100 matheux avec les 100 coffres, puisqu'on est en face du même problème de permutation circulaire, à ceci près qu'il faut dénombrer toutes celles qui concourrent à maintenir nos matheux vivants !

Dernière modification par freddy (22-04-2009 11:39:48)