DEFI 72 : Les 100 segments.

Posté par minkus minkus

Bonjour a tous.

Bon he bien puisque tout le monde est rentre on peut attaquer les choses serieuses avec le premier defi du mois a quatre etoiles. Prenez votre temps pour repondre.

On considère une grille carrée 55 de 25 cases. Cette grille est constituée de 36 sommets et de 100 segments qui correspondent aux 4 côtés de chaque case. (Certains segments sont comptes deux fois.)

Le but du jeu est de relier les 36 sommets sans passer deux fois sur le même segment, alors qu'il est possible de passer plusieurs fois par le même sommet.

Remarques :

- On ne peut pas sortir de la grille.
- Les seuls mouvements autorises sont les mouvements verticaux et horizontaux. (Avec des virages a 90 degres.)
- Le point de depart et le point d'arrivee ne sont pas imposes et ils doivent etre relies sans lever le crayon. (Evidemment !)

A la fin on inscrit dans chaque case le nombre de ses cotes qui ont ete parcourus (4, 3, 2, 1 ou 0) et on fait le total des points. Ainsi le score maximal absolu est de 100 points (254) car certains segments peuvent rapporter 2 points lorsqu'ils appartiennent a deux cases.

Un exemple pour mieux comprendre :

Si on parcourt les 36 points en spirale en partant d'un coin alors sur les 25 cases, 24 rapportent 2 points et celle du centre 3 points. Cela fait donc un total de 51 points mais on peut faire mieux.

Le score de 100 points est en fait irrealisable en pratique et le probleme que je vous pose est de trouver le score maximal effectivement réalisable.

Bon courage.

minkus

PS : Desole pour l'enonce a rallonge mais je tenais a m'assurer que tout le monde comprenne bien le probleme, sans aucune ambiguite. J'espere n'avoir rien oublie.

Posté par sly2112 sly2112

Mon score est de 91.

Posté par vince909 vince909

Bonsoir minkus,

Je trouve que le score maximal possible est de 93, à savoir 18 cases à 4 points et 7 cases à 3 points.

Merci pour le défi.

Posté par borneo borneo

Bonsoir, ça tombe bien, je me suis intéressée aujourd'hui aux sept ponts de Königsberg, patrie du grand Kant.

On veut obtenir une chaîne eulerienne et donc tous les sommets doivent être de degrés pairs (ici 2 ou 4) sauf deux, ceux du départ et de l'arrivée (qui peuvent être distincts, selon l'énoncé, sinon il faudrait un cycle eulerien)

J'ai commencé par dessiner un cycle eulerien sur le damier. On a deux possibilités, l'une avec 88 segments et l'autre avec 92 segments. J'ai choisi celui de 92, puis je pouvais admettre deux sommets de degré impair, c'est à dire 3.
Je peux alors ajouter 1 segment, qui relie départ et arrivée.

Donc le nombre maximum de segments est 93.

Ma réponse : 93 points.

Merci pour cette énigme qui m'ouvre la porte d'une discipline passionnante.

Posté par plumemeteore plumemeteore

Le score maximum est 93.
Une ligne fournit un nombre pair de chemins à chaque sommet qu'elle rencontre, sauf aux extrémités dans le cas d'une ligne ouverte. Or dans le carré complet, il y a seize points, sur les bords, qui reçoivent un nombre impair de chemins. Il y a donc au moins seize extrémités et huit lignes ouvertes : celle du problème et sept autres, qui ont le moins de valeur possible et seront de simples segments du bord entourant le segment central de chaque côté du grand carré, un de ses huits segments appartenant à la ligne principale.
La ligne comprend plusieurs parties :
le segment précité
les quatre carrés de coin
le périomètre du reste
le périmètre de la figure à l'intérieur de ce périmètre
le carré central
On trace le segment du bord, puis on parcourt le périmètre extérieur, en faisant un détour par les carrés de coin quand on arrive à proximité; on peut faire une interruption pour tracer le périmètre intérieur et une autre interruption dans celui-ci pour tracer le carré central.
Voici un exemple :
abcdef
ghijkl
mnopqr
stuvwx
123456
7890AB

Le parcours de la ligne : bcdjkeflkqwvuopv43utnoijpqrxw56BA5409328712tsmnhgabhic
Minkus, en mettant quatre étoiles, aurais-tu voulu faire peur aux concurrents ?

Posté par savoie (invité)

