Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 08-05-2019 12:14:53

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Serpents bin tassés

Bonjour,

Un serpent est constitué d'une suite de carrés adjacents, sans cycle, et tel que le serpent ne peut se toucher par les côtés ou les coins.

Par exemple:
http://www.prise2tete.fr/upload/caduk-serpent.png
A gauche c'est bien, à droite, c'est pas du tout bien roll

Étant donné un rectangle de x sur y, quel est le plus grand serpent que l'on peut y tracer (respectant les conditions précédemment énoncées)?

Comme j'aime bien prolonger les énoncés par des questions un peu plus ouvertes, on pourra essayer de répondre à la même question avec un serpent pouvant se toucher par les coins (mais pas par les bords, c'est trop facile sinon wink )

Indice:
Spoiler : [Afficher le message] intérieur et extérieur se complètent

  • |
  • Répondre

#0 Pub

 #2 - 08-05-2019 14:13:49

TOUFAU
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 105

Serpent bien tassés

Je dirais
y si x=1
[(x+1)(y+1)-3]/2 si x et y pairs
[(x+1)(y+1)-2]/2 sinon

De là à ce que ce soit des optimums... A part pour le premier. là je suis formel.

 #3 - 08-05-2019 15:04:09

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 747

Serpets bien tassés

Si X est impair (ou Y)
arrondi (X/2) * Y + (arrondi(X/2)-1)

Si X et Y sont pairs
(X * Y/2) + X/2

 #4 - 08-05-2019 16:15:28

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Serpents bien taséss

TOUFAU
Oui, reste à le démontrer... smile

