Chemins sur un échiquier

[Ben314]

Bon, ça fait au moins 4 fois que je le dit : un "chemin de la théorie des graphes", ça n'a RIEN A VOIR avec ce qu'on appele un chemin sur une feuille de papier : un graphe, c'est un objet purement algébrique : c'est la donnée de deux types d'objects que l'on appelle "sommets" et "arrêtes" mais les sommets ne sont absolument pas des "points du plan" (ou d'un autre espace) et les arrêtes ne sont absolument pas des courbes continues ou quoi que ce soit d'autre de représentable sur une feuille de papier !!!
Donc, si tu veut, tu peut utiliser la théorie des graphes, mais il faut commencer par préciser quel est l'ensemble des "sommet" et celui des "arrêtes"

[beagle]

je ne cherche pas forcément la théorie des graphes.
j'ai transformé le chemin de la pièce d'échec qui fait des boucles qui revient sur des cases,
en un chemin plus simple tel que la ligne du haut ne repasse plus comme frontière avec la surface bas du fait de tous les ziguiguis qui font tourner en s'entortillant les lignes.

bref j'ai deux lignes, une sup en frontière uniquement avec la surface haut,
l'autre ligne est en contact uniquement avec la surface bas
ces deux lignes parallèles en ligne brisée sans croisements
partent de gauche et arrivent à droite

donc trois surfaces haut:H
la surface C entre les deux lignes
la surface B en bas.

[Ben314]

bref j'ai deux lignes, une sup en frontière uniquement avec la surface haut,
l'autre ligne est en contact uniquement avec la surface bas

De nouveau, tu parle de surface "du haut" et de surface "du bas" alors que... tu n'as toujours pas démontré que ce ne sont pas les mêmes...

[beagle]

J'ai transformé le chemin biscornu en un chemin simple à une case d'épaisseur,

la surface C dite de la courbe est délimitée par deux lignes, une ligne dite sup et une ligne dite inf

la ligne dite supérieure est dessinée en rouge, elle commence avec le sommet de la case de départ,
tant que l'on va vers la droite en ligne droite la ligne rouge est dessus,
quand on monte elle est à gauche
quand on va en ligne droite vers la gauche elle est en dessous
quand on descend la ligne rouge est à droite

lors de la dernière case qui est une marche vers la droite, elle est au-dessus

c'est l'inverse pour la ligne verte dite du bas.

[Ben314]

J'ai transformé le chemin biscornu en un chemin simple à une case d'épaisseur,

la surface C dite de la courbe est délimitée par deux lignes, une ligne dite sup et une ligne dite inf

la ligne dite supérieure est dessinée en rouge, elle commence avec le sommet de la case de départ,
tant que l'on va vers la droite en ligne droite la ligne rouge est dessus,
quand on monte elle est à gauche
quand on va en ligne droite vers la gauche elle est en dessous
quand on descend la ligne rouge est à droite

lors de la dernière case qui est une marche vers la droite, elle est au-dessus

c'est l'inverse pour la ligne verte dite du bas.

Tout à fait O.K. mais je ne vois pas en quoi ça prouve que l'on ne peut pas aller du "dessus" au "dessous" sans couper la ligne.

[fatal_error]

@fatal_error : si j'ai bien suivi tu as une notion de "courbe qui sépare un rectangle de hauteur h en deux", tu dis que quand h=2 ça marche, puis tu fais une récurrence.
Je crois pas avoir vu de moment où tu expliquais, pendant l'étape de récurrence, comment à partir d'un chemin horizontal dans un rectangle de hauteur (h+1) tentant de traverser le chemin infranchissable, tu obtenais un chemin horizontal dans le sous-rectangle de hauteur h pour pouvoir appliquer l'hypothèse de récurrence. Ou alors tu l'as fait mais j'ai rien compris ?

en fait c'est une courbe horizontale qui sépare un rectangle de largeur h en deux (c'est pareil, mais je précise pour qu'on manipule la même chose). Je prends h pour largeur car on confonds l et 1, réflexe d'informaticien...dsl.

L'idée de ma récur, c'est de dire : pour un rectangle de largeur h, tout chemin reliant le bord gauche au bord droit est infranchissable.
A l'hérédité, tout chemin reliant le bord gauche au bord droit se décompose en un chemin reliant le bord gauche au bord avant le bord droit + un chemin de se bord au bord droit. et apres j'applique la récurr sur le premier terme décomposé, et la définition pour le deuxieme chemin décomposé.

Je n'ai pas montré l'existence d'un chemin du bord gauche au bord avant le bord droit pour la décomposition. En revanche on peut montrer assez facilement que si chaque case du damier est un sommet et les arrete les relation entre sommets, alors le graphe est connexe et toute case du damier atteignable. Il existe donc un chemin quelconque reliant deux cases dans le rectangle de largeur h (pour la récurrence), l'une au bord gauche, l'autre au bord h.

[beagle]

Tout à fait O.K. mais je ne vois pas en quoi ça prouve que l'on ne peut pas aller du "dessus" au "dessous" sans couper la ligne.

Il est fort ce Ben, il est fort.
Arrivé à ce stade là,
c'est de la flotte qu'il y a sur les bords, c'est plus facile à comprendre et super mathématiques à faire rèver Ben.
bref à ce stade là, je décomprime le ressort de ma ligne brisée.
rotation de 90° pour les branches montantes, par rotations adéquates
ce qui amène cette ligne brisée en ligne droite,
la ligne rouge supérieure est au-dessus la verte en dessous
maintenant en ligne droite,
l'eau des bords rouges si elle était capable de passer un angle rouge pourrait passer la ligne drite rouge par la mème fuite,
ou alors c'est l'inverse, l'eau des bords quand c'est déplié en ligne droite ne pouvant pas passer, elle le peut encore moins-pareil quand c'est enveloppé-replié.
ça c'est des maths propres!!!!

[Doraki]

@fatal_error

Tu as donc le pion 1 qui va par exemple de gauche à droite dans un rectangle de largeur h,
et tu veux montrer par récurrence sur h que pour tous les rectangles, tout chemin "horizontal" du pion 1 du bord gauche au bord droit est "infranchissable", c'est à dire que pour tout chemin "vertical" du pion 2 du bord haut au bord bas qui est compris dans ce rectangle, les deux chemins s'intersectent ?

En fait je crois que c'est dans ta preuve de P2, qu'il manque des détails.

Tu dis que si on a un chemin horizontal infranchissable dans un rectangle de largeur p, (x0,1)....(xn,p)
et qu'on prolonge le chemin en (x0,1)...(xn,p)(xn,p+1), on obtient un chemin horizontal infranchissable dans un rectangle de largeur (p+1).

Pour montrer que le chemin est infranchissable, tu dois dire "prenons un chemin vertical dans le rectangle de largeur (p+1) et montrons qu'il intersecte (x0,1)....(xn,p)(xn,p+1)".
Ensuite, tu dis "(x0,1)...(xn,p) est infranchissable donc seul (xn,p)(xn,p+1) peut être franchi", ce qui n'est pas très compréhensible. (même pas du tout).

J'arrive pas du tout à donner un sens à "peut être franchi" qui ferait marcher ta phrase.

Et pour revenir à mon problème, la définition de "(x0,1)...(xn,p) est infranchissable" parle de chemins verticaux dans le sous-rectangle de largeur p, tandis que la définition de "(x0,1)...(xn,p)(xn,p+1) est infranchissable" parle de chemins verticaux dans le rectangle de largeur (p+1).

Bon si ton chemin vertical ne passe pas par la colonne (p+1) alors il intersecte (x0,1)...(xn,p) donc on a fini, mais si il passe par la colonne (p+1), il faut détailler comment tu trouves qu'il intersecte (x0,1)...(xn,p)(xn+1,p)
Et j'ai pas l'impression que ce soit très facile.

En fait c'est même carrément faux si on retire l'hypothèse "(x0,1)...(xn,p)" est un chemin, tout en gardant le fait que ce soit une partie infranchissable du rectangle de largeur p. Donc si tu ne comptes pas utiliser le fait que c'est un chemin, t'as perdu.
Donc il faudra au moins refaire une récurrence, et au final, si t'arrives à quelquechose, ce sera plutôt alambiqué (2 récurrences imbriquées sur le même objet :/)

[vincentroumezy]

Personne ne sait si ma démonsteation est valide ?

[Imod]

Oups : j'ai mélangé deux problèmes , on oublie :cry:

Imod

[Ben314]

Je ne suis toujours pas convaincu que ça aide vraiment :
Sur ton graphe, on suprime le sommet en plein milieux et on considère qu'il y a deux "grandes" arrêtes passant à cet endroit là l'une par dessous l'autre.
Pour ce nouveau graphe, le résultat est faux.
Peut tu en terme de graphe me dire quel différence il y a avec le graphe de départ ?

[Doraki]

La tentative de fatal_error m'a fait penser à une autre preuve plutôt simple :

On prend un rectangle a*b,
On prend un chemin (x0,y0)....(xn,yn) avec y0=1 et yn=b
On prend un chemin (x'0,y'0)....(x'm,y'm) avec x'0=1 et x'm=a.
On convient que x'(-1) = 0 et x'(m+1) = a+1.

On montre par récurrence sur k que :
Ou bien il existe i dans {0..k} et j dans {0..m} tels que (xi,yi) = (x'j,y'j)
Ou bien il existe j1<=j2 dans {0..m} tels que x'(j1-1) = xk-1, x'(j2+1) = xk+1, et
pour tout j dans {j1...j2}, x'j = xk et y'j > yk.
(ou non exclusif)


Un lemme bien utile, également utilisé dans ma première preuve, dit que si on a une suite d'entiers
(a1,a2,...,an), tels que |ak+1 - ak| <= 1, et si on a un a tel que a1 < a < an, alors il existe une sous-suite (ak,ak+1,ak+2...,ak') de la forme (a-1,a,a....a,a+1)

[nodjim]

On a accepté l'idée d'un territoire unique construit par 1 pion qui se déplace selon un chemin totalement arbitraire d'une face à l'autre. Cette seule assertion ne suffit elle pas à montrer que l'échiquier est coupé en deux ?
Si on fait passer de l'eau par ce territoire, le chemin existe, il a été tracé par le pion, donc un courant d'eau est possible, donc le plan est bien coupé en 2. Où est le problème?

[Doraki]

C'est au moins la 50ème fois que tu poses cette question.

Le problème a été posé dans un cadre arithmétique précis.
Tant que tu refuses de décrire ton raisonnement avec ce cadre arithmétique, (par exemple tu pourrais essayer de donner une définition arithmétique de "être coupé en deux", puis essayer de prouver correctement que en effet c'est ce qui arrive, puis montrer pourquoi "avoir été coupé en deux" => le pion 2 va croiser la trajectoire du pion 1), tu ne parles pas du même problème que nous.

C'est un problème d'arithmétique, qu'on pourrait (si on voulait) traduire en une propriété sur des entiers.
On veut donc une preuve d'arithmétique pour montrer un résultat d'arithmétique.

Si on en trouve une, c'est bien.
Si on en trouve pas, ça donnerait un énoncé "vrai" mais indémontrable, qu'on pourrait ajouter à l'arithmétique de Peano pour obtenir un système plus puissant.

[nodjim]

C'est au moins la 50ème fois que tu poses cette question.

Je sais. Je tente à chaque fois de donner une image aussi frappante que possible. J'essaye maintenant avec un courant d'eau: Comment peut on admettre que si une rivière, même aussi tortueuse soit elle, si elle rentre par une face et sort par l'autre, ne coupe pas le plan en 2, et qu'on n'aura pas besoin d'un pont pour la franchir ? Il y a la rive droite et la rive gauche. Les terres de la rive droite ne peuvent être en contact avec les terres de la rive gauche. ça me dépasse qu'on s'interroge sur cette banalité.

[Doraki]

Si on refuse ton argument, ce n'est pas parcequ'il n'est pas clair ou qu'on ne le comprend pas.
C'est que ce n'est pas de l'arithmétique.

Ce n'est pas en donnant une image différente de la même chose, frappante ou pas, qui fasse couler de l'eau, de l'encre ou je ne sais quoi, avec des pays, des frontières, des douanes ou des ponts, qui va y changer quelquechose.

[beagle]

Le beagle continue, il est sur une piste.

Or donc , nous en étions à avoir fabriqué un chemin plus propre que celui de la pièce intiale,
décrit quelques posts au-dessus:

Une bande espace de la courbe=C,
limitée toujours en haut quand on va de gauche à droite
limitée à gauche pour monter
limitée en bas pour aller de droite à gauche
limitée à droite pour descendre
par une ligne rouge
et ligne verte délimite la bande de l'autre coté.

snif, snif le beagle
Pour sortir d'un zigouigui donné et espérer progresser, on montre que pour toute colonne k:
on traverse-rencontre un nombre impair de bande C, de lignes rouge, de lignes vertes
ce faisant une pièce descendant de par le haut tombera toujours sur une rouge en premier.

Si la pièce se décide à contourner ce rouge,
elle le fera vers la gauche ou vers la droite,
en contournant la bande rouge par la gauche, elle sera toujours à contres courant du circuit,
et c'est retour à la case de départ au-dessus du point rouge E.
si la pièce veut contourner par la droite,
elle sera dans le sens du circuit , et sera ramenée au point d'arrivée juste au-dessus du point G rouge

Donc je pars d'un point M sur le bord supérieur de l'échiquier, je descend la colonne, je tombe sur un point rouge M' de la ligne rouge.
A partir de là il faut un peu d'habileté, la main gauche va suivre par le coté gauche le tracé, sans lever le doigt, elle arrivera au bord gauche de l'échiquier sans mauvaise rencontre, elle remontera la partie supérieure du bord gauche de l'échiquier, elle partira à droite en direction du point M.Un doigt de la main droite connecté au départ au doigt gauche en M' va suivre le tracé vers la droite et finalement arriver au bord droit de l'échiquier sans avoir fait de mauvaise rencontre, le doigt droit remonte la partie supérieure du bord droit de l'échiquier, tourne en haut à gauche pour suivre le bord supérieur de l'échiquier.Il suffit maintenant de synchroniser les deux doigts pour qu'ils arrivent en mème temps au point M. On dit que les doigts ont connecté une surface connexe.
Les doigts reprennent un travail ordinaire (pour l'oreille ou le nez).

[beagle]

Deuxième solution tirée d'un article de Friedmann(1).
dans cet article Friedmann démontre pourquoi si on prend un matelat gonflable qui ne prend pas l'eau lorsqu'il est gonflé,
ne prend pas l'eau non plus lorsqu'on le dégonfle et qu'on le plie de multiples façons.
Il fait l'hypothèse que la valve est bien refermée dans les deux cas de figure,cause fréquente de maladresse, étourderie au niveau de la connexité.
C'est assez marrant et effectivement peu de gens avant lui avaient ouvert au cutter l'intérieur d'un matelat dégonflé trempé dans l'eau.
Je ne vous met pas la démonstration qui est assez hardue.

Mais l'article en question commence par la ligne droite (segment)connexée à, et il montre que la ligne droite lorsqu'on la brise en ligne brisée simple conserve la connexité.
De façon schématique, je vous épargne les calculs de Friedmann,
une ligne brisée non sécante est connecté à ...,
Un coté de la ligne brisée est rouge, l'autre coté est bleu.
Pour casser la connexité, interrompre la ligne rouge par du bleu,
il faut prendre un bout très pointu bleu,
par de nouveaux pliages l'amener au contact de la ligne brisée,
taper sur la ligne brisée, ce qui enfonce le bout pointu,
alors la ligne brisée contient un morceau de bleu, la connexité est perdue.

Ce qui est typiquement le cas de cet exo depuis le début.Enfin depuis le moment où l'on sait savoir transformer un chemin complexe en un chemin simple en ligne brisée non sécante.

(1)Friedmman JJ, Beagle JM, coherence of the inflatable matelet,
last review of maths, 2012,2508-2732, (en cours de publication)

[nodjim]

Finalement c'est ce problème, à résolution évidente, qui permet de résoudre celui ci:
Soit A un nombre de valeur 1+nk qui doit atteindre la valeur n(j+1) 0Soit B un nombre de valeur x comprise entre 1 et n qui doit atteindre la valeur n(n-1)+ y comprise entre 1 à n.
A et B passent d'une valeur à l'autre par (+ ou - n) ou (+ ou -1). A et B doivent toujours rester positifs.
La suite des nombres pour que A atteigne son objectif est SA.
La suite des nombres pour que B atteigne son objectif est SB.

Montrer que les suites SA et SB comportent au moins un nombre égal.

A tout prendre, je préfère me servir du modèle de l'échiquier pour prouver le problème arithmétique que l'inverse!

[beagle]

"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"

Doraki,
je ne vois pas dans l'énoncé qu'il soit exigé une preuve arithmétique,
et depuis le début avec nodjim on cherche à savoir quel "chemin" est accepté comme coupant en deux un échiquier.
Toi et Ben nous dites aucun chemin continu ne sera preuve de ...
OK, dont acte.
Et bravo aussi à votre façon de faire.Mème si cela me passe au-dessus de la tète.C'est pas parce que je suis pas assez costaud que vous avez tort.

Et je ne suis pas convaincu de la réponse de Ben disant qu'une démonstration par théorie des graphes serait acceptable, dans les conditions d'exigence que vous fixez toi et Ben.