Bonjour,

Je propose comme score maximal : 93.

Merci pour cette belle énigme. Une comme je les aime !

Posté par gloubi gloubi

Bonjour,

Voici une solution à 92 points, que je considère comme optimale.
Pour une bonne(?) lisibilité, je n'ai pas inscrit le nombre de côtés parcourus dans chaque case. Le décompte est simple: 17 cases à 4 points et 8 à 3 points.
Petite imprécision sur le dessin: le segment E3-E1 devrait être continu avec un "saut" de E2 sur F2-D2.

A+,
gloubi

Posté par chaudrack chaudrack

Bonjour et merci pour l'énigme.

Je n'ai pas trouvé mieux que 92 points.

Réponse en image



@ plus, Chaudrack

Posté par nobody (invité)

Je pense que la solution est 93. Comme je ne suis pas bon en dessin et qu'il y a déjà plein de réponses, je vous reporte sur l'un des dessins des autres "mathiliens". En revanche, je propose une démonstration.
Je vais en effet démontrer qu'il n'est pas possible de faire strictement plus que 93 :
* Par un sommet ne peut passer qu'un nombre pair de "segments parcourus", exception faite de 2 sommets (par exemple, le premier sommet et le dernier).
* Appelons degré d'un sommet le nombre de segments (parcourus ou non) issus de ce sommet. Ainsi, tous les somments "intérieurs" sont de degré 4, les 4 sommets des coins sont de degré 2, et les autres sommets (sommets du bord) sont de degré 3. Sur ces sommets de degré 3, on ne pourra faire passer que 2 segments maximum (sauf éventuellement pour 2 sommets exceptions), d'après la remarque précédente.
* Sur chaque sommet de degré 3 (sauf pour les 2 exceptions), il faut donc choisir un segment issu de ce sommet qui ne sera pas parcouru. Le moins "coûteux" est de choisir un segment du bord.
La moitié des segments qui relient 2 sommets de degré 3 ne sera donc pas parcouru. Il y en a (6-2)*4=16. Donc, 8 segments ne seraient pas parcourus, sauf que 2 "sommets" exceptions peuvent "récupérer" un segment. Donc, seuls 7 segments (du bord) ne pourront donc pas être parcourus dans le meilleur des cas et 7 points au moins seront perdus par rapport au score théorique de 100.

Posté par savoie (invité)

J'ai déjà répondu mais je vais juste faire joli dans la présentation des énigmes : 5 réponses en même temps aux 5 énigmes en cour, ça fait sympa !!Bref ne tenez pas compte de ce messagge qui n'aura plus aucun sens dans quelques minutes, lorsqu'un intrus aura décidé de répondre à l'une ou l'autre des 5 énigmes....

Posté par Nofutur2 Nofutur2

Pour ne pas lever le crayon sans repasser sur un segment, il faut que d'un sommet parte un nombre pair de segment (sauf pour le départ et l'arrivée).
Les 16 sommets latéraux extérieurs (sauf les 4 coins), sont reliés à 3 segments chacuns, ce qui impose de ne pas atteindre 8 segments extérieurs,sauf un qui est atteint grâce au sommet départ et au sommet arrivée.
Le score maximal réalisable est donc de 93. Voici un exemple joint.

Posté par Fractal Fractal

Bonjour, il me semble qu'il y a une incohérence dans l'énoncé ou alors il y a quelque chose que je n'ai pas compris.
D'après l'énoncé il y a 100 segments, un par côté de chaque carré. Mais tu dis également que "certains segments peuvent rapporter 2 points lorsqu'ils appartiennent a deux cases".
Il me semble qu'il s'agit plutôt de deux segments mais situés au même endroit, et qu'il faudrait donc passer deux fois au même endroit mais en imaginant qu'on passe sur les deux segments. Ainsi on n'est pas passé deux fois sur le même segment car certains segments sont doubles.

Suivant cette interprétation, le graphe du problème comporte uniquement des sommets de degré pair donc le score 100 est réalisable sans problème.

Si l'on considère que le trajet entre deux points côtes à côte n'est réalisable qu'une fois (le sens usuel du mot segment) l'énigme devient alors plus intéressante mais dans ce cas le fait qu'il y ait 100 segments n'a pas vraiment de sens.

Je vais donc suivre la deuxième interprétation car la première serait triviale.


Le score maximal réalisable est de 93 points.