godisded
Arrondi par excès ou par défaut?
Si c'est par excès, OK pour le premier cas. (Note que si X est impair, l'arrondi de X/2 par excès est donné par (X+1)/2 ( et par (X-1)/2 par défaut )
Non pour ton deuxième cas, on peut faire mieux...
A priori, on devrait s'attendre à une formulation symétrique selon X et Y.
Cela peut se faire en prenant le max entre ta formule et ta formule où on intervertit X et Y (toutefois, ça ne donne toujours pas l'optimum...)

 #5 - 08-05-2019 17:16:01

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 747

serpents bien tasséd

Arrondi par défaut, ça suffit, non ? smile
Merci pour la "correction" du premier cas, je n'arrivais pas à le faire simplement !

Pour le deuxième, je suis une buse car j'ai oublié de contrôler ma réponse. (j'ai la réponse graphique, mais j'ai planté la mise en équation)
(X * Y/2) + X/2 + (Y/2 - 1)

 #6 - 08-05-2019 17:47:17

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Serpents bieen tassés

godisdead
Vu que l'on cherche la taille maximale, il vaut mieux arrondir par excès.
Normalement, c'est simple de trouver un serpent qui atteint cette taille.
Ok pour le cas pair.
Comme pour TOUFAU, il ne te reste qu'à démontrer tes conjectures... wink

 #7 - 08-05-2019 17:49:05

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Serpents bieen tassés

J'arrive à construire récursivement un serpent de taille [latex]\lfloor\frac{xy+x+y-1}{2}\rfloor[/latex], en me ramenant à un rectangle de x sur (y-2).

Il me reste à démontrer qu'on ne peut pas obtenir de serpent plus grand.

Il me semble que le résultat ne change pas si on autorise les hydres (des serpents avec plusieurs têtes), du moment qu'il n'y a pas de cycle.

 #8 - 08-05-2019 19:07:50

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Serpnts bien tassés

Ebichu
Oui, et le tout en une formule bravo! lol
Même consigne que pour nos 2 premiers participants, reste la démo à trouver smile

Oui pour ta deuxième remarque.
A priori, si ta démo dans le cas du serpent n'est pas trop tirée par les cheveux, tu démontres par la même occasion ce résultat. (Mais je ne voulais pas trop alourdir l'énoncé de l'énigme)

 #9 - 08-05-2019 20:44:39

TOUFAU
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 105

Serpets bien tassés

Ok, tentons une démonstration, tolérant certaines libertés…

Je ne reviens pas sur le cas x=1,

Imaginons que notre serpent souffre d’obésité. Et qu’il soit large de non pas 1, mais 2 cases. Il se balade en restant centré sur une case, mais la pauv’ bête déborde d’1/2 case de chaque côté. Avec une autorisation de braquer en angle droit quand même, il souffre assez comme ça. Et il peut utiliser dans un passage retour les demi-cases latérales sur lesquelles il n’est pas passé à l’aller.

Notre ‘damier’ est étendu d’1/2 case tout autour, pour permettre à notre invertébré de cheminer partout. La surface du damier est donc de (x+1)(y+1).

Au mieux, notre ami pourra passer par la moitié de cette surface compte tenu de son embonpoint (si on oublie ses flans, bien entendu, pour revenir à notre problème initial). Soit (x+1)(y+1)/2 cases.

Seulement voilà, tout boucle étant interdite, il doit bien commencer quelque part et finir quelque part (comme le dit la chanson). Ce faisant, il va condamner 1/2 case au départ et 1/2 case à l’arrivée, celle derrière ou devant lui, inutilisables ensuite dans son parcours. Donc une case en tout en terme de surface.

Soit au mieux [(x+1)(y+1)-2]/2 cases parcourues finalement. Et comme il faut que tout ça soit un nombre entier, on revient au maximum à [(x+1)(y+1)-3]/2 si x et y sont pairs.

Il s’agit d’un maximum théorique, mais comme on peut aisément trouver une solution (et même plein) atteignant ce résultat, il a une belle tête de vainqueur.
La rigueur de tout ça est très relative, je sais.

 #10 - 08-05-2019 21:53:03

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

serpenys bien tassés

TOUFAU
C'est vraiment pas si mal.
Pour que ce soit vraiment rigoureux, il faudrait mieux détailler ce qui se passe dans les angles, je ne sais pas si dans ta solution tu les traites bien.
Spoiler : [Afficher le message] Lorsque le serpent tourne, certains flancs du serpent se chevauchent, faisant diminuer l'aire 
Mis à part ça ta solution est rigoureuse. La mienne est basée sur un principe semblable, quoique un peu différent.
Cependant, comme Ebichu l'a fait remarquer, on peut prolonger ce résultat aux hydres (serpents avec plusieurs têtes). Dans ce cas, on peut adapter ta démo, mais ça devient un peu plus casse-gueule (car cette fois, les angles du serpent vont vraiment poser problème...), et il faut vraiment justifier proprement.
Ma preuve, elle, s'adapte très facilement à ce cas...

 #11 - 09-05-2019 14:24:53

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

serpents bien yassés

J'ai trouvé une solution. Elle consiste à épaissir le serpent d'un demi-carreau de chaque côté, à la suite de quoi l'aire occupée par le serpent vaudra 2L+2, où L est la longueur du serpent. En voici la preuve.

Pour un carreau sur lequel le serpent voyage en ligne droite, on rajoute deux petits carrés de côté 1/2 carreau (verts) de chaque côté du serpent (cas du milieu sur mon illustration).

http://www.prise2tete.fr/upload/Ebichu-solutionserpent.png

Si le serpent fait un virage (cas de gauche), on rajoute cinq petits carrés verts, mais on enlève un petit carré à l'endroit en rouge, car les petits carrés verts des deux carreaux voisins du virage vont se chevaucher à cet endroit.

Si enfin on est à une extrémité du serpent (cas de droite), on rajoute 8 petits carrés verts.

Chaque extrémité contribue pour 3 carreaux, et chaque virage ou chaque ligne droite pour 2 carreaux chacun. Un serpent de longueur L recouvre ainsi une aire totale de 2L+2.

Considérons le rectangle initial de taille xy, et agrandissons-le de 1/2 carreau le long de chaque bord, de sorte qu'on a maintenant un rectangle d'aire (x+1)(y+1). Le serpent épaissi va recouvrir une partie de cet rectangle.  On a donc 2L+2 <= (x+1)(y+1) d'où [latex]L \leq \frac{xy+x+y-1}{2}[/latex].

 #12 - 09-05-2019 19:21:02

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Srepents bien tassés

Pas mal Ebichu, tu as exactement la même solution que TOUFAU, avec une justification précise sur les angles du serpent. (Mais une moins jolie prose, on ne peut pas tout avoir sad )
En bidouillant un peu, tu dois pouvoir l'adapter au problème de l'hydre, mais il faut traiter les angles un peu différemment.
Ma méthode est légèrement plus simple que celle-ci, et s'adapte directement à l'hydre.

Sinon, tu peux passer au cas du serpent avec possibilité de collisions au coins.

 #13 - 09-05-2019 22:36:10

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

serpznts bien tassés

L'hydre n'est guère plus compliqué. Quand on a un T, ça rajoute une extrémité au serpent, et il faut placer à côté de la case du T deux petits carrés verts et deux petits carrés rouges. Quand on a un +, ça rajoute deux extrémités au serpent, et il faut placer 4 petits carrés rouges à côté de la case du +. La même démonstration tient.

Pour la question ouverte, j'adopte la même démarche, sauf qu'au lieu d'épaissir mon serpent régulièrement, je lui rajoute des pointes : sur chaque côté de longueur 1 carreau bordant le serpent, je rajoute une pointe formée d'un triangle rectangle isocèle, dont l'hypoténuse est le côté de longueur 1 (un tel triangle a donc une aire de 1/4 carreau). J'obtiens un majorant de la taille du serpent : [latex]\lfloor\frac{2xy+x+y-1}{3}\rfloor[/latex].

Il n'est pas optimal, par exemple pour un rectangle 4x2, il donne 7, alors que le plus grand serpent possible est de taille 6. Par contre, il donne parfois la bonne valeur, comme pour le rectangle 6x3 où il donne 14.

 #14 - 10-05-2019 14:18:53

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Serpent bien tassés

Ebichu
Ok pour l'hydre.
J'obtiens également le même majorant en appliquant simplement ma méthode.
Mais en forçant un peu, on peut obtenir mieux...

 #15 - 11-05-2019 19:54:56

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Serpents bien tasssés

Pour le problème ouvert, Ebichu obtient une borne supérieure de :
[TeX]\left \lfloor \dfrac{2xy+x+y-1}{3} \right \rfloor[/TeX]
Pour ma part, j'arrive à obtenir:
[TeX]\left \lfloor \dfrac{15xy+8x+8y+4}{24} \right \rfloor[/TeX]
Qui dit mieux? big_smile

Indice:
Spoiler : [Afficher le message] Cherchez longueur plutôt qu'aire, c'est plus simple wink

J'ajoute aussi un indice pour ceux qui ne décollent pas sur la première question yikes

Spoiler : [Afficher le message] intérieur et extérieur se complètent

 #16 - 11-05-2019 20:32:20

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3220
Lieu: Luxembourg

serpents bien taqsés

Pour le premier cas (sans les coins), en étudiant suivant x et y pair ou impair, je trouve une longueur maximale de serpent de: ent[(x+1)(y+1)/2]-1 (ou ent représente la partie entière).
Pour le second cas (avec les coins), je cherche encore à optimiser.

 #17 - 11-05-2019 20:53:45

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Serpents bien assés

Franky1103
Oui, c'est la bonne formule, une démo?

 #18 - 12-05-2019 00:01:35

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 747

Serpents ien tassés

Je ne comprends pas pourquoi l'hydre serait différent du serpent ?
Sur un carre 5*5, avec ta formule, tu remplis donc 19 cases, je ne vois pas comment faire ... sad

 #19 - 12-05-2019 00:27:58

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Seprents bien tassés

Non, la formule donnée, c'est pour la deuxième question, avec les coins qui se touchent. Pour le problème de l'hydre, il faut montrer que l'on obtient la même chose qu'avec un serpent...

 #20 - 12-05-2019 08:47:32

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3220
Lieu: Luxembourg

Serpents bien tasss

En guise de démonstration, je me suis contenté de calculer la longueur et le nombre de lignes, suivant que x et y soient pair ou impair (donc 4 cas). Seul le cas où x et y sont impairs semble particulier car (x+1).(y+1) est alors impair.

 #21 - 12-05-2019 09:17:38

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Serpents bien ttassés

Ce n'est pas une démonstration, c'est une conjecture.
Ou alors si pour chaque x,y, tu as trouvé un serpent avec la taille que tu indiques, alors tu as démontré que c'était une borne inférieure.
Il reste à démontrer que l'on ne peut pas trouver de serpents plus grand que cette borne, et c'est généralement pas la partie la plus simple dans ce genre de problème... wink

 #22 - 12-05-2019 09:54:17

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

szrpents bien tassés

Je me suis aperçu que mon raisonnement était deux fois plus puissant que ce que je pensais. Et avec une amélioration mineure en plus, j'obtiens pour la question 2 une borne supérieure de
[TeX]\left \lfloor \dfrac{7xy+4x+4y+4}{12} \right \rfloor[/TeX]
On est très proche de l'optimum pour des carrés, un peu moins pour les rectangles...
La formule est valable si x et y sont supérieurs à 4.
Edit: Désolé, j'ai confondu x +y et x*y...
Ma formule est donc [latex]\left \lfloor \dfrac{8xy+2x+2y+6}{12} \right \rfloor[/latex]

 #23 - 14-05-2019 14:22:36

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Serpents ien tassés

Les réponses sont désormais visibles, voici ma méthode. Plutôt que de passer par une aire autour du serpent, je passe par le périmètre du serpent.

Le périmètre du serpent est égal au périmètre autour des cases blanches et du bord.

Le périmètre du serpent est 2n + 2, ou n est le nombre de case noire. En effet, une case noire à un périmètre de 4.
Chaque case noire ajoutée possède exactement un bord en commun avec le reste du serpent déjà construit (pas de cycle, ce qui est commun avec le problème de l'hydre)

Soit m le nombre de cases blanches.
Le périmètre du rectangle est 2x + 2y. On a m + n = xy (aire du rectangle)
Toutes les cases blanches se rattachent au bord (via une succession de cases blanches. En effet, si un groupe de cases blanches n'était pas rattaché au bord, il serait entouré de cases noires. Or les cases noires ne peuvent former de cycles.
On peut donc de proche en proche ajouter des cases blanches de manière à ce qu'elles soient en contact avec un bord du rectangle ou avec une case blanche déjà posée. A la différence des cases noires, les cases blanches ajoutées peuvent toucher plusieurs autres cases blanches. A chaque case blanche ajoutée, le périmètre augmente de 4 - 2*c ou c est le nombre de contact de la case blanche avec les cellules préalablement posée. Comme c >= 1, le périmètre augmente au maximum de 2. Le périmètre est donc inférieur à 2x + 2y + 2m.

Donc par égalité des périmètres noirs et blancs, on a [latex]2n + 2 \leq 2x + 2y + 2m[/latex]
soit [latex]4n + 2 \leq 2x + 2y + 2m + 2n = 2x + 2y + 2xy[/latex]
Ou encore [latex]n \leq \dfrac{x + y + xy -1}{2}[/latex]
Comme n est entier, on a [latex]n \leq \left \lfloor\dfrac{x + y + xy -1}{2}\right \rfloor[/latex]
Il est facile de vérifier que cette borne est atteinte.

Dans le cas d'un serpent touchant les coins, les cases blanches ajoutées peuvent ne toucher aucune case précédemment posée. Dans ce cas, le périmètre blanc sera inférieur à 2x + 2y + 4m.
On en déduit le majorant d'Ebichu, mais on s'aperçoit vite que cette borne n'est pas atteinte souvent.

On peut toutefois améliorer un peu...
Le périmètres blanc est égal à 2x + 2y + 4m - 2c, ou c est le nombre total de contacts entre 2 carrés blanc ou entre un carré blanc et le bord du rectangle. Pour que c = 0, il faudrait que toutes les cases autour du rectangle soit noires. Déjà, cela ferait un cycle, ce qui donne c > 0. Mais surtout, toutes les cases adjacentes au cases noires au bord du rectangle seraient blanches, ce qui augmenterait beaucoup le nombre de contacts.

Ainsi, on voit que si il y a 4 cases noires adjacentes le long du bord, alors au moins deux cases blanches sont en contact à cet endroit.

Soit B et N le nombre de cases blanches et noires sur le bord. B + N = 2x + 2y - 4 = L.
Si B cases blanches sont en contact avec le bord, alors cela implique que N - 3B-8 cases blanches sont en contact sur le deuxième anneau (après analyse des coins). Si B > (xy - 12)/4, alors, il y a au moins (L - 8)/4 contacts sur le bord. Sinon, il y a B + N - 3B - 8 = L - 3B - 8 > (L - 8)/4 (car c'est minimal si B est maximal).
Il y a donc au moins (L - 8)/4 contacts, donc le périmètre blanc est inférieur à:
2x + 2y + m - (L - 12)/2 = (4x + 4y + 4m - 2x - 2y + 4 + 8)/2 = (2x + 2y + 4m + 12)/2.
On obtient alors [latex]\left \lfloor \dfrac{8xy+2x+2y+8}{12} \right \rfloor[/latex]
(Je ne sais pas d'où sortait mon 6, sans doute encore une erreur...)

 #24 - 14-05-2019 18:39:19

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

serpenrs bien tassés

Je n'ai pas encore eu le temps de lire le détail de la démo, mais tu peux au moins simplifier ta formule par 2. La formule avec 15/24, c'était une erreur ?

 #25 - 14-05-2019 20:50:16

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Serpents bien tasssés

Exact, on peut diviser par 2... yikes

Oui, les deux premières formules sont évidemment fausses, asymptotiquement, un serpent maximal occupe les 2/3 de l'aire totale.

J'ai oublié d'indiquer où j'ai trouvé le problème:
http://depot-e.uqtr.ca/7700/1/031015002.pdf
(voir les 12 dernières pages)
Il donne les conjectures pour les serpents maximaux.
Je pense que le problème n'est actuellement pas si compliqué à résoudre. En utilisant ce que j'ai fait pour améliorer  la borne supérieure, mais en l'appliquant sur un anneau plus grand, je pense que ça doit marcher. (Mais il faut appliquer sur un anneau d'au moins 5 cases normalement). Il faut aussi bien prendre en compte les coins et les deux extrémités du serpent. Ça me parait très fastidieux, mais faisable (en faisant une grosse récurrence en peu dégueu sur l'arrangement optimal sur tout le bord)

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Si il y a 63 pommes et que vous en prenez 23, combien en avez-vous ?

Sujets similaires

Mots clés des moteurs de recherche

Mot clé (occurences)

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete