Chemins sur un échiquier

Olympiades mathématiques, énigmes et défis
Benjamin
Modérateur
Messages: 2337
Enregistré le: 14 Avr 2008, 12:00

par Benjamin » 11 Nov 2010, 21:07

Imod a écrit:J'ai pas trop de temps , je pars au volley mais je crois que j'ai une démo qui tient la route . On considère la trajectoire complet d'un pion ( en blanc ) . Le deuxième pion doit passer du territoire rouge au bleu , comme ces deux territoires n'ont pas de point commun il faut passer par la bande blanche .

Image

Imod

Ce n'explique pas pourquoi ça ne marche plus quand on peut marcher en diagonale (ie que dans ce cas, on peut passer d'un territoire à l'autre alors qu'ils n'ont rien en commun, pourquoi ça devient faux quand on ne se déplace plus en diagonale ? J'avoue que j'ai du mal avec ça).



vincentroumezy
Membre Irrationnel
Messages: 1363
Enregistré le: 19 Juil 2010, 13:00

par vincentroumezy » 11 Nov 2010, 21:13

Si o considère qu'un con appartient à ses deux cotés adjacents, on peut dire que si les daux pions vont l'un du coté gauche au coin inférieur droit, et l'autre du coté haut b=vers ce meme coin décriront des courbes qui peuvent ne pas se couper.

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

par Imod » 11 Nov 2010, 21:24

En fait les deux zones n'ont pas de point de contact ( j'ai changé dans le message précédent ) or le déplacement d'un pion se fait toujours entre deux cases ayant un côté commun il faut donc bien passer par la zone blanche .

Imod

PS : volley annulé faute de combattants :zen:

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 11 Nov 2010, 22:00

Mais comment tu sais que tu peux colorier en 2 couleurs distinctes sans qu'elles se rentrent en contact ?

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 11 Nov 2010, 22:07

Doraki a écrit:Mais comment tu sais que tu peux colorier en 2 couleurs distinctes sans qu'elles se rentrent en contact ?
Je dirait même plus (Dupond-Dupont) : quel "algorithme" utilise tu pour colorier (par exemple) en rouge et comment prouve tu que le rouge ne "déborde pas" sur le coté droit ?

Je "reprend" Doraki surtout pour ajouter (ce que sa modestie lui interdit de mettre lui même) que pour répondre "carré" à la question "pourquoi le rouge ne déborde pas de l'autre coté", ben le plus simple (pour le moment), c'est la méthode "Doraki"...

P.S. Bon, OK, je faillote un peu...
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

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

par Imod » 11 Nov 2010, 22:11

Ce qui est sûr ( facilement démontrable ) c'est qu'il n'y a pas un côté de case coloré en bleu d'un côté et en rouge de l'autre . Le pion en descendant enlève une case à chaque niveau et ça suffit pour conclure car le pion se déplaçant horizontalement doit passer de la zone rouge à la la zone bleue par un côté de case .

Sauf erreur :zen:

Imod

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 11 Nov 2010, 22:25

Ben, comme c'est la seconde fois que je vois le verbe "faillote" tapé de ta main, et qui, phonétiquement, a l'air de vouloir dire "fayote", qui signifie "...fais du zèle", ce que le contexte confirme, je me permets cette petite digression amicale afin que, si les circonstances aidant, tu aies à écrire à nouveau ce vocable familier, tu puisses l'orthographier sans faute. Cela dit, ça ne retire rien à tes brillantes interventions, et je ne fayote pas en le disant.

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 11 Nov 2010, 22:28

Imod a écrit:Ce qui est sûr ( facilement démontrable ) c'est qu'il n'y a pas un côté de case coloré en bleu d'un côté et en rouge de l'autre . Le pion en descendant enlève une case à chaque niveau et ça suffit pour conclure car le pion se déplaçant horizontalement doit passer de la zone rouge à la la zone bleue par un côté de case .

Sauf erreur :zen:

Imod

ça alors, on va finir par me donner raison! Imod, tu n'as pas le droit de dire "ce qui est sûr.." car c'est synonyme de "il est évident que..".
Ah, mais....

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

par Imod » 11 Nov 2010, 23:54

Je n'ai pas voulu être trop formel mais le pion descendant crée un territoire connexe de largeur au moins 1 ( en blanc ) . On ne peut donc passer du territoire rouge au bleu au rouge sans mettre un pied dans le blanc , pour moi c'est 100% rigoureux , mais bon , à chacun sa vision :we:

Imod

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 12 Nov 2010, 00:08

Le mieux pour ne pas avoir de dire "c'est évident" ou "pour moi c'est 100% rigoureux", c'est de faire la preuve dans un assistant de preuve.

