Un chemin de tour

[Patastronch]

Oula qu'il est horrible ce problème !

Bon j'ai trouvé une maniere de paver mais j'ai encore aucune piste pour prouver que ca marche dans tous les cas.

L'idée est simple, il suffit de compter le nombre de bloc dans chaque colonne.
Exemple pour :
On a un bloc dans la premiere colonne (de taille 3), un dans la seconde (de taille 1), un dans la troisieme (de taille 3) et un dans la derniere (de taille 1).

Cas 1 : Si ce nombre de bloc est inferieur ou égal à n alors il est toujours possible de paver verticalement avec n pieces le territoire (en effet, si il y a moins de n blocs, alors il suffit de découper en plusieurs blocs les blocs de taille plus grande ou égale à 2 qui existent necessairement puisque la taille moyenne des blocs et de 2)
Cas 2 :
Si jamais le nombre de bloc est strictement supérieur à n alors on fait pivoter de 90 degré ce territoire et cette fois (conjecture) en rééffectuant le comptage des blocs par colonne on en obtiens quoiqu'il arrive un nombre inferieur à n et on se retrouve dans le premier cas.
Retour sur l'exemple : APres pivotement (ou en comptant les bloc horizontalement) on aurait 2 blocs (de taille A) dans la premiere colonne, un bloc (de taille 4) dans la seconde et 2 blocs (de taille 1) dans la troisieme colonne.

En fait voila la propriété (que je conjecture pour le moment) qu'on a selon moi et qui inspire mon pavage :
S'il existe un pavage alors il en existe un qui ne fait intervenir que des rectangles dans le meme sens (les rectangles d'une case sont dans le sens qui nous arrange). En d'autre terme, si on a un pavage possible alors on peut toujours le transformer en un pavage avec uniquement de pieces horizontale (ou verticale le cas échéant).

[Imod]

Je crois que tu conjectures bien , il n'y a plus qu'à prouver :hein: :hein:

Imod

PS : je donnerai un indice si personne ne trouve , mais ça m'étonnerais beaucoup :zen:

[Patastronch]

Bon, je me lance, pour démontrer que soit en comptant les blocs horizontalement (somme Sh) soit verticalement (somme Sv) au moins un des comptages est inférieur ou égale a n, il suffit de prouver que Sh+Sv=2n-1 (propriété élémentaire de la théorie des graphes pour assurer la connexité), on aura bien Sh+Sv Sh+Sv=3. Une frontière commune A=1, on a donc bien Sh+Sv=4.

n->n+1 : On ajoute 2 cases a un territoire de 2n cases. Quand on ajoute une
case on a plusieurs cas possible :

1/Création d'une unique frontière => Dans ce cas on augmente Sh+Sv de 1 et on augmente A de 1, on augmente donc la somme Sh+Sv+A de 2.

2/Création de deux frontières (parallèles ou perpendiculaires) => laisse inchangée la somme Sh+Sv et augmente A de 2, on augmente donc la somme Sh+Sv+A de 2.

3/Création de trois frontières => réduit la somme Sh+Sv de 1 et augmente A de 3, on augmente donc la somme Sh+Sv+A de 2.

4/Création de quatre frontières => réduit la somme Sh+Sv de 2 et augmente A de 4, on augmente donc la somme Sh+Sv+A de 2.

Donc dans tous les cas l'ajout d'une case à un territoire augmente Sh+Sv+A de 2 ! Comme on ajoute 2 cases en passant de n à n+1, on a bien ce qu'on désirait : Sh+Sv+A=4n


Voila, je sais pas si j'ai été assez clair, j'ignore si je suis passé par des cas inutile et si on pouvait pas faire plus simple mais en tous ca a l'air de marcher !!

[Imod]

Tout cela a l'air correct Patastronch :++:

On peut simplifier la récurrence , en faisant l'économie de si on remarque qu'on peut conserver la connexité de l'ensemble en retirant une case bien choisie du territoire et que ( le nombre de cases du territoire ) .

J'adore ces problèmes sur lesquels on n'a si peu de prise !!!