Démonstration :
Le graphe du problème comprend 16 sommets de degré 4, 16 de degré 3 et 4 de degré 2.
On sait qu'un graphe possédant une chaîne eulérienne doit posséder au maximum 2 sommets de degré impair.
Par conséquent, le plus grand sous graphe du graphe du problème possédant une chaîne eulérienne possèdera au maximum
- les 16 sommets de degré 4
- les 4 de degré 2
- seulement 2 de degré 3 et donc 14 de plus de degré 2.
Dans le meilleur des cas 7 segments ont alors été retirés.
Étant donné que retirer un segment du bord fait perdre un point et qu'en retirer un du milieu en fait perdre 2, il faut se débrouiller pour que les segments retirés se situent sur les bords.
Il reste à vérifier que cette possibilité est effectivement faisable.
C'est le cas, voici le chemin à parcourir (en numérotant les sommets de gauche à droite et de haut en bas) :
7 1 2 8 9 3 4 10 11 5 6 12 11 17 18 24 23 29 30 36 35 29 28 34 33 27 26 32 31 25 26 20 19 13 7 8 14 15 9 10 16 17 23 22 28 27 21 22 16 15 21 20 14 13

7 segments du bord ont été retirés, donc 7 points, donc le score obtenu est de 93 comme on peut le vérifier en comptabilisant le nombre de côtés parcourus par case.

Merci pour l'énigme, problème intéressant

Fractal

Posté par jacques1313 jacques1313

Je trouve une solution à 93 points.

Posté par piepalm piepalm

En partant du coin supérieur gauche, on peut tracer 13 segments (H=haut, B=bas, D=droite, G=gauche) DBDHDBBGHDDHD pour atteindre le coin supérieur droit. En recommençant 3 fois en pivotant à chaque fois d'un quart de tour, on trace tous les segments sauf 8 (les deuxième et quatrième des cotés extérieurs. Comme la ligne obtenue est une ligne fermée, on peut la commencer en n'importe quel point, par exemple au deuxième point du coté supérieur, et tracer un segment supplémentaire pour finir. On obtiendra alors un total de 93. Je ne pense pas qu'il y ait mieux, mais...

Posté par slaurent128 (invité)

Bonjour,
j avais décidé que ce mois-ci, je ne participerai pas aux énigmes d'optimisation, car pour l'instant je me suis toujours trompé sur celles-ci.
Mais bon, finalement, je tente quand meme...
J'arrive à faire 93 points.
S'il faut un dessin, je le montrerai.

Merci pour l'énigme

Posté par manpower manpower

Bonjour,

Je ne vois pas mieux que de condamner 8 segments (aux bords pour ne pas qu'ils soient comptés deux fois en commençant à réfléchir à partir des coins).

Je penche ainsi pour un score maximal "pratique" de .

Une proposition en image...



Merci pour l'énigme.

Posté par la_brintouille la_brintouille

Le meilleur score possible est 93, faut il justifier ? L'énoncé ne semble pas le préciser ... je le ferai si doute il y a !

Posté par gloubi gloubi

Bonjour,

Dans un moment de désoeuvrement, je me suis repenché sur cette énigme, et je m'aperçois que le score optimal est supérieur à 96 (97 au minimum).

Et dire que j'étais content de moi!

Merci pour le   !

gloubi

Posté par kiko21 kiko21

Bonjour,

Je ne trouve pas mieux que

Ma soluce en image...

...avec fond transparent (Bornéo comprendra... ou enragera !!)

Merci et à bientôt, KiKo21.

Posté par lotfi lotfi

bonjorno,
je pense que 92 est le score maximal réalisable.

Posté par Pti_Kiwi (invité)

On considère que les 36 sommets sont ceux d'un graphe.
Il faut placer un maximum d'arètes pour rendre ce graphe eulérien (que l'on peut parcourir en passant par chaque sommet et revenir au départ)
Les degrés maximums de chaque sommet sont:
233332
344443
344443
344443
344443
233332
Un graphe est eulérien si est seulement si chaque sommet est de degré pair. Donc les degrés de chaque sommet vont être:
222222
244442
244442
244442
244442
222222
Ce qui correspond à un seul score possible:
43434
34443
44444
34443
43434
C'est à dire un score maximum de 92.

Posté par pitbull94 (invité)

la réponse est 93

Posté par ONERAoPARADIS (invité)

Bonsoir,

