Merci pour l'illustration !

Tiens, pour le c, il y aurait pas un problème pour la méthode exposée dans le cas suivant ?

XXXXX
XNNNX
XNNNX
XNNDX
XXXXD

titoufred a écrit:

Tiens, pour le c, il y aurait pas un problème pour la méthode exposée dans le cas suivant ?

XXXXX
XNNNX
XNNNX
XNNDX
XXXXD

Il y a en effet un problème , il semble impossible dans cette situation de raccorder un chemin à l'intérieur du carré central à un parcours sur la couronne extérieure .

On peut quand même s'en sortir en considérant un carré NXN coincé dans l'angle opposé aux deux cases incriminées .

Je vais essayer d'illustrer ça

Vasimolo

@Vasimolo
Merci pour tes schémas illustrant la récurrence et surtout d'avoir "sauvé" cette solution qui commencait à avoir du plomb dans l'aile

@nodgim
Si je pars sur un rectangle de 3 x K (K impair et supérieur à 3), j'arrive à démontrer que ça marche pour tout rectangle (3+2N)x(K+2N), donc finalement pour tout rectangle impair x impair

Vasimolo a écrit:

Voilà

En ajoutant toutes les vaguelettes nécessaires pour atteindre le coin en bas à gauche du carré vert .

Vasimolo

Bien joué !

Quoiqu'il en soit on passera toujours de la case 1 à la case 2 (idem pour les autres qui sont voisines) . Donc il parait facile de de passer d'un rectangle impair à un autre  de largeur ou de longueur +2

Oui donc si on choisit deux cases quelles qu'elles soient, on peut toujours ramener ç au problème avec 2 lignes de moins... Il suffit de choisir où on met les deux lignes en rab et de constater qu'elles ne changent rien au parcours.

J'ai juste négligé le cas où on considère les deux lignes en rab une en haut et l'autre en bas... Mais le principe est le même. Le passage de 3x à 5x5 est particulier ... Mais au delà, il est toujours possible d'exclure deux ligne du problème et de le ramener au cas  (-2 lignes) ou (-2 colonnes)



En oubliant les lignes 2 et 3, puis 5 et 6  , puis les colonnes 2 et 3 on en revient au cas 3x3.

Pour la récurrence 3XN->3X(N+2)

a) Les deux cases sont sont dans le "supplément" 3X2 :


b) Une case dans chaque morceau :


c) Les deux cases sont dans le bloc 3XN :

Il suffit d'ajouter une boucle s'appuyant sur deux cases voisines liées ( par récurrence ) dans le chemin initial .


Vasimolo

J'avais posé cette question sur le rectancle impair*impair car la démo que j'ai présentée (quelque peu tombée dans l'oubli..) le prouve de fait.

C'est tout à ton honneur, Vasimomo, d'avoir tenté de comprendre ma démo, elle est simple en fait mais assez longue à expliquer.

Pour le cas particulier de la ligne unique, dans le cas d'un pion en haut ou en bas, j'ai bien envie de proposer dans ce cas là la rotation d'un quart de tour de l'échiquier dès le début de la démo. Qu'en penses tu ?

Ne nous plaignons pas ça aurait pu être Vasilomo

Vasimolo

Bonjour,
La démonstration de nodgim me semble très astucieuse.
Dans le cas où un des 2 pions est situé sur le bord inférieur ou supérieur, on pourrait effectivement tourner l'échiquier d'un quart de tour. Si le problème persiste (ce qui signifie que ce pion est dans un angle de l'échiquier), alors on se contentera d'un découpage en 3 rectangles (au lieu de 5). Une autre solution consisterait à "forcer" la dimension minimale d'un rectangle à 3 unités.
De même si les 2 pions sont situés sur des cases voisines (en diagonale), alors on ferait un découpage en 4 rectangles (le n°5 serait "dégénéré").
Une soucis survient peut-être quand on a le cas de figure émanant de titoufred, qui avait d'ailleurs déjà mis la récurrence en difficulté:
XXXXX
XXXXX
XXXXX
XXXDX
XXXXD
Bonne soirée.
Frank

Franky1103 a écrit:

XXXXX
XXXXX
XXXXX
XXXDX
XXXXD

Dans ce cas particulier, où même la rotation ne résout pas le problème: Le D dans l'angle est envoyé à gauche (balaye donc le rect 1*5) et celui au dessus remonte tout en haut en balayant les colonnes 4 et 5. Reste alors un rectangle tjs i*p résolvable.

J'ai fait dans ma démo des déplacements tjs identiques pour simplifier, mais du coup pour des cas particuliers comme celui ci je suis obligé de faire autrement. Je vais réfléchir à une stratégie plus générale qui prendra en compte tous les cas de figure. ça risque d'être plus abstrait....