Moins de n serpents

[beagle]

modifié le 28 mars

[beagle]

modifié le 28 mars

[nodgim]

Pas convaincant.

[Imod]

Je ne suis pas sûr d'avoir tout compris , mais il est clair qu'en supprimant une ligne et une colonne à la frontière du terrain , on ne supprime pas forcément un serpent même en acceptant des reconnexions .

C'est plus subtil que ça

Imod

[Pseuda]

Bonsoir,

On généralise le problème à une figure convexe quelconque formée de de petits carrés : rectangle nxm, carré nxn, pyramide, carré tronqué d'un coin .... Par exemple, pour cette dernière figure (carré tronqué d'un coin), il ne faut plus que (n-1) serpents, pour un carré tronqué de 2 coins en ligne aussi, mais pour un carré tronqué de 2 coins en diagonale, il faut de nouveau n serpents. (donc je pense que ce n'est pas une question de longueur de serpents).

On considère la figure formée par les "noeuds" (centres des carrés 2x2 inclus dans la figure). On imagine que ces noeuds sont des petits carrés dont le centre est le noeud. Pour remplir la figure d'origine, il faut alors le nombre de serpents de la figure formée par les noeuds + 1 : c'est son enveloppe.

Par exemple, pour un carré nxn, la figure formée par les noeuds est un carré (n-1)x(n-1). La figure formée à l'intérieur des noeuds est un carré (n-2)x(n-2), etc... La récurrence est immédiate.

Il s'agit de montrer le point de départ : l'enveloppe des noeuds (il n'y en a qu'une) nécessite un nombre de serpents + 1, ou bien : la figure formée par les noeuds nécessite un nombre de serpents - 1.

[Pseuda]

Attention le problème est hyper-addictif

En effet. A l'essai, on est très vite intimement persuadé que c'est vrai, mais on ne voit pas pourquoi, donc on n'arrive pas à le démontrer, alors c'est assez frustrant.

[beagle]

Pour un carré nxn
mettre un seul serpent engendre des coudes appelés U
U ou n pour ceux horizontaux
U couché dans un sens ou dans l'autre pour les U dit verticaux.

Impossible d'enfermer un total serpent sans avoir un minimum de n-1 coudes U verticaux ou horizontaux.
Pour avoir notre structure avec soit descendant soit montant il faut couper ces n-1 U
ce qui donne un minimum de n serpents.

[beagle]

modifié le 28 mars

[Pseuda]

Bonjour,

Si tous les serpents sont droits, il en faut au moins n. Si on les autorise à zigzaguer, il ne peut y en avoir strictement moins de n que si on les autorise à se retourner sur eux-mêmes.

[nodgim]

Sans doute, mais il faut étayer un peu plus !
En anglais, on appelle ça du wishfull, je n'ai plus en tête l'équivalent français ( c'est un comble ! )

[beagle]

"modifié le 28 mars

[Imod]

Bien sûr Beagle , on peut toujours répondre comme ça , mais la charge de la preuve est à celui qui la fait et pas à celui qui la lit . Sur des petits rectangles on voit bien que ça marche à cause de l'impossibilité de rebrousser chemin . Sur des rectangles plus grands les formes se multiplient et l'argument de retour impossible est loin d'être convainquant . Il faut mettre le doigt sur le point qui empêche de faire moins de n serpents : ce que tu ne fais pas vraiment .

Il y a une idée de base assez simple ( quand on l'a vue )

Imod

[Pseuda]

Si un seul serpent remplit tout le carré nxn, il faut qu'il fasse demi-tour au moins (n-1) fois. Il faut donc le couper pour qu'il n'y ait plus de demi-tours, donc en au moins (n-1) endroits (les endroits de demi-tours), ce qui produit au moins n serpents.

Et voilà !

[nodgim]

@Pseuda: ce n'est pas mal, mais pas encore convaincant. Pourquoi 1 seul serpent doit il faire "demi tour" n-1 fois ?

[beagle]

c'est génial que pseuda ne lise pas mes messages, come ça on peut dire la même chose ça fait un fil de discussion à la Dupont et Dupont, et je dirais même plus un serpent unique ...
En plus j'avais mieux précisé, puisqu'il ya 2 dimensions différentes, et que l'on peut ranger un serpent avec n-1 retournements d'une dimension et n-2 d'une autre dimension (je sais pas si deux fois n-1 existe)
Bref non seulement il n'est pas démontré ce n-1, mais en plus il faut expliquer que l'on peut couper les retournements, que j'avais appelé des U,
ben cela se coupe en transformant d'un coup un retournement d'une dimension et d'une autre,
sinon ce serait faux le n-1

Bref pour répondre à Dominique par ailleurs,
il me semble ètre encore capable de voir ce que je ne démontre pas et ce que je balance comme idées qui viennent en tète. Mais autant les problèmes de Dominique sont intéressants, autant le dialogue dans les fils de discussions instaurés ne sont pas plaisants. Donc j'efface.je laisse juste le Dupon et Dupont et je dirais même mieux un seul serpent n-1 ....

[Pseuda]

Bonjour,

Je reprends plus précisément :

S’il y a un seul serpent à l’intérieur du carré nxn, il se retourne au moins (n-1) fois. Il faut donc le couper en (n-1) endroits => n serpents.
S’il y a k serpents à l’intérieur du carré, ils se retournent au total à eux tous au moins (n-k) fois. Il faut donc les couper en (n-k) endroits = > n serpents.

Le tout est de montrer le nombre de retournements. Je pense que le problème vient entièrement de là : en effet, que les serpents aient le droit de n'aller que tout droit, ou d'avoir un seul coude, ou plusieurs coudes d'un même type, à chaque fois, le résultat est le même : au moins n serpents.

@Beagle : où as-tu vu qu'on n'a pas le droit de s'inspirer de nos réponses respectives ? C'est vrai que les U m'ont fait penser aux retournements (mais pas forcément en U d'ailleurs : ils peuvent avoir lieu plus loin, en U très élargi, dans le trajet du serpent). C'est le but du forum : de réfléchir ensemble, et je ne râle pas quand je vois qu'on s'est inspiré de mes réponses : au contraire, cela me fait plaisir.

[beagle]

@Beagle : où as-tu vu qu'on n'a pas le droit de s'inspirer de nos réponses respectives ? C'est vrai que les U m'ont fait penser aux retournements (mais pas forcément en U d'ailleurs : ils peuvent avoir lieu plus loin, en U très élargi, dans le trajet du serpent). C'est le but du forum : de réfléchir ensemble, et je ne râle pas quand je vois qu'on s'est inspiré de mes réponses : au contraire, cela me fait plaisir.

et où as-tu vu que les U avaient une distance dans mes messages?
Quant aux deux dimensions tu n'y es toujours pas, dommage!

[Pseuda]

Tu interprètes, Beagle. Je te laisse, et je laisse tomber ce fil si tu y es.

[beagle]

Tu interprètes, Beagle. Je te laisse, et je laisse tomber ce fil si tu y es.

oh mais lis un peu mieux, tu dis te barrer d'un fil de discussion si j'y suis,
alors que j'ai dit que j'avais rien à faire dans ce fil comme d'hab dans les fils de Dominique.
Donc tout va bien avec toi sur ce fil. Juste surprenant.

[Imod]

Les n-1 retournements pour un serpent , c'est vrai et je pense que ça doit pouvoir se prouver rigoureusement . Par contre , il faut faire attention que le problème est pris à l'envers , il faudrait s'assurer que n serpents peuvent toujours s'assembler en un grand serpent avec seulement n-1 points de colle : ce n'est pas évident du tout .

Imod