Qui est volontaire ?

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 12 Nov 2010, 00:57

Imod a écrit:Je n'ai pas voulu être trop formel mais le pion descendant crée un territoire connexe de largeur au moins 1 ( en blanc ) . On ne peut donc passer du territoire rouge au bleu au rouge sans mettre un pied dans le blanc , pour moi c'est 100% rigoureux , mais bon , à chacun sa vision
En ce qui me concerne, je trouve que ce n'est qu'une façon légèrement différente de reformuler le problème de départ : ce que tu affirme, c'est que le "rouge" ne peut pas aller de gauche à droite sans couper le blanc, ce qui n'est pas trés différent du problème initial...

@Doraki : c'est quoi un "assistant de preuve"

@nodjim : je peut essayer de me souvenir quelque temps que "fayot", c'est avec un 'y' et pas avec un 'i' et deux 'l', mais, d'expérience, je sais que ce genre de truc, dans ma cervelle de piaf, ça s'envole assez vite... :cry:
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

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

par Imod » 12 Nov 2010, 01:04

Bon je ne vais pas trop insister parce que cette "querelle" est de peu d'intérêt . Le pion descendant doit passer par toutes les niveaux , il crée donc une chaîne "verticale" de largeur au moins 1 ( la largeur d'une case ) . Pour passer de gauche à droite , le pion "horizontal" va traverser la zone frontière blanche en une case et comme la largeur de la chaîne est au moins 1 ...

Pour moi c'est très clair mais à chacun sa vision et s'il faut retourner aux axiomes fondateurs , il faudrait aussi définir ce qu'est un échiquier , sans moi :we:

Imod

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 12 Nov 2010, 01:23

Le problème est que le pion qui "descend" peu trés bien remonter pour ensuite redescendre, etc.
Cela signifie que, si tu considère une ligne donnée, elle commence par du rouge, puis il y a une case blanche, mais il n'est pas du tout exclu qu'il y ait d'autre case rouges plus loin sur la droite.
En fait la preuve de Doraki repose sur le fait que, si on retrouve du rouge plus loin sur cette ligne, il faudra avoir "passé" un nombre pair de fois la ligne blanche (en comptant de façon astucieuse le nombre de "passages") alors que, sur l'ensemble de la ligne, il y a un nombre impair de "passage" et c'est ce qui prouve que l'autre coté ne peut pas être rouge lui aussi.
La petite difficulté réside dans le fait de définir proprement ce que l'on compte quand on compte les "passages" de la ligne blanche.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

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

par Imod » 12 Nov 2010, 01:29

J'ai bien compris mais moi je préfère considérer le territoire balayé par la pièce descendante et ses frontières gauche et droite , la trajectoire de la pièce ne m'intéresse que dans le sens ou elle traverse l'échiquier de part en part .

Imod

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 12 Nov 2010, 12:47

On arrive donc à cette question délicate: quels sont les axiomes de base qu'on peut poser pour ce problème ? Par exemple, si je dis que la trace d'un pion est continue, parce qu'il avance d'une case à la fois, est ce admis par tous ?

vincentroumezy
Membre Irrationnel
Messages: 1363
Enregistré le: 19 Juil 2010, 13:00

par vincentroumezy » 12 Nov 2010, 19:59

Dans le but de répondre à la question initiale, je pense qu'il ne faut pas se perdre dans un excès de formalisme, pour ne pas écrire 300 pages pour démontrer que 1+1=2.

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 12 Nov 2010, 21:19

Dans la mesure où ffpower donne une formalisation bien précise du problème avec un "ça a l'air évident mais j'ai pas de vraie preuve", il s'attend à une preuve que tu pourrais prouver à quelqu'un d'aveugle qui vivrait dans un monde à 1 dimension, sur lequel l'argument "bah la trajectoire d'un pion elle coupe l'échiquier en au moins 2 parties c'est évident" n'est pas valable.

Si on souhaite formaliser cette "évidence" on est tenté de dire
"bah on colorie une case libre en rouge, puis on colorie toutes ses voisines libres en rouge et ainsi de suite".
L'ennui c'est que ça prouve pas que ça colorie pas toutes les cases, et cet algorithme n'apporte en fait absolument rien vu qu'il faut prouver exactement la même chose qu'avant : pour dire qu'il y a une case qui n'est pas coloriée en rouge, il faut dire qu'il faut trouver 2 cases telles qu'il n'y a pas de chemin qui les relie.
Si vous êtes tenté de dire que vous restez du même coté de la courbe, bah c'est justement le problème vu que "coté" n'est pas défini.