après quelques essais sur des carrés de 9 cases, la logique est un peu la même pour ce carré de 25 cases et donc mon résultat est : 92  ! ! ! ( score = 92 points)

Bonne continuation et Miaouw à tous

ONERAoPARADIS

Posté par evariste evariste

pas mieux que 93 points
par exemple :
A2-A1-B1-B2-C2-C1-D1-D2-E2-E1-F1-F2-E2-E3-F3-F4-E4-E5-F5-F6-E6-E5-D5-D4-E4-
E3-D3-D2-C2-C3-D3-D4-C4-C5-D5-D6-C6-C5-B5-B6-A6-A5-B5-B4-C4-C3-B3-B4-A4-A3-
B3-B2-A2-A3

Posté par jugo jugo

Bonjour,

Je ne saurais pas le démontrer (et pour cause si ma réponse est fausse), mais il me semble bien qu'au mieux, on laisse 7 segments non parcourus sur le pourtour de la grille, ce qui fait 7 points perdus sur les 100 disponibles.

Score maximal : 93

Posté par ben314 (invité)

En espérant que mon premier message ne me vaudra pas un poisson, je dirais 93

Posté par minkus minkus

Bonjour,

Personnellement je trouve que vous vous en etes bien sortis avec ce defi. La reponse etait bien 93.

Je constate qu'il y a beaucoup de 92 et cela correspond au parcours symetrique obtenus par quasiment tout le monde. Pour obtenir 93 il fallait voir que les points de depart et d'arrivee pouvaient etre disctincts (et donc relies a la fin).

Borneo : J'ai du mal a faire le parcours complet en suivant tes fleches

Fractal : Comme tu l'as bien note, j'ai eu un peu de mal a torturer l'enonce avec ces histoires de 100 ou 60 segments et c'est pour ca que j'ai donne un exemple. J'ai fait de mon mieux mais je comprends l'incoherence dont tu parles. Le doute n'etait cependant pas permis car je disais clairement que le score 100 n'etait pas possible.

Bravo slaurent, tu ne t'es pas trompe et tu gardes le cap. Il va falloir prendre des risques si tu veux rester dans les premiers

Enfin Gloubi as tu la reponse 97 en images ?  une demo prouve que 93 est  vraiment le max.

A bientot.

minkus

Posté par minkus minkus

C'est plus serre au niveau du temps moyen grace a la reponse rapide de Vince909. Esperons que les defis suivants departagent les ex-aequo

Posté par gloubi gloubi

Bonjour minkus,

Argh,


je voulais dire 93 of course.
Sorry

gloubi

Posté par borneo borneo

Minkus, je vais refaire mon dessin. J'ai bien aimé cette énigme, qui m'a demandé très peu de temps, car je suis en plein dans la topologie.
En fait, la démo est très simple et il y a plein de sites internets où on peut en apprendre plus.

Posté par borneo borneo

Voilà, il m'a quand même fallu 10 minutes pour retrouver mon tracé

Posté par minkus minkus

Merci Borneo, en fait je crois que l'autre trace etait bon aussi mais quand je suis arrive au point d'arrivee en cours de chemin j'ai cru qu'il y avait un probleme. J'avais oublie qu'on pouvait passer deux fois par ce point d'arrivee

Posté par borneo borneo

Minkus, c'est le même !

Posté par minkus minkus

Oui je sais et c'est pour ca que je n'ai pas compris pourquoi tu as dit que tu as mis 10 minutes pour le retrouver.

Ah ca y est ! J'ai compris. Je croyais qu'il fallait suivre une fleche jusqu'au bout de la ligne et en fait non, pas au croisement 16 !!

Decidement

Posté par kiko21 kiko21

Bonsoir,

> Bornéo

Et combien de temps pour le fond "pas transparent" ??

A+, KiKo21.

Posté par kiko21 kiko21

> Bornéo

J'ai fait le mien avec excel...
Pas toi ?? Etonnant !!
Super pour les quadrillages et les flèches...

A+, KiKo21.

Posté par borneo borneo

Oui, excel, et après paint.

Posté par kiko21 kiko21

Excel fait bien les flèches...



A+, KiKo21.

Posté par slaurent128 (invité)

merci pour tes encouragements minkus.
par contre, ca tombe a l'eau maintenant que l'énigme des sucettes est finie
mais j'essaierai de rattraper mon retard, si cela est possible...