Chemins sur un échiquier

[Ben314]

Quand je dit que "tu peut utiliser la théorie des graphes", cela vient simplement du fait que je ne considère pas dans un tel problème que tel ou tel outil soit interdit : tu peut utiliser ce que tu veut comme théorie.
Bien sûr, il faut si possible éviter d'utiliser un gros théorème qui demande des pages de démonstrations mais je ne pense pas que tu trouve dans la théorie des graphes de "gros théorème" qui rende le problème trivial...

[beagle]

OK, possible, mais qu'une surface connexe soit reliée d'un point à un autre et que cela divise cette surface en deux, il me semble que si cela n'est pas admis, certains exemples de théorie des graphes me semblent remis en question, les gars ne se gènent pas pour compter les surfaces , les arètes et les sommets,
sur ce que j'ai vu,le gars met le doigt dans les surfaces et compte,1,2,3,4 il dit j'ai 4 surfaces et pas 5
m'enfin c'est uniquement d'après ce que j'ai aperçu.

Sinon, Ben avec mon dernier truc de ligne rouge, ça passe ou pas?

[Doraki]

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) 0<j,k<n.
Soit 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!

Comme ça ?

n=5,j=2,k=3,x=2,y=2

SA = 16, 15
SB = 2, 7, 12, 17, 22

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.

Ah, ça c'est bien, c'est quelque chose qu'on PEUT montrer proprement colonne par colonne en faisant une récurrence.

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.

il dit "ça paraît évident" parcequ'il sait depuis le début que tout le monde dira en premier "un chemin de haut en bas coupe le truc en deux", mais que c'est un raisonnement intraduisible tel quel dans le langage échiquier/case/chemin de cases.
S'il pose la question c'est qu'il n'accepte pas ce raisonnement vague pas formalisé.

[nodjim]

Comme ça ?

n=5,j=2,k=3,x=2,y=2

SA = 16, 15
SB = 2, 7, 12, 17, 22