Tout l'intérêt du problème est de trouver un moyen de faire ce coloriage avec un algorithme dont on PEUT prouver de manière élémentaire qu'il va marcher.

L'algo intuitif "colorier la composante connexe d'une case libre choisie au départ", il est très complexe vu qu'il fait une induction sur les chemins à partir de cette case. De manière équivalente, la définition de composante connexe, prise telle quelle, ne permet pas de résoudre le problème.

En contrepartie, l'algo que j'ai proposé est plus simple vu qu'il ne fait qu'une induction sur x pour colorier. D'où le fait qu'il soit plus simple à étudier et à montrer qu'il marche (compatible avec la notion de composante connexe, et utilise au moins 2 couleurs distinctes)


Pour Ben, un assistant de preuve c'est un programme qui t'aide (pas ou peu) à écrire une preuve formelle puis la vérifie. (et qui peut extraire des prorgammes à partir des preuves, c'est cool)
Genre Coq, développé à l'inria. Je te laisse googler pour voir ce que c'est et ce qu'on a déjà formalisé dedans (genre théorème des 4 couleurs, théorème fondamental de l'algèbre...)

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

par ffpower » 15 Nov 2010, 18:57

Bonjour,
Pardon pour mon absence ce week end durant ce débat, j'étais occupé ( et je viens de voir que plein d'exos ont été posé et que j'ai tout loupé..sigh ). Bref, pour en revenir à :

nodjim a écrit:On arrive donc à cette question délicate: quels sont les axiomes de base qu'on peut poser pour ce problème ? Par exemple, si je dis que la trace d'un pion est continue, parce qu'il avance d'une case à la fois, est ce admis par tous ?


Je propose maintenant une formulation mathématique précise du probleme :

Notations:
- et sont les projections canoniques de
-est la distance sur définie par

Enoncé :
Soit R un entier strictement positif, et 2 suites finies d'éléments de vérifiant :
-Pour tout i entre 0 et m-1, et pour tout j entre 0 et n-1,
-, , ,
Montrer l'existence de , tels que

Ainsi l'énoncé est maintenant purement arithmétique, donc le but est d'obtenir une démonstration purement arithmétique. Donc que des additions, soustractions, reccurences, ect..( en gros ca revient probablement à travailler dans l'axiomatique de Peano, même si je m'y connais pas bien )
Ainsi, comme l'a dit Doraki, il faut une démo pour aveugle. On peut évidemment parler en termes géométriques afin de rendre la démo plus visuelle, et que tout formaliser deviendrait vite trop lourd, mais en gardant en tête que pour chaque propriété géométrique utilisée il faut savoir en faire une démo arithmétique.

Sinon, j'ai une idée de preuve prometteuse, dont l'approche est assez différente de celle de Doraki. J'écris l'esquisse de preuve dans un post ulterieur afin de ne pas trop encombrer celui ci..

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 15 Nov 2010, 19:41

Ben314 a écrit:...Je sais pas si j'ai pas un poly à la fac assez bien fait...
Bon, désolé : je suis à la fac et j'ai rien sous format informatique en topo algébrique...
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

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

par ffpower » 15 Nov 2010, 20:45

Donc voilà mon plan de demo :
Je pars de et comme dans l'énoncé en supposant de plus que et sont injectives, que commence et finit sur la même verticale( ), et que commence et finit sur la même horizontale (). Il est facile de se ramener à ce cas.

Je dirai que est un demitour de longueur b-a de si , et , et .ou si on la même chose en remplacant par .. ( autrement dit, et sont des coins consécutifs ou le chemin tourne 2 fois dans la meme direction ).

Supposons maintenant que et ne se croisent pas. Si et ne sont pas tous 2 des lignes droites ( cas trivial ), il y a forcément des demis tours effectués. J'en choisis un de longueur minimale, disons . On constate alors qu'entre les points et , il n'y a aucun point de ni de , car ceci impliquerait l'existence d'un demi tour de longueur plus petite. Du coup, on peut construire un nouveau chemin , identique à , sauf qu'au lieu de tourner en puis en , on tourne en puis en . Ainsi et vérifie encore les mêmes hypotheses, et est plus court que ( de 2 cases ). Donc en itérant le procédé, on finit par se ramener au cas trivial des 2 droites..

PS : c'est dans ce genre de situation que je regrette de ne pas savoir maitriser d'outils de dessins comme vous. J'espere que vous arriverez quand même à suivre la démarche..

EDIT :
Ben314 a écrit:Bon, désolé : je suis à la fac et j'ai rien sous format informatique en topo algébrique...

Pas bien grave, merci quand même..Le lien que tu m'as passé me va de toute facon très bien pour l'instant..

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 14 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