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
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).
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.
scelerat a écrit:J'aurais colorie non 2 mais 3 zones dans l'echiquier
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.
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
ffpower a écrit:Je comprend pas trop.A quoi correspondent les 5 faces?
Patastronch a écrit:Si ton graphe comporte 4 sommets il est forcément planaire.
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
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 19 invités
Tu pars déja ?
Identification
Pas encore inscrit ?
Ou identifiez-vous :