Imod

[Patastronch]

Ce problème me fait penser a celui du pavage par cube d'une certaine manière, dans le sens où le résultat qu'on cherche est très intuitif, on sait donc où on veut aller, on ressent pourquoi c'est vrai, mais des qu'il faut le prouver ça deviens un véritable casse-tête !

Bon maintenant, en tant que fan, je propose qu' Imod nous propose sa solution miracle (contenu en une unique figure comme d'habitude) !

[Imod]

Je te la proposerai dès demain ( pas à 00h00 !!! ) , ainsi qu'à Alpha et aux autres intéressés . Je n'ai pas trouvé de solution qui me fasse vraiment jubiler alors si un noctambule peut faire mieux d'ici là ...

Imod

[Imod]

Une autre solution avec pratiquement la même idée mais sans le de Patastronch .

On remarque d'abord que si est connexe ( au sens d'une promenade de tour ) , on peut trouver une case de telle que reste connexe . Pour cela on pose la tour sur une case quelconque de et on la déplace de case en case sans jamais sortir du territoire ni repasser par une case déjà visitée . En retirant du territoire la case d'arrivée de la tour on conserve un territoire connexe .



Sur la figure le territoire est constitué de l'ensemble des cases coloriées . On pose la tour sur la case verte et on garde un territoire connexe en retirant la case bleue ou la case rouge .

Maintenant par récurrence sur ( pair ou impair ) le nombre de cases du territoire , on a . Si est pair ou et c'est fini .

Imod

[Alpha]

On remarque d'abord que si est connexe ( au sens d'une promenade de tour ) , on peut trouver une case de telle que reste connexe .

Et dire que j'ai eu cette idée à un moment au début de mes recherches (je voulais justement faire une récurrence). Enfin j'avais pas trouvé de démonstration satisfaisante de ce fait (que le territoire reste connexe si on lui enlève une certaine case). Et puis là j'ai eu une autre idée qui m'a paru meilleure et puis j'ai complètement laissé tomber la récurrence :marteau:

[nodgim]

Le périmètre-rectangle englobant le territoire de la tour ne peut excéder n à la fois en horizontal et en vertical.
2n cases peuvent se grouper sur 1 ligne et 2n colonnes: OK
sur 2 lignes et n colonnes: OK
sur n lignes et n-1 colonnes au maximum quand le territoire est étiré en diagonal: là encore on sait trouver n rectangles (n lignes).
Bien sûr, quand le nombre de lignes et de colonnes est inférieur à n, On forme les rectangles en prenant par exemple 1 rectangle pour 1 ligne, et on découpe ensuite où on veut par arriver à n. :happy2:

[Imod]

Je ne comprends pas ton raisonnement , il pourrait y avoir plusieurs rectangle 1Xk ou kX1 sur une ligne ou une colonne :hein: :hein: :hein:

Imod

[nodgim]

Bon, en fait c'est simple, dans le principe: rayer du territoire 2 cases à la fois.
Quand on est obligé de rayer 3 cases, on en raye 1 seule aussitôt après.

Le territoire ressemble à une ville: des impasses, des rues et des places. On raye les impasses. Si elles ont un nombre impair de cases, on laisse en l'état la dernière case. Les places sont rayées pareil, en prenant soin de garder une rue (une case de large). Les rues sont en réseau, elles forment des boucles: on coupe ces boucles, qui deviennent des impasses, on procède comme ci dessus. A la fin, il ne reste qu'une colonne vertébrale, un couloir unique avec des cases latérales de ci de là. On raye en commençant paer un bout.Quand on arrive à cette configuration de 4 cases: A1, A2, A3, B2, On raye A1 A2 A3 (1 rectangle) puis B2 (2ème rectangle). Quand c'est une configuration A1, A2, A3 et B3, on raye A1 A2 puis A3 B3. Il n'y a pas d'autres configurations possibles.
A la fin, on a bien partager le térritoire en n rectangles.

[Imod]

