Inscription / Connexion Nouveau Sujet
Deux rois aux trajectoires orthogonales
Bonjour à tous 
J'avais évoqué ce problème à propos des démonstrations dans lesquelles on abusait un peu trop de « il est clair que » , « on voit bien que » , « dans le pire des cas on a » , …
"On considère deux rois sur un échiquier le premier est placé sur une des cases du bord gauche et le deuxième sur une case du bord inférieur . Les mouvements de chacun d'eux se font d'une case vers une case voisine c'est-à-dire partageant un côté avec elle . Le premier roi finit son parcours sur la colonne de droite et le deuxième sur la ligne du haut . Est-on assuré qu'au moins une des cases de l'échiquier ait été visitée par les deux rois ?"
Je reconnais que j'utilise souvent l'artifice que je citais en préambule pour éviter d'avoir à entrer dans tes détails techniques laborieux . J'ai tout de même en mémoire des problèmes comme celui de Jordan ou de l'aiguille de Kakeya qui montrent les limites du procédé .
Pour revenir au problème , la réponse est clairement oui et on peut le montrer avec des outils assez sophistiqués comme l'homotopie ou le théorème de Brouwer , mais peut-on le démontrer proprement avec des outils élémentaires ?
Avis aux amateurs , on s'amuse en laissant le blankage de côté 😊
Imod
Bonsoir Verdurin
Et le deuxième une case par ligne mais en quoi cela entraîne-t-il qu'ils aient traversés la même case ?
Imod
Bonjour,
La trajectoire du roi qui va de gauche à droite sépare l'échiquier en 2 parties non communicantes (puisque passe par une case pour chaque "abscisse"). Cette trajectoire est donc une frontière hermétiquement close entre le haut et le bas de l'échiquier.
L'autre roi démarre d'un coté de la frontière décrite ci-dessus et doit se rendre au final de l'autre coté de cette frontière ... ce qui est donc impossible sans franchir cette frontière, donc sans passer par une case de cette frontière ... qui a été visitée par le 1er roi.
salut
c'est le principes 
ou encore des trois maisons qu'on doit relier chacune à deux réseaux sans croisement
Bonjour à tous les deux
@Candide : L'objectif initial est de trouver une démonstration qui n'utilise pas un artifice pour cacher une difficulté . Si on prend le trajet du premier roi que tu considères , comment définis tu les cases gauches et les cases droites . J'ai l'impression qu'avec des parcours tordus , certaines cases ne pourraient être ni l'une ni l'autre ou les deux .
@Carpediem : Les problèmes sont voisins mais je ne pense pas que celui-ci soit un problème de graphe .
Je suis sans doute trop tatillon mais c'est le cahier des charges que j'ai annoncé au départ 
Imod
Bonjour,
Nous resterons de nouveau en désaccord.
La logique de mon message n'est en rien un artifice pour cacher une difficulté.
En partant du bord gauche de l'échiquier et en bougeant d'une case à la fois, pour atteindre au final le bord droit, on ne peut rien faire d'autre que de passer sur toutes les "abscisses" de l'échiquier (quelles que soient les "ordonnées") et donc former une ligne sans trou (cette de la trajectoire) qui sépare le haut du bas de l'échiquier.
Tout comme un escargot traversant une chaussée unique, en partant d'un coté de la route et en arrivant (en empruntant n'importe quel chemin) de l'autre coté... la trace de l'escargot forme une frontière "sans trou" sur la route, la coupant en 2 zones qu'il est impossible de relier sans passer par la dite frontière formée par la trace.
Ou bien en traçant un trait continu (sans lever le crayon) du bord gauche d'une feuille jusqu'au bord droit, on sépare la feuille en 2 zones (une sous la ligne et une plus haut que le ligne) qu'il est impossible de relier sans passer par la ligne tracée... et ceci que la ligne tracée soit droite ou ait n'importe quelle autre forme.
****
Pour relier par un trait continu (puisque avancée de 1 case à la fois) un point A quelconque du bord gauche à un point B quelconque du bord droit de l'échiquier,
quelle que soit la trajectoire choisie (une en rouge dessinée parmi toutes les possibles), cette ligne trajectoire coupe l'échiquier en 2 parties non communicantes, une partie C de l'échiquier sous la ligne trajectoire et une partie D de l'échiquier au dessus de la ligne trajectoire.
Il est impossible de relier par un trajet continu un point de la zone C et un point de la zone D sans passer sur la ligne trajectoire AB (qui est continue) (et évidemment sans sortir de l'échiquier)
La trajectoire (rouge) peut même passer plusieurs fois sur la même case, cela ne change rien à la conclusion. Il y a toujours une barrière continue entre les zones C et D puisque la trajectoire rouge doit obligatoirement passer, au moins une fois, par des cases occupant au final toutes les abscisses disponibles sur l'échiquier ... et que cette trajectoire est une ligne continue.
@Candide : Sache avant tout bien que je n'ai aucun problème avec les oppositions de points de vue . Tant que les échanges restent courtois et argumentés
Tu résumes le parcours du premier roi à un chemin simple , c'est une évidence ?
Imod
Tu résumes le parcours du premier roi à un chemin simple , c'est une évidence ?
Tu n'as pas lu mon message
"quelle que soit la trajectoire choisie (une en rouge dessinée parmi toutes les possibles ... )"
Et il a été expliqué pourquoi.
@ Candide :J'ai bien compris qu'en passant de gauche à droite le roi devait visiter toutes les abscisses , je me questionnais sur l'évidence d'un chemin simple allant de gauche à droite , c'est une question bête ? On peut bien sûr supprimer des boucles ou des branches inutiles mais aboutit-on nécessairement à un chemin simple ? Sans cet argument les territoires haut et bas n'ont pas vraiment de sens . Si l'existence de la frontière d'une frontière nord-sud est établie , tout coule de source .
Il y a certainement un argument simple qui justifie l'existence de ce chemin et je ne l'ai pas lu dans tes messages .
Imod
un cas plus "concret" peut-être (qui est une simple redite de candide2 auquel je ne vois pas ce qu'on peut rajouter)
on découpe le carré ABCD par une ligne polygonale reliant un point du segment [AB] à un point du segment [CD].
si on veut à nouveau découper (ces deux morceaux de carré) par une ligne polygonale reliant un point du segment [AD], à un point du segment [BC] alors les deux découpes ont (au moins) un point d'intersection.
du point de vu topologique la ligne polygonale AB du dessin de candide2 partage le carré en deux parties de frontière commune la ligne polygonale AB : pour passer d'un pays à un autre il faut alors traverser la frontière ...
Il n'est pas utile de répéter le message de Candide , j'ai posé une question : pour quelle raison existe-t-il un chemin simple allant du bord gauche au bord droit ?
Imod
qu'appelles-tu un chemin simple ?
et c'est toi qui donnes les règles de construction de ce chemin !!
pour répondre à ta question je dirai que la raison est que le carré est connexe donc je peux joindre l'un des bords au bord opposé par une ligne (polygonale) continue (selon ta règle de construction)
En analyse comme en théorie des graphes un chemin simple passe une seule fois par chaque sommet sans jamais se recouper . Sinon tu ne réponds pas vraiment à la question .
Imod
Bonsoir
Par récurrence, on peut montrer que c'est impossible pour tout échiquier de taille nxn.
On initialise à 2x2, il n'y a que 4 trajectoires possibles.
Pour l'hérédité, on envisage la réduction de l'échiquier (n+1)*(n+1) à son sous-échiquier n*n obtenu en supprimant la première ligne et la première colonne, et on écarte les cas dégénérés de trajectoire où le roi initialement situé sur la première colonne resterait toujours sur la première ligne (a1-b1-c1,...) puisqu'il rencontrerait obligatoirement la position de départ de l'autre roi (et vice-versa). On invoque alors l'argument selon lequel les deux rois seront obligés de se déplacer dans le sous-échiquier en question de taille n*n, et la boucle est bouclée, me semble-t-il
L'hérédité en images :
Le roi blanc ne peut pas faire cette trajectoire car il rencontrerait la case de départ du roi noir. (et même raisonnement pour le roi noir)
Par conséquent, les deux rois seront obligés de se retrouver à un moment dans ce carré :
Et on en revient au cas de rang précédent
Remplacer la dernière image de mon précédent message par :
Les mouvements diagonaux ne sont pas autorisés 
Bonjour,je n'ai pas répondu car l'impossibilité est flagrante ,mais
une solution à la Moebius est envisageable .
Une réponse un peu longue à toutes ces interventions
@Zormuche : en fait la propriété reste vraie pour tout échiquier mXn , on peut même considérer un échiquier 1X1 . La démonstration par récurrence me semble plutôt compliquée car même si les deux rois quittent leur ligne et colonne initiale la rencontre peut très bien se faire sur cette ligne ou colonne .
@Dpi : Oui c'est évident comme le théorème de Jordan et on a le droit de ne pas vouloir perdre son temps à le démontrer .
@Tous : l'argument gauche-droite utilisé par Candide est recevable pour un chemin simple car il correspond à des abscisses inférieures ou supérieures à celles du roi montant . L'existence d'une case commune n'est alors rien d'autre que le théorème des valeurs intermédiaires . Si le chemin n'est pas simple , la définition de gauche et droite est moins claire .
Sur le dessin les cases noires ont été atteintes par le roi montant , les rouges sont clairement à gauche et les bleues à droite , c'est bien moins clair pour les blanches .
On peut bien sûr affirmer qu'on peut réduire la zone noire à un chemin simple comme sur le dessin ci-dessous avec la ligne rouge :
Il est clair qu'alors gauches et droites sont parfaitement définies . Il reste tout de même une question dont la réponse est sans doute simple , un tel chemin existe-t-il toujours ?
Sinon on peut aussi prétendre que si le deuxième roi passe en zone blanche , il aura coupé la trajectoire du premier mais on est toujours dans des affirmations non justifiées .
Pour résumer , on n'est pas obligé de jouer si on trouve les règles ridicules mais si accepte de jouer , il faut simplement respecter les règles
Imod
Ce que je voulais dire, c'est que j'écarte ces cas "triviaux" où les deux rois restent sur la colonne/ligne, car la rencontre est inévitable. Mon but est de montrer que pour toutes les trajectoires, il y a rencontre. Je me concentre alors sur les cas où la rencontre n'est pas triviale
Cependant il reste un blocage, les rois peuvent très bien quitter ce carré après la rencontre :
Je reste sur la démonstration de Candide qui laisse tout de même pas mal de blancs
Comment réduire le territoire du roi montant à un chemin simple ? Le territoire est connexe et passe par la ligne du bas , au moins une case de cette ligne est connectée à la ligne juste au dessus . Le domaine reste connexe si on supprime toutes les autres cases de cette ligne . La case restante de la première ligne est connectée à une case de la deuxième . Si cette nouvelle case est connectée à une case de la troisième ligne on continue le procédé , sinon elle est liée à une case de la même ligne qui elle-même va être liée à une nouvelle case de la même ligne ou à une case de la troisième et ainsi de suite jusqu'à ce qu'on trouve une case sur la troisième ligne . On supprime ensuite toutes les cases de la deuxième ligne qui n'ont pas été impliquées dans l'affaire et on construit ainsi de proche en proche un chemin allant de la première à la dernière ligne . Sur chaque ligne , ce qu'il reste du domaine se réduit à un segment d'au moins une case donc en ajoutant au besoin une colonne de chaque côté on aura deux domaines avec des cases gauches et des cases droites . Le deuxième roi partant de la gauche ( on peut exprimer ça avec les abscisses des cases ) va devoir passer à droite et traverser une ligne continue allant du bas vers le haut . Ce n'est rien d'autre que le théorème des valeurs intermédiaires .
Imod
Annuler
connectez vous