Chemins sur un échiquier

Olympiades mathématiques, énigmes et défis
ffpower
Membre Complexe
Messages: 2542
Enregistré le: 13 Déc 2007, 06:25

Chemins sur un échiquier

par ffpower » 09 Jan 2008, 16:56

On a un échiquier carré de n*n cases. Deux pions se baladent sur cet échiquier, sachant qu'un pion peut se déplacer d'une case a une case adjacente (mais pas en diagonale). On suppose qu'un pion part du côté gauche de l'échiquier et après s'être balader sur celui ci se retrouve du coté droit. Le deuxième pion part du côté haut et finit sur le côté bas. Montrer que les deux pions vont forcément passer sur une même case (pas forcément en même temps). Ca semble évident, mais je n'ai jamais réussi à le prouver. Ma joie serait immense si quelqu'un trouvait une solution (bon j'exagère peut-être un tout petit peu^^). En tout cas bonne chance!



Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 09 Jan 2008, 17:32

ffpower a écrit:On a un échequier carré de n*n cases. 2 pions se baladent sur cet echequier,sachant qu un pion peut se déplacer d une case a une case adjaçante(mais pas en diagonale).On suppose qu un pion part du coté gauche de l échequier et apres s etre balader sur celui ci se retrouve du coté droit.Le 2eme pion par du coté haut et finit au coté bas.Montrer que les 2 pions vont forcément passer sur une meme case(pas forcément en meme temps).Ca semble évident,mais j ai jamais réussi a le prouver.Ma joie serait immense si qqun trouvait une solution(bon j exagere p-e un tout petit peu^^).En tout cas bonne chance


Doit y avoir quelque chose qui m'echappe.

Le premier pion est sur la ligne i. Il va donc passer par les cases (i,j) pour tout j<9.
Le second pion est sur la colonne k. Il va donc passer par les cases (l,k) pour tout l<9.

comme k<9, le premier pion passe par la case (i,k)
comme i<9, le second pion passe par la case (i,k).

Vu que tu as l'air ded dire qu'il y aquelque chose de compliqué a démontrer, y a surment quelque chose que j'ai aps du capter.

Au passage, on dit un échiquier. Pas un échéquier.

ThSQ
Membre Complexe
Messages: 2077
Enregistré le: 10 Oct 2007, 19:40

par ThSQ » 09 Jan 2008, 17:38

C'est une histoire de connexité (par arc en l'occurrence) : le premier pion va créer au moins deux composantes connexes dont l'une contient le forcément le bord du bas. Après on peut appliquer le "théorème du passage des douanes" : le chemin de l'autre pion rencontre forcément la frontière d'une des composantes crées par l'autre.

ffpower
Membre Complexe
Messages: 2542
Enregistré le: 13 Déc 2007, 06:25

par ffpower » 09 Jan 2008, 20:42

Patastronch:on dirait que tu as l impression que un pion se balade sur une ligne et l autre sur une colonne.Ce n est pas le cas,ils peuvent faire un chemin.Un pion sur la case (i,j) peut aller en (i-1,j),(i+1,j);(i,j-1),(i,j+1).

C est effectivement une sorte de probleme de connexité,mais c est pas evident de montrer que le 1er pion va séparer 2 composantes connexes(d ailleurs,c est pas vrai si le pion passe par toutes les cases)

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 09 Jan 2008, 20:45

ffpower a écrit:Patastronch:on dirait que tu as l impression que un pion se balade sur une ligne et l autre sur une colonne.Ce n est pas le cas,ils peuvent faire un chemin.Un pion sur la case (i,j) peut aller en (i-1,j),(i+1,j);(i,j-1),(i,j+1).



En effet c est ce que j'ai cru. Je savais bien que quelque chose m'échappait !

Imod
Habitué(e)
Messages: 6474
Enregistré le: 12 Sep 2006, 13:00

par Imod » 09 Jan 2008, 20:46

D'accord pour un argument de connexité mais mon côté coincé trouve un peu légère l'explication ci-dessus :hein:

Imod

scelerat
Membre Relatif
Messages: 397
Enregistré le: 03 Aoû 2005, 15:37

par scelerat » 10 Jan 2008, 13:09