Tout cela me semble bien compliqué !!! La suppression des impasses ne pose pas de problèmes mais les places peuvent joindre certaines parties du territoire et supprimer la place risque de déconnecter le territoire .



On pourrait bien sûr commencer par les places les plus extérieures ou formant des boucles mais tout cela devient très vite inutilement compliqué sans certitude d'examiner l'ensemble des cas .

Imod

[nodgim]

Tout cela me semble bien compliqué !!! La suppression des impasses ne pose pas de problèmes mais les places peuvent joindre certaines parties du territoire et supprimer la place risque de déconnecter le territoire .



On pourrait bien sûr commencer par les places les plus extérieures ou formant des boucles mais tout cela devient très vite inutilement compliqué sans certitude d'examiner l'ensemble des cas .

Imod

La partie jaune que tu représentes est, dans mon système, une boucle (pour reprendre l'image d'une ville, la partie centrale, vide, est un pâté de maisons). Il suffit d'ôter 2 cases (1 rectangle) à cette boucle pour que le chemin devienne linéaire, c'est à dire avec une entrée (case rouge), une sortie (case bleue) et un seul chemin possible.
Et non, ce n'est vraiment pas compliqué.

[Imod]

Ca vient sûrement de moi mais je ne suis pas convaincu . Par exemple un boucle peut-être connectée de plusieurs façons au reste du territoire et pour la casser comment choisir les deux cases contigües à supprimer ?



Pour casser la boucle jaune sans perdre la connexité il faut retirer les deux cases en bas à droite . Comment traitres-tu ce cas ?

Imod

[nodgim]

Ca vient sûrement de moi mais je ne suis pas convaincu . Par exemple un boucle peut-être connectée de plusieurs façons au reste du territoire et pour la casser comment choisir les deux cases contigües à supprimer ?



Pour casser la boucle jaune sans perdre la connexité il faut retirer les deux cases en bas à droite . Comment traitres-tu ce cas ?

Imod

Ce réseau n'est pas complet, il y a 13 cases :doh:

[Imod]

Ce réseau n'est pas complet, il y a 13 cases :doh:

J'ajoute une case et là casser la boucle c'est déconnecter le territoire !!!



Imod

[nodgim]

J'ajoute une case et là casser la boucle c'est déconnecter le territoire !!!



Imod

Là oui, je suis obligé de faire une séquence 1, 4, 1 (3 rectangles) pour respecter mon système. Tu as bien trouvé une faille dans mon raisonnement qui en restait à 2 ,2 ou 1,3. Je ne sais pas s'il y a plus critique. :doh:

[Imod]

Une des difficultés pour trouver une solution constructive c'est la variété des territoires possible , personnelement j'ai renoncé à une construction effective des rectangles hors récursivité mais je ne détiens sûrement pas toute la vérité :we:
D'autre part l'exercice doit être amusant à progammer en utilisant la ballade de la tour sur son territoire :zen:

Imod

[nodgim]

Après analyse, il s'avère qu'on peut avoir une configuration plus longue que 4, 1 ,1 .
Exemple (les 1 sont des cases, les 0 du vide)
0010101010101....
1111111111111...
0101010101010...
Les cases résiduelles des impasses sont en quinconce par rapport au chemin. On est alors obligé de prendre n cases en une seule fois, et pour compenser, il faut n-2 rectangles de 1, ce dont on dispose, puisqu'il s'agit justement de celles qui sont disposées de part et d'autre.

Voilà donc une réserve levée. Maintenant, ça semble tenir la route. :happy2:

[Imod]

Voilà donc une réserve levée. Maintenant, ça semble tenir la route. :happy2:

Ton exemple était dans mes tiroirs depuis longtemps ! Le principe d'une preuve est de convaincre son interlocuteur de la logique de sa démarche , pas de le mettre au défi de trouver une faille dans son raisonnement . Je suis presque sûr que si tu détaillais les étapes une à une , je pourrais exhiber un contre-exemple ( si j'en avais le courage ) . L'avantage de la récurrence est d'établir le résultat simplement et sans conteste :zen:

Imod