J'ai été eu, là.
ça devrait aller mieux comme ça:
On part d'un couple A de nombres (1,y) qui doit arriver à (n,y') avec 1<=y,y'<=n. C'est la suite A.
et du couple B(x,1) qui doit arriver à (x',n) avec 1<=x,x'<=n. C'est la suite B.
le 1er ou 2ème nb du couple peut varier de + ou -1, sans jamais être négatif ni nul, ni dépasser n. On ne peut faire varier qu'un seul nombre du couple à la fois.
Montrer que dans ces 2 suites, il existe un couple identique.

Et donc je dis que c'est facile à résoudre par le biais de l'échiquier. Sinon..

[Doraki]

T'as juste recopié le premier post quoi.
Donc le théorème de l'échiquier tu le poses comme axiome de ta théorie de l'arithmétique ?

[nodjim]

Bien, alors, je t'accorde le droit de passer sur comment on prolonge la ligne bord par bord, et sur le fait qu'elle finisse par boucler vu qu'on fait tourner un algo qui a un nombre fini d'états.
J'imagine que la frontière a le droit de passer par les bords de l'échiquier.

Quel est exactement ton point de départ ? Tu prends deux cases C1 et C2 les plus "éloignées" du territoire, et tu prends un bord B de C1 qui est encore plus "éloignée" de C2 ?
Comment tu vas faire pour prouver que ce que tu obtiens est indépendant de ton choix de (C1,C2,B) ?
Genre ne serait-ce qu'en échangeant C1 et C2, il est pas du tout évident qu'on va obtenir la même "frontière extérieure".

C1 et C2 font partie du territoire. Ce sont les 2 cases les plus éloignées l'une de l'autre dans le territoire. C'est juste une définition pour distinguer frontière extérieure et frontières intérieures. Le pt de départ est C1 ou C2, on s'en fout un peu. Si on part de C1, on passera de toute façon par C2 et vice versa. Ce sont 2 cases de la frontière extérieure.

[nodjim]

T'as juste recopié le premier post quoi.
Donc le théorème de l'échiquier tu le poses comme axiome de ta théorie de l'arithmétique ?

ben oui, pour résoudre ce problème là.

[ffpower]

Ah bah c'est sur que si tu met la conclusion comme axiome, de suite ça aide :langue2:

[beagle]

doraki:"il dit "ça paraît évident" parcequ'il sait depuis le début que tout le monde dira en premier "un chemin de haut en bas coupe le truc en deux", mais que c'est un raisonnement intraduisible tel quel dans le langage échiquier/case/chemin de cases."

c'est là qu'on ne se comprend pas depuis un bout de temps, enfin ça va mieux merci,
mais
la ligne continue qui va d'un bord à l'autre est très mathématiquement faisable, c'est une case collée à la case suivante par un segment commun,
et il n' y a que des lignes droites
la continuité=l'infranchassibilité de la ligne droite est bien définissable
et des angles droits,
là aussi l'infranchissabilité est bien définie

Donc il y a une courbe continue d'épaisseur 1 case d'un coté à l'autre.

mais c'est bien le fait qu'une courbe continue d'un bord à l'autre divise en deux surfaces que vous n'acceptez pas comme posé.OK, mais je disais par exemple une démonstration par théorie des graphes remonterait-elle assez en arrière comme régression de ce qui est supposé connu ou non?

Bon et ma ligne rouge connexe, ça peut marcher bien rédigé?

[nodjim]

En géométrie, et c'est dans notre culture, qui dira que le visuel est à jeter aux orties ?
Or c'est une réponse visuelle évidente qui est avancée.
Dans mon jeune temps, on abordait la théorie des ensembles par les patates, on mettait des croix dedans ou dehors, on mettait des croix dans les ensembles communs, on voyait tout de suite les unions, les intersections, etc.. Je continue de m'en servir ça marche très bien.
Et maintenant, on me dit, ah ben non, une surface coupe en deux un plan, mais tu ne prouves pas qu'une ligne qui va passer de part et d'autre ne traverse pas cette surface. J'ai même bien du mal à écrire la contradiction sans faire de pléonasme.
Allez expliquer ça à des enfants, je crois que vous allez en traumatiser beaucoup.

[Ben314]

En géométrie, et c'est dans notre culture, qui dira que le visuel est à jeter aux orties ?
Or c'est une réponse visuelle évidente qui est avancée.
Dans mon jeune temps, on abordait la théorie des ensembles par les patates, on mettait des croix dedans ou dehors, on mettait des croix dans les ensembles communs, on voyait tout de suite les unions, les intersections, etc.. Je continue de m'en servir ça marche très bien.
Et maintenant, on me dit, ah ben non, une surface coupe en deux un plan, mais tu ne prouves pas qu'une ligne qui va passer de part et d'autre ne traverse pas cette surface. J'ai même bien du mal à écrire la contradiction sans faire de pléonasme.
Allez expliquer ça à des enfants, je crois que vous allez en traumatiser beaucoup.

Ici, on est dans le forum "énigme" qui, c'est le moins qu'on puisse dire, n'est pas à vocation "pédagogique".
Sinon, le fond du problème c'est de savoir si on peut faire des maths axiomatisées en se fiant à son intuition. La réponse est non : on ne risque pas de se fier à son intuition concernant par exemple la découpe d'une boule qui donne deux boules de même taille, pas plus que sur les questions de cardinalité des ensembles infinis ou concernant la courbe de Peano.
On peut répondre "je ne veut pas faire de maths axiomatisées" pour continuer à pouvoir raisonner "à l'intuition".
Sauf que l'histoire (des math) a montré que cette position est "intenable" : on obtient assez rapidement des trucs à la fois vrais et faux.
En résumé, les math, c'est de l'intuition ET du formalisme. Par exemple les patates avec des croix dedans, ça c'est le coté intuition (indispensable) mais, principalement dans le cas d'ensembles infinis, ça ne constitue clairement pas une preuve (pas assez "formel")...

[ffpower]

Le visuel n'est pas à jeter car il donne souvent des idées de démarches de preuves. Mais il ne donne pas de preuves..

Et si tu résolvais un exercice de théo des ensembles juste en utilisant des patates, je te dirais la même chose

[nodjim]

Ce n'est pas de l'intuition c'est du dessin. L'intuition c'est: je soupçonne que ce n'est pas possible, qu'il faut un croisement. Je montre qu'un pion crée un ensemble connexe, je l'ai fait, je n'y reviens pas. Je dessine un ensemble dans le carré qui s'étend de gauche à droite. Cet ensemble coupe le plan en 3, car il a 2 lignes indépendantes qui vont de bout en bout. Et là je vois qu'il n'est pas possible de faire un second ensemble connexe qui ira de haut en bas sans intersecter le 1er ensemble.
Je vois pas trop où est l'intuition là dedans. Même si je reconnais que ce n'est pas formel.

[Doraki]

C1 et C2 font partie du territoire. Ce sont les 2 cases les plus éloignées l'une de l'autre dans le territoire. C'est juste une définition pour distinguer frontière extérieure et frontières intérieures. Le pt de départ est C1 ou C2, on s'en fout un peu. Si on part de C1, on passera de toute façon par C2 et vice versa. Ce sont 2 cases de la frontière extérieure.

Je le redis, ce n'est pas évident que C1 et C2 sont sur la même frontière.

Toutes les frontières forment des boucles, et y'en a un nombre fini, ok.

Tu pourrais définir une frontière extérieure comme une frontière dont le diamètre (sup de la distance entre 2 bords compris dans la frontière) est maximal.
Ou alors définir une frontière extérieure comme une frontière de périmètre maximal (edit : nan cette définition-là elle marche pas).

Mais même avec ces définitions, il reste à prouver qu'il y'en a qu'une seule, ce qui demande du travail (je sais pas si c'est infaisable ou juste très dur), et puis il reste à utiliser ce concept proprement dans la suite de la preuve pour montrer que les deux trajectoires s'intersectent.
D'ailleurs pour l'instant j'vois pas en quoi ça aide de savoir qu'il y a une "frontière extérieure" (quoi que ça veuille dire) et quelles en sont les propriétés importantes que tu vas utiliser.