ThSQ a écrit:C'est une histoire de connexité (par arc en l'occurrence) : le premier pion va créer au moins deux composantes connexes dont l'une contient le forcément le bord du bas. Après on peut appliquer le "théorème du passage des douanes" : le chemin de l'autre pion rencontre forcément la frontière d'une des composantes crées par l'autre.

J'aurais colorie non 2 mais 3 zones dans l'echiquier : les cases visitees par le premier pion, puis les deux zones de part et d'autre de celle-ci. L'important est que la zone des cases visitees par le premier pion a une "epaisseur" d'au moins une case partout, donc qu'on ne peut la traverser sans y poser le pied (pardon, le pion).

ThSQ
Membre Complexe
Messages: 2077
Enregistré le: 10 Oct 2007, 19:40

par ThSQ » 10 Jan 2008, 19:27

Imod a écrit:D'accord pour un argument de connexité mais mon côté coincé trouve un peu légère l'explication ci-dessus :hein:

Imod


C'est pas vraiment une explication (encore moins une preuve) juste quelques idées jetées à la vas-vite !

scelerat
Membre Relatif
Messages: 397
Enregistré le: 03 Aoû 2005, 15:37

par scelerat » 11 Jan 2008, 15:52

scelerat a écrit:J'aurais colorie non 2 mais 3 zones dans l'echiquier

Je vais expliciter un peu.
Je prends le pion qui va de bas en haut ou de haut en bas. Je colorie en bleu toutes les cases qu'il parcourt. Ensuite, je colorie en rouge toutes les cases qui sont a l'interieur du polygone delimite par le cote gauche, eventuellement les parties necessaires des cotes superieurs et inferieurs, et la frontiere bleue, en vert toutes celles interieures au polygone delimite de meme avec le cote droit. Il est aise de demontrer qu'une case rouge ne peut etre adjacente qu'a un bord, une autre case rouge et/ou une case bleue, donc qu'il n'est pas possible de passer le pion directement d'une case rouge a une case verte.

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 11 Jan 2008, 17:25

scelerat a écrit:Je vais expliciter un peu.
Je prends le pion qui va de bas en haut ou de haut en bas. Je colorie en bleu toutes les cases qu'il parcourt. Ensuite, je colorie en rouge toutes les cases qui sont a l'interieur du polygone delimite par le cote gauche, eventuellement les parties necessaires des cotes superieurs et inferieurs, et la frontiere bleue, en vert toutes celles interieures au polygone delimite de meme avec le cote droit. Il est aise de demontrer qu'une case rouge ne peut etre adjacente qu'a un bord, une autre case rouge et/ou une case bleue, donc qu'il n'est pas possible de passer le pion directement d'une case rouge a une case verte.

Non il peut y a voir des cases rouge adjacente a une case verte :

Si le pion fait une boucle alors les cases à lexterieur de la boucle, dans au moins l'une des zones formées, sont et rouge et vertes si j'ai bien compris ton coloriage.

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 11 Jan 2008, 17:30

Ah non j'ai rien dit. J'avais comrpis que a gauche de la ligne bleu c 'etait rouge et a sa droite c'etait vert.

Je retire ma remarque :)

Imod
Habitué(e)
Messages: 6474
Enregistré le: 12 Sep 2006, 13:00

par Imod » 11 Jan 2008, 19:37

A la réflexion il s'agit plutôt d'un problème de graphe comme celui des trois maisons que l'on doit raccorder au circuit d'eau gaz et électricité .
En supposant par l'absurde que l'on peut relier haut et bas ainsi que gauche et droite sans que les raccords se croisent on obtient un graphe planaire à 4 sommets ( H , B , G et D ), 6 arêtes et 5 faces ce qui contredit la formule d'Euler : s+f-a=2 .

Imod

ffpower
Membre Complexe
Messages: 2542
Enregistré le: 13 Déc 2007, 06:25

par ffpower » 11 Jan 2008, 19:55

Je comprend pas trop.A quoi correspondent les 5 faces?

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 11 Jan 2008, 20:09

Imod a écrit:A la réflexion il s'agit plutôt d'un problème de graphe comme celui des trois maisons que l'on doit raccorder au circuit d'eau gaz et électricité .
En supposant par l'absurde que l'on peut relier haut et bas ainsi que gauche et droite sans que les raccords se croisent on obtient un graphe planaire à 4 sommets ( H , B , G et D ), 6 arêtes et 5 faces ce qui contredit la formule d'Euler : s+f-a=2 .

