Forum de mathématiques - Bibm@th.net

abel

Membre

Inscription : 28-06-2015

Messages : 11

parcours geométriques sur un octogone

Bonjour,

Sur un cercle, on place huit points A, B, C, D, E, F, G et H de telle sorte que ABCDEFGH soit un octogone régulier.
On leur associe respectivement les chiffres 0, 2, 0, 6, 2, 0, 1, 6.

En partant d’un chiffre 0, sans lever le crayon, on trace un parcours de 7 segments différents
qui indique la date du 2 juin 2016 : 0-2-0-6-2-0-1-6.
On forme ainsi six angles dont les sommets sont sur le cercle.
La somme des six angles ne peut être inférieure à une certaine valeur M (en degrés)
qui est effectivement atteinte pour certains parcours.

On associe enfin à chaque parcours un nombre à 8 chiffres : chaque chiffre correspond au rang
de la lettre dans l'alphabet.
Par exemple, au parcours FBCHEAGH, on associe le nombre 62385178.

On note P la somme des nombres associés à tous les parcours ayant une somme d’angles minimale M.

Quelles sont les valeurs de M et P ?

Glozi

Invité

Re : parcours geométriques sur un octogone

Bonjour,
Merci pour l'énigme. Je me demande si c'est une question faite pour être traitée avec papier et crayon ou alors avec l'ordinateur ?
Avec l'ordi et un petit script python je trouve (sans avoir vérifié à la main).

▼Texte caché

M=270, P=155803482
avec des angles non orientés.

Bonne journée

abel

Membre

Inscription : 28-06-2015

Messages : 11

Re : parcours geométriques sur un octogone

Désolé, ce n'est pas la bonne réponse.
Tu devrait mettre des traces de debug dans ton code pour localiser le problème.

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : parcours geométriques sur un octogone

Bonjour,

▼mon interprétation

1) le parcours initial rejoint dans l'ordre 7 sommets adajacents, donc six angles. Chaque angle a l'ouverture maximale, donc il n'existe pas d'autre parcours avec la même somme angulaire que ceux similaires à celui-ci. La somme des 6 angles est donc de 360/8*6 = 270°.

2) en partant d'un sommet, il n'y a que deux façons de faire ce genre de trajet, soit dans le sens des aiguilles d'une montre, soit l'inverse. Comme on peut partir des huit sommets, il y a donc seize parcours avec une somme angulaire de 270°. Il suffit prendre dans l'ordre les numéros des sommets adjacents et d'opérer le glissement pour avoir ces seize parcours :

1234567
2345678
3456781
4567812
5678123
6781234
7812345
8123456
1876543
8765432
7654321
6543218
5432187
4321876
3218765
2187654

don la somme vaut 79999992

abel

Membre

Inscription : 28-06-2015

Messages : 11

Re : parcours geométriques sur un octogone

Désolé Ernst, ce n'est pas non plus la bonne réponse.
La somme M des angles doit être minimale (le tracé ne relie pas forcément des sommets consécutifs comme tu le précise dans ta solution)
Donc M est inférieur à 270°.

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : parcours geométriques sur un octogone

Bonsoir,

▼correctif

Oui, j'ai écrit une grosse bêtise : sur un octogone régulier l'angle ABC fait 135°, il y en a six, donc M = 810°.