Tant que tu raisonnes vaguement sur un dessin, tu risques systématiquement d'utiliser le fait que le théorème est vrai d'une manière ou d'une autre, plus ou moins cachée comme une "évidence" dans ce que tu dis.
Le dessin aide souvent pour guider une preuve, oui.
Mais parfois (cet exercice en étant l'exemple archétypal), un dessin va te dire quelquechose de hautement non trivial et il pourra pas t'aider.

[nodjim]

Je comprendrai quand on me dira: ton dessin n'est pas bon parce que ceci ou cela. Tu n'es pas sûr et certain que...Mais un dessin, s'il est bon, ne peut être remis en cause.
Et la démo qui va avec.

[Ben314]

Je comprendrai quand on me dira: ton dessin n'est pas bon parce que ceci ou cela. Tu n'es pas sûr et certain que...Mais un dessin, s'il est bon, ne peut être remis en cause.
Et la démo qui va avec.

Est tu vraiment sûr qu'UN SEUL dessin va te suffire pour englober tout les trajets possible de droite à gauche ?
Perso, si tu fait tout les dessins possibles de trajet droite/gauche et que, sur chaque dessin, tu matérialise en rouge et vert les zones "au dessus" et "en dessous" du trajet pour vérifier que ce n'est pas la même zone, effectivement, j'accepterais ça comme une "VRAI" preuve (certe un peu longue...)

[Doraki]

Ton problème c'est que t'as un axiome personnel qui dit "tout ce que moi je vois sur un dessin est vrai".
Et nous on ne peut pas l'utiliser pour plusieurs raison :
- on n'est pas toi
- "voir sur un dessin" est un truc absolument pas défini.

En quelque sorte, t'as un oracle dont tu sors plein d'énoncés et tu décides qu'il sont vrais.

Il faut que j'invente un dessin qui te fasse montrer un truc faux ?

Il est possible que l'argument de théorie des graphes donné en page 1 te convienne et que les graphes planaires sont ce qu'il faut pour nous formaliser un peu le genre de trucs que tu "vois sur un dessin".

Mais, pour justifier proprement le fait que K3,3 n'est pas un graphe planaire (le problème des 3 maisons à relier à 3 machins), on est ramené au point de départ et je soupçonne très fort qu'il faut utiliser le théorème de jordan.

[nodjim]

Est tu vraiment sûr qu'UN SEUL dessin va te suffire pour englober tout les trajets possible de droite à gauche ?
Perso, si tu fait tout les dessins possibles de trajet droite/gauche et que, sur chaque dessin, tu matérialise en rouge et vert les zones "au dessus" et "en dessous" du trajet pour vérifier que ce n'est pas la même zone, effectivement, j'accepterais ça comme une "VRAI" preuve (certe un peu longue...)

On n'est pas obligé de faire un dessin pour tous les cas. 1 ligne découpe le plan en 2, dans l'un de ces plans, une autre ligne découpe une nouvelle fois le plan. Les 2 lignes ne se croisent pas puisqu'elles sont issues d'une surface connexe. La propriété de coupure du plan est là quelle que soit la forme de la ligne.

[ffpower]

Unraisonnement encore et toujours à base d'assertions injustifiées..

[nodjim]

Un raisonnement encore et toujours à base d'assertions injustifiées..

Laquelle ? les 2 lignes de part et d'autre de la connexe ? le fait qu'elles ne se coupent pas ? ou le fait que ça marche pour n'importe quelle config ?