[ENIGME 150 QI] Couvrir une GRILLE

Le 19 juin 2022 à 12:43:44 :
Un autre problème intéressant qui se dégage, c'est montrer que l'optimal pour couvrir un carré de taille n+1 privé d'un de ses coins, c'est n. Si on sait montrer ça, ça implique ce que tu cherches. Est-ce que ce problème-ci passe mieux à la récurrence ?

C'est dans l'autre sens : si on démontre que n est optimal pour ton problème, alors il l'est pour le mien.

On peut reformuler le problème en disant : si je me donne le droit à A chemins de contrainte Nord-Ouest et B chemins de contrainte Nord-Est et si je peux couvrir en respectant les règles, alors A+B vaut au moins n.

On a déjà traité le problème quand A ou B est nul. Est-il possible de traiter le cas où A ou B est égal à 1 ?

Ca semble plus simple que le problème initial et, si c'est possible, ça entrouvre une porte vers une récurrence

Avez-vous un contre-exemple à l'énoncé plus fort suivant ?

Si on a une configuration de k<n chemins orientés mutuellement évitants, alors ils couvrent au plus n²-k² sommets. On peut penser n²-k² comme la somme des k premiers termes de la suite de nombres impairs 2n-1, 2n-3, 2n-5, etc.

Cet énoncé est vrai pour k=1 car tout chemin orienté couvre au plus 2n-1 sommets.

Il est également vrai pour k=2.En effet, si les deux chemins couvrent au plus 2n-2 sommets, alors c'est free win. Si un chemin (A) couvre 2n-1 sommets, alors il va d'un coin du carré au coin diagonalement opposé. On tourne le carré pour que cette diagonale apparaisse verticale. Si l'autre chemin (B) est de type vertical avec ce point de vue tourné, il est forcément de longueur au plus 2n-3 puisque son point le plus bas n'est pas le plus bas du carré et idem pour le haut. Si l'autre chemin est de type horizontal, comme l'autre chemin traverse le carré de part en part et comme les chemins n'ont pas le droit de se croiser, le chemin B doit se trouver soit intégralement à gauche de A, soit intégralement à droite. Par symétrie, supposons qu'il est à droite. On ne perd pas en généralité à supposer A le plus à gauche possible (longeant deux bords du carré). Mais alors, comme le coin le plus à gauche du carré est interdit pour B, ainsi que les deux voisins de ce coin, le chemin B couvre nécessairement au plus 2n-3 sommets.

Je ne vois pour l'instant pas comment exploiter cette généralisation pour envisager une récurrence sur k.

Le 24 juin 2022 à 02:00:40 :
Bon, quelqu'un a fourni une preuve franchement convaincante sur stackexchange.
Y a encore deux trois trucs à formaliser histoire de s'assurer qu'il n'y a pas une erreur subtile, mais je doute que ça soit le cas.
https://puzzling.stackexchange.com/questions/116708/cover-an-n-times-n-grid-with-non-diagonal-non-intersecting-n-1-shortest-paths

[Autre compte de EIBougnador]

Ah oui, sympa !

L'idée qu'il nous manquait, c'est qu'on peut passer d'un carré de taille n à un carré de taille n-1 en découpant le long d'un chemin orienté quelconque reliant deux coins opposés du carré : il suffit d'enlever le chemin puis de faire glisser les deux moitiés l'une vers l'autre.

Genre si on veut donner cette énigme à quelqu'un, c'est vraisemblablement la bonne indication à donner quand on nous en demande une.

Sympa en tout cas.

J'ignore à quel point je trouve la démo ultra-éclairante sur les "raisons" pour lesquelles l'énoncé est vrai. Certainement qu'en digérant bien la démo, ces raisons se dégagent bien.

Si jamais j'ai envie de passer encore un peu de temps en compagnie de cette énigme, je regarderai peut-être si cette stratégie de la fermeture éclair permet également de démontrer la "conjecture" de mon post précédent, à savoir :

Si on a une configuration de k<n chemins orientés mutuellement évitants, alors ils couvrent au plus n²-k² sommets. On peut penser n²-k² comme la somme des k premiers termes de la suite de nombres impairs 2n-1, 2n-3, 2n-5, etc.