Pour le reste, quand il est écrit « tous les parcours ayant une somme d’angles minimale M», moi je comprends que la somme (des six angles d'un parcours quelconque entre huit sommets) doit faire au moins 810°, et peut faire plus. Or il n'est pas possible de faire plus, et on n'a pas le droit de faire moins. C'est pourquoi je pense que ma somme est juste quand même...

Si maintenant la somme est égale ou inférieure, cela change tout, dans ce cas les parcours avec croisement sont possibles, et cela revient à dénombrer absolument tous les parcours possibles sans plus se soucier se soucier de l'angle. Dans ce cas on a 8! = 40 320 parcours différents tous valides, et la somme de ces parcours notés '12345678' et variations vaut 2 015 999 979 840, rien que ça. 

PETARDIER FERME

Membre

Inscription : 14-01-2023

Messages : 10

Re : parcours geométriques sur un octogone

Ce problème ressemble étrangement au défi Turing 173.

Glozi

Invité

Re : parcours geométriques sur un octogone

Bonjour,
Effectivement, je ne connaissais pas ces défis Turing mais ça à l'air intéressant, sinon nouvelle proposition :

▼Texte caché

Dans ma précédente réponse je supposais que le chemin devait forcément passer par chaque sommet au plus une fois mais en fait ce n'est pas forcé par l'énoncé. Sans cette contrainte je trouve
M * P= 133xxxxx705. Je mets des x pour ne pas donner directement le code de la solution de l'énigme sur de défi Turing.

Bonne journée

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : parcours geométriques sur un octogone

Bonjour,

▼troisième mouture

Ok, cette fois j'interprète l'énoncé de la façon suivante : on part de n'importe quel chiffre zéro (donc on peut choisir) et on doit simplement obtenir la date donnée sans lever le crayon, donc on repart du sommet sur lequel on est arrivé. Dans ce cas il s'agit de trouver le parcours ayant une somme minimale. Un tracé qui part de n'importe quel 0, va vers n'importe quel 2, et revient vers le même 0 va faire un tronçon 0-2-0 ayant un angle de... 0°, tadaa !

Je vais donc passer en revue tous les parcours possibles 0-2-0-6-2-0-1-6, calculer les angles pour chacun d'eux, et ne garder que le minimum.

Programme Python, bing résultat :

===== INFOS GÉNÉRALES =====
Nombre total de parcours compatibles : 432
Somme minimale des angles            : 135°
Nombre de parcours minimaux          : 1

===== PARCOURS MINIMAL =====
('F', 'E', 'F', 'D', 'E', 'C', 'G', 'D')  |  angles = 135.0°  |  nombre = 65645374

(jusqu'à la prochaine interprétation bien sûr ;-)

abel

Membre

Inscription : 28-06-2015

Messages : 11

Re : parcours geométriques sur un octogone

Je n'ai pas moi même la solution du problème mais le raisonnement suivant me semble être la bonne voie:

-Les chiffres ne servent pas: on peut partir de n'importe quel chiffre.
-le parcours des sommets ne suit pas l'ordre des sommets consécutifs
mais celui ajoutant un nouvel angle minimum.
-Le parcours peut suivre soit l'ordre du sens  trigonométrique, soit l'ordre du sens horaire.

Pour le sens horaire, le parcours en suivant les angles minimums est ABHCGDFE soit 12837465
(et les 7 autres permutations circulaires de ce nombre)
Pour le sens trigo, le parcours en suivant les angles minimums est AHBGCFDE soit 18273645
(et les 7 autres permutations circulaires de ce nombre)

les angles ajoutés à chaque fois sont identiques et égaux à l'angle ABH = 22.5° donc M=22.5*6=135°

Cela donne:
M= 135
P= 799999992
M*P= 107999998920
mais ce n'est pas la bonne réponse.
Quelqu'un peut-il compléter mon raisonnement y a t'il d'autre façons de parcourir les 8 sommets en faisant une somme d'angles de M=135°
D'autre part je ne comprends pas pourquoi le parcours donné dans l'énoncé passe deux fois par le point H.

Dernière modification par abel (15-01-2026 20:36:02)

Glozi

Invité

Re : parcours geométriques sur un octogone

Attention :
- Ernst, le chemin FEFDECGD est interdit car il utilise deux fois le segment [EF], cela est interdit par l'énoncé : tous les segments doivent être différents.
- On peut cependant utiliser plusieurs fois le même sommet (pourvu que tous les segments issus de ce sommet soient différents, c'est le cas du chemin FBCHEAGH, on utilise deux fois le point H avec les segments [CH], [EH] et [GH] qui sont bien tous différents).
- abel je crois que tu n'as pas compris le problème que tu as posé car les chiffres sont très importants !! Le chemin ABHCGDFE ne va pas car par la correspondance (ABCDEFGH)=(0,2,0,6,2,0,1,6) la date correspondant à ABHCGDFE est 02/60/1602 et non 02/06/2016 comme demandé.

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : parcours geométriques sur un octogone

Bonsoir,

Attention :
- Ernst, le chemin FEFDECGD est interdit car il utilise deux fois le segment [EF], cela est interdit par l'énoncé : tous les segments doivent être différents.
- On peut cependant utiliser plusieurs fois le même sommet (pourvu que tous les segments issus de ce sommet soient différents, c'est le cas du chemin FBCHEAGH, on utilise deux fois le point H avec les segments [CH], [EH] et [GH] qui sont bien tous différents).

Ah magnifique ! J'ai beau essayer de comprendre, il y a toujours des trucs que je loupe, donc un grand merci. Va falloir que je m'y remette, snifff, et donc que je trouve le temps. C'est déjà grâce à toi que j'ai compris que les sommets n'étaient pas à prendre dans l'ordre, et à partir du moment où je pouvais revenir sur certains, j'avais trouvé l'astuce de l'angle 0°, tout content que j'étais.

(hé hé, en fait le problème, pour des gens comme moi, c'est déjà le français)

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : parcours geométriques sur un octogone

Bonjour,

Allez hop, mouture suivante, cette fois j'ai essayé de suivre scrupuleusement l'énoncé...

▼et hop

- 8 points ABCDEFGH équidistants sur un cercle et formant les sommets d'un octogone régulier
- à ces sommets sont associés dans l'ordre les chiffres 0-2-0-6-2-0-1-6
- il s'agit de former cette séquence (qui peut se lire comme une date) de la façon suivante :
-- on démarre de n'importe quel sommet '0'
-- on se dirige vers n'importe quel sommet '2'
-- de là on se dirige vers n'importe quel sommet '0'
-- de là on se dirige vers n'importe quel sommet '6'
-- etc. en respectant :
--- un parcours qui trace des segments entre les sommets
--- qui forme une ligne continue donc qui repart obligatoirement des sommets sur lesquels il arrive
--- qui ne peut utiliser un segment déjà emprunté

Il existe 192 parcours légaux qui respectent ces contraintes. Chacun de ces parcours forme la date attendue de huit chiffres avec sept segments et six angles distincts. Si on fait la somme de ces angles pour chacun des parcours, on s'aperçoit que celles-ci varient entre 810° et 202,5°.

Seuls trois parcours totalisent la somme minimale de 202,5° et il s'agit de A-E-C-D-B-C-G-D, A-E-F-D-E-C-G-D et C-E-A-D-B-C-G-D.

Si on remplace les lettres ABCDEFGH par les chiffres 12345678 on obtient donc 15342374, 15645374 et 35142374 et leur addition donne 66130122.

En passant, je trouve très satisfaisant ce genre de tâtonnement, de correction ou d'amélioration grâce aux intervenants, c'est cool.

Glozi

Invité

Re : parcours geométriques sur un octogone

Bonjour Ernst,
Bravo, je crois qu'on a trouvé la même chose (et c'est juste d'après le site des defis Turing). J'ai été surpris par la facilité avec laquelle on pouvait oublier un point de l'énoncé (moi non plus je n'avais pas vu que le chemin FEFDECGD était interdit au départ, je m'en suis rendu compte quand le site des défis Turing m'a dit que ma réponse était fausse !).
Bonne journée

abel

Membre

Inscription : 28-06-2015

Messages : 11

Re : parcours geométriques sur un octogone

Bravo Ernst, je n'avais pas pris en compte l'ordre de passage 0-2-0-6-2-0-1-6
et le fait de repasser plusieurs fois par un même sommet.