Imod


Le graphe que tu construis est planaire, je comprends pas comment tu trouves 5 faces.

Par contre tu as raison on peut se servir de cette idée .

Si on modélise le probleme sous forme d'un graphe :
Image

Alors rejoindre H et B et rejoindre G et D reviens a construire un graphe contenant un sous-graphe isomorphe partiel a K3,3 donc non planaire.

Rappel du théoreme utilisé : Theoreme de Kuratowski => Un graphe est planaire si et seulement si il ne contient pas de sous-graphe partiel isomorphe a K3,3 et k5

Imod
Habitué(e)
Messages: 6474
Enregistré le: 12 Sep 2006, 13:00

par Imod » 11 Jan 2008, 20:18

ffpower a écrit:Je comprend pas trop.A quoi correspondent les 5 faces?

Si on suppose l'existence des deux chemins , on schématise l'échiquier par quatre points G , D , H et B représentant les extrémités des chemins . Alors de chaque sommet partent trois arêtes dont deux suivent les bords de l'échiquier et la troisième l'un des chemins précédents . Par exemple le sommet H peut être relié à G et D en suivant les bords et à B en suivant le chemin H à B . On obtient en tout cinq faces : HBD , BDG , BHG , HGD et une face illimitée ( ce qui se pratique usuellement en théorie des graphes ) .

Imod

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 11 Jan 2008, 20:25

Si ton graphe comporte 4 sommets il est forcément planaire.

Pour qu'un graphe ne soit pas planaire faut qu'il contienne un K3,3 ou un K5 soit respectivement 6 et 5 sommets. Donc tous graphes possedant moins de 5 sommets est forcément planaire !

Imod
Habitué(e)
Messages: 6474
Enregistré le: 12 Sep 2006, 13:00

par Imod » 11 Jan 2008, 20:40

Patastronch a écrit:Si ton graphe comporte 4 sommets il est forcément planaire.

D'accord :marteau: les graphes ne font pas partis de ma culture mathématiques et je ne suis pas du tout à l'aise avec leur vocabulaire , un jour il faudra que je m'y mette car ça a l'air passionnant ( et en plein essor ) .

Imod

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 11 Jan 2008, 20:43

D'ailleur je fais la moral sur le planaire, mais le mien ne semble pas planaire en fait. J'ai pas de sous-graphe isomorphe partiel a K3,3 , je suis allé trop vite. Mon graphe ne prouve donc rien du tout.

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 11 Jan 2008, 20:47

Imod a écrit:D'accord :marteau: les graphes ne font pas partis de ma culture mathématiques et je ne suis pas du tout à l'aise avec leur vocabulaire , un jour il faudra que je m'y mette car ça a l'air passionnant ( et en plein essor ) .

Imod

Si c est sur le K3,3 et K5 que tu bloques ca veut juste dire :

K3,3 => graphe des maisons, c est a dire 2 groupes de 3 sommets ou chaque sommet d'un groupe possede une arrete vers tous les sommets de l'autre groupe.

K5 => graphe complet a 5 sommet.

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 11 Jan 2008, 21:21

C'est bon le graphe est bien non planaire :

le théoreme de Kuratowski est en fait :
Un graphe est non planaire si et seulement si il contient un sous-graphe homéomorphe à K3,3 ou K5

et non isomorphe comme ce que j'ai énoncé plus haut !

Or mon graphe contien bien un sous-graphe homéomorphe a K3,3.

Si on considere le graphe K3,3 suivant avec comme premier groupe :

CoinHautDroit H et G
et comme second groupe CoinBasGauche B et D.

Alors si on remplace l'arrete CoinHautDroit-CoinBasGauche par la chaine CoinHautDroit-CoinHautGauche-CoinBasGauche, on retrouve bien un sous-graphe de mon graphe. Donc il contien un sous-graphe homéomorphe a K3,3 !

Le dernier point est l'assurance que ce graphe modélise bien le probleme voulu. Mais ca me semble assez evident avec l'isomorphisme proposé.

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 8 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite