Salut,

Un essai assez simpliste, mais pas que...

On peut toujours imaginer que les serpents ne se déplacent que vers la droiteuniquement, cela ne change rien au problème.

Le coin haut-gauche doit être recouvert. S'il l'est par un serpent se déplaçant vers le haut, on se ramène dans le pire des cas à traiter le cas N-1 avec un serpent de moins. Par récurrence, dans cette hypothèse, il faudra 8 serpents au minimum.

Idem si le serpent se déplace vers le bas mais ne tourne qu'à la dernière colonne.

Idem, s'il ne tourne pas du tout.


Dans le cas ou ce serpent se déplace vers le bas, quelle que soit sa forme, on peut ramener la situation au cas de 2 carrés de dimension X et Y avec X+Y = N-1 en prenant comme base le point ou le serpent coupe la diagonale.



Toujours par récurrence, et sachant qu'un carré de 1 case nécessite un serpent, on conclut.

@gwen27 : beaucoup de bonnes idées dans ton message. Un problème cependant : et si ton serpent orange est trop court, et ne touche ni le bord d'en bas, ni celui de droite ? Il y a alors la possibilité qu'un même serpent, passant par l'espace laissé en bas à droite, recouvre les carrés X et Y...

Heu, je ne comprends pas ce dernier message ?

On suit bien la solution de Gwen et intuitivement on ne va pas réussir à joindre toutes les zones bleues aux grises sans un rebroussement contraire à la nature des serpents mais il manque un argument .

Il faudrait aussi évoquer le cas où le serpent issu du coin supérieur gauche ne traverse pas la diagonale ( même si c'est évident ) .

Vasimolo

Une autre piste peut être.

Tout d'abord, on remplace les cases par des points et donc chaque point est relié par une liaison en extrémité ou en passage (représentation type graphe)

Pour un graphe donné, on va s'efforcer de remplacer, ligne par ligne, en commençant par exemple par celle du bas et en montant ligne par ligne, chaque segment vertical par un horizontal. Comme, pour une ligne donnée, une liaison n'a au mieux qu'une seule verticale, cette substitution se fait normalement avec un nombre inchangé de liaisons, car on raccourcit toujours une liaison par grignotage de l'extrémité de sa partie verticale, ou avec un nombre moindre par regroupement de 2 liaisons horizontales.

Au final, avec seulement des liaisons horizontales, il y a au minimum n liaisons.

Non , le cas où la diagonale n'est pas traversée n'est pas plus clair que le reste

Ce qui marche à coup sûr c'est que si on trouve un serpent qui relie deux bords on peut conclure par récurrence . Je pense qu'on est toujours dans cette situation s'il y a au plus n serpents , mais il faut le prouver .

Vasimolo

En effet , il faut trouver une autre idée

Vasimolo

J'ai l'impression que tu raisonnes à l'envers

Tu pars d'une configuration très particulière à 8 serpents que tu déformes progressivement en expliquant pourquoi on ne peut pas la réduire . Et pourquoi n'existerait-il pas une configuration avec 7 serpents n'aboutissant pas à ton point de départ ?

Vasimolo

@Gwen : J'ai pu passer à côté de ton idée mais tu pars d'un recouvrement avec n serpents qu'on ne peut pas réduire et tu en déduis qu'on ne peux pas faire avec moins de n serpents .

Pour moi il y a un problème logique .

Vasimolo

@gwen27 : je vois bien l'idée, j'avais eu la même à l'époque. Cependant, pour l'instant, ta preuve est bien informelle. Il faudrait écrire tout ça un peu plus proprement.

Je n'ai jamais réussi à la formaliser : j'avais essayé de trouver un invariant en utilisant le nombre de départs, ou de vides, ou de serpents allant dans un sens ou l'autre... mais je n'ai pas trouvé.

Bref, pour l'instant, ce n'est pas assez clair pour que je sois convaincu. Mais il ne manque peut-être pas grand chose pour que ce soit le cas.

C'est fait. Ce n'est pas parce qu'il n'y a pas de réponse qu'il n'y a pas de recherche.
" Il n'est pas nécessaire de réussir pour persévérer "

Une piste m'a mené sur un autre problème. Il s'agit d'un damier de n lignes et une infinité de colonnes, qu'on remplit évidemment avec n serpents en ligne. Mais si 1 seul d'entre eux se met à prendre une verticale, fusse sur une seule case, c'en est fini du remplissage infini si on ne veut ignorer aucune case d'aucune colonne. Le but est alors de savoir combien de colonnes après le coude on peut encore remplir. Pour un seul serpent déviationniste, c'est facile, mais à partir de 3, ça commence à se compliquer....

Je ne réagis pas car je ne veux pas parasiter le cours de votre pensée qui vous entrainera peut être vers d'autres territoires que la mienne, mais je suis votre progression avec intérêt.