Mon score est de 91.

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.

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.

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 ?

Bonjour,

Je propose comme score maximal : 93.

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

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

Bonjour et merci pour l'énigme.

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

Réponse en image



@ plus, Chaudrack

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.

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....

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.

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

Je trouve une solution à 93 points.

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...

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

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.

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 !

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

Bonjour,

Je ne trouve pas mieux que

Ma soluce en image...

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

Merci et à bientôt, KiKo21.

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

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.

la réponse est 93

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

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

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

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

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

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

Bonjour minkus,

Argh,

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.

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

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

Minkus, c'est le même !

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

Bonsoir,

> Bornéo

> Bornéo

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

A+, KiKo21.

Oui, excel, et après paint.

Excel fait bien les flèches...



A+, KiKo21.

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...