Ce n'est pas mal du tout !

Soit tu remplis 1 ligne du bas et dans ce cas au mieux une seule colonne au dessus de cette ligne. Soit tu remplis 1 ligne en haut mais seulement 1 colonne de la partie basse.

Le problème est toutefois celui ci : un serpent peut toujours remplir n colonnes (de l'extrême droite à l'extrême gauche) plus un certain nombre de cases supplémentaires montantes, ce qui autorise à penser que moins de n serpents peuvent remplir le casier.

Euh, si. Même le n° 1 peut occuper entièrement la ligne 2.

Bonne réponse Vasimolo. Du coup, ta proposition me plait de plus en plus.

Avec ta méthode il est impossible de placer un serpent "en escalier" tant qu'on n'a pas placé tous ceux qui se trouvent en dessous de lui. Autrement dit, la contribution de chaque serpent au dessus d'une ligne donnée ne peut être que sa partie verticale, soit 1 seule colonne par ligne. Les parties horizontales des serpents en escalier ne sont là donc que pour finir une ligne. Donc il est impossible qu'une ligne soit remplie en avance des lignes à occuper puisque k lignes occupées ne peuvent remplir au mieux que k colonnes d'une ligne supérieure.

On tient la solution là non ?

Il faut tout de même que tu prouves l'existence d'un serpent "en dessous de tous les autres " à chaque étape de la construction. C'est assez court mais c'est ta démo je te laisse faire.

Concernant la première partie de ta preuve, chapeau, c'est très joli Je suis convaincu. Ce n'est effectivement pas très facile à rédiger, ça demande encore un peu de travail, mais je pense qu'il sera possible de s'en sortir.

Par contre, je ne saisis pas bien la fin de l'argument. Peux-tu préciser un peu les grandes lignes de "Il n'y a plus qu'à voir que k serpents ne peuvent pas recouvrir plus de k lignes" ?

Je crois avoir quelque chose de plus complet .

Il est clair que le serpent 1 ne peut pas occuper plus d'une case de la ligne 2 sinon il y aurait une case vide sous au moins une de ces deux cases et le serpent 1 serait mal nommé . Supposons par récurrence qu’au plus k cases de  la ligne k+1 sont occupées par les k premiers serpents et considérons les cases de la ligne k+2 . Au plus k cases sont occupées par les k premiers serpents sinon il y aurait un trou sous l'une de ces cases dans la ligne k+1 . Notons x le nombre de cases occupées de la ligne k+2 et ajoutons le serpent k+1 . Toujours pour la même raison ce serpent ne peut pas occuper plus de k+1-x cases ( le +1 pour la case de la ligne k+1 qui hisse le serpent sur la ligne k+2 ) donc un maximum de k+1 cases occupées pour l'ensemble de la ligne.

PS : il peut y avoir plusieurs cases du serpent k+1 sur la ligne k+1 mais une seule peut-être surmontée par une case occupée de la ligne k+2 .

J'espère ne pas m'être trop emmêler dans les indices

Vasimolo

Avant de valider, j'ai besoin d'un éclaircissement. Je veux être sûr d'avoir bien compris.

Notons x le nombre de cases occupées de la ligne k+2

Je suppose qu'il faut comprendre "le nombre de cases de la ligne k+2 occupées par les k premiers serpents" ?

Dans ce cas, on a x<=k. Mais quand, par la suite, tu dis :

ce serpent ne peut pas occuper plus de k+1-x cases

ce ne serait pas plutôt "ce serpent ne peut pas occuper plus de x+1 cases" ? Ce qui ne change pas la conclusion, car x<=k donc x+1<=k+1.

OK, erreur de raisonnement de ma part, j'ai compris maintenant. C'est une belle démonstration, bravo ! Sur un sujet vraiment beaucoup plus difficile qu'il en a l'air.

Ma preuve était très différente de la tienne, on peut même dire qu'elles n'ont rien à voir. Si ce n'est un point commun : je pense qu'il faudrait un certain boulot pour les amener à passer le cap d'un assistant de preuve...

Vasimolo a écrit:

En fait il faut prouver que la relation "est en dessous de" peut être prolongée en un ordre total ( j'en parlais dans un message précédent ) . Ça semble presque évident car si on a a<b et b<c on ne peut pas avoir c<a : ajouter que a<c peut-il créer un conflit ?

Vasimolo

Certes, non, mais dit comme ça, il y a un goût d'inachevé. Enfin, pour moi en tout cas.

@nodgim : tu appelles cela de l'opiniâtreté, j'appelle cela de la folie furieuse. Je ne pensais qu'à ça en m'endormant pendant deux mois. Je ne sais pas s'il faut encourager ce genre de comportement. Ça aurait été plus efficace d'en discuter avec d'autres personnes dès le début, mais des fois on se lance un défi... Je suis d'accord avec ton analyse, c'est sans doute moins décourageant quand on sait qu'il existe une solution, mais ça n'enlève rien à la performance de Vasimolo.

Pour le problème auquel tu fais allusion, je pense voir les arguments qui permettent de conclure, ça utilise des résultats de topologie qu'il n'est sans doute pas facile de rédiger proprement.

@Vasimolo : tu peux envoyer le problème sur d'autres sites.

Voici ma démo : http://www.prise2tete.fr/upload/Ebichu-serpents.pdf

Et pour la suite : https://fr.wikipedia.org/wiki/Th%C3%A9o … _Szpilrajn

Je crois que si on allait expliquer ça aux alcooliques anonymes ils nous regarderaient bizarre.