Inscription / Connexion Nouveau Sujet
Niveau énigmes
Partager :

Hexagones

Posté par
Diablow
25-05-14 à 23:38

Bonjour à tous,

Ce problème tourne dans ma tête depuis longtemps, mais je n'ai jamais pu lui apporter une réponse... Peut-être quelqu'un pourra-t-il m'aider ici... Le problème est simple dans son énoncé. Soit les 7 hexagones ci-dessous. On affecte à chaque sommet (notés de "a" à "x") les nombres de 1 à 24 de telle façon que la somme des 6 nombres de chaque hexagone reste constante. Il faut tout simplement savoir combien il existe de solutions.

Je ne suis jamais allé bien loin : on peut montrer que la somme de chaque hexagone est forcement comprise entre 65 et 87. assez élémentaire... L'exploration systématique des solutions via un ordi me semble assez difficile vu le nombre de possibilités ...

Quelqu'un a-t-il une idée ?
  

Hexagones

Posté par
dpi
re : Hexagones 26-05-14 à 11:27

Bonjour,

C'est un exercice plaisant.

J'arrive à 75 comme total médian.
On voit 12 sommets uniques
6 sommets doublés et 6 sommets triplés.

Je pense qu'un seule solution est possible avec bien sûr les symétriques

Posté par
dpi
re : Hexagones 26-05-14 à 17:59

Bonjour suite

Je considérais que l'hexagone central faisait
partie du jeu.

Donc le maximum est 87 et le minimum 63

On peut chercher la médiane avec  75

Posté par
weierstrass
re : Hexagones 26-05-14 à 20:54

Bonjour, j'ai crée un algorithme qui permet de résoudre le problème.
J'espère qu'il est assez efficace pour permettre de fournir la réponse.
Je fournirais les détails après l'avoir testé, je pense que dans tout les cas, ça peut te donner une idée...

Posté par
Diablow
re : Hexagones 26-05-14 à 21:10

Quelques résultats par trop difficiles à établir:

La somme sur chaque hexagone
Dans mon esprit, l'hexagone central faisait partie des hexagones dont la somme est constante.
Si on désigne par Ei les douzes nombres externes (abfj...), Mi les six nombres médians(denv...), Ci les six nombres centraux (him...), alors on a:
Ei + Mi + Ci = 300
Ei + 2Mi + 3Ci = 7*somme
Ci = somme
Ce qui donne, tous les calculs réalises, que la somme est comprise entre 65 et 85 (bornes incluses)

Symétrie sur la somme sur les hexagones
Il existe une symétrie des solutions par rapport à 75. Supposons qu'il existe une solution dont la somme sur les hexagones égale 75+. Si on remplace chaque nombre de la solution par 25 moins ce nombre, alors, il est simple de constater que la figure résultante est aussi une solution mais dont la somme vaut 75-

Réduire le nombre de configuration à explorer
Concernant les différentes solutions, d'une façon simple, plusieurs facteurs qui permettent de réduire le problème:
Rotations : h est inférieur au min (i, m, q, p, l)
Symétrie : m < p
Sur les bords : a<b et c<g et o<s et w<x et r<v et f<j
Si je compte bien, il existe 24! possibilités de disposer les nombres.
Si on tient compte des 3 points ci dessus on arrive à 24!/(2^8*3)=807875523090155520000 (ce qui fait beaucoup)
Le programme le plus rapide que j'ai réalisé évalue environ 10.000.000 de grilles par seconde. Soit environ 2.500.000 ans de calcul.

Posté par
Diablow
re : Hexagones 26-05-14 à 21:13

Citation :

de weierstrass:

Bonjour, j'ai crée un algorithme qui permet de résoudre le problème.
J'espère qu'il est assez efficace pour permettre de fournir la réponse.
Je fournirais les détails après l'avoir testé, je pense que dans tout les cas, ça peut te donner une idée...


je suis impatient...

Posté par
weierstrass
re : Hexagones 26-05-14 à 22:12

Comme tu t'y attendait, (et moi aussi un peu...), le programme semble un peu débordé par la tâche

Néanmoins, voila mon idée d'algorithme, je ne sais pas si tu avais pensé à un similaire, il permet quand même de réduire pas mal le nombre annoncé de grille à tester.
Il est basé sur un principe récursif,n codé sur python.
Il à l'air de pas mal marcher, on peut visualiser les étapes en mettant des "print" aprés chaque boucle "for"
Mon programme est assez laid et on peut sans doute le simplifier, par exemple en utilisant des listes pour éviter les [a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16...
Il n'utilise pas le procédé de récursion visant à appeler la fonction dans la fonction, car je ne connais pas grand chose aux programmes récursifs, et que ce n'était pas pratique pour les conditions, mais le principe reste le même.

Je n'ai pas une très grande experience informatique, si vous voyez une erreur dans le raisonnement , dans l'écriture de l'algorithme, ou des améliorations possibles, n'hésite pas à le faire remarquer (surtout que comme le programme est long, on est pas à l'abri d'une faute vicieuse.)
A part ça, le programme n'est pas si compliqué à comprendre:
Le principe:

 Cliquez pour afficher



Voilà, j'espère que tu as a peu près compris...

Pour t'aider à comprendre l'algorithme:
ak in [a1,a2,a3...]==True
on vérifie si la valeur que l'on viens d'attribuer n'aurait pas déjà été placée sur la grille

a1+a2+a6+a7<28
si cette somme est inférieure à 28, si on met derrière un 24 et un 23 pour compenser un si petit nombre, on aura pas 75, donc inutile de continuer avec ça...

continue
on viens d'observer que si on continuait avec la dernière valeur renseignée, ça ne marcherait pas, donc ceci fait revenir au début de la dernière boucle "for" et attribue le numéro suivant.Sans ça, l'algorithme effectuerait tout les "for situés derrière pour rien (quel gâchis )


Avec ça tu devrais pouvoir t'en sortir sur la compréhension de l'algorithme...
LE voici...
bon courage:
 Cliquez pour afficher


cordialement.

Hexagones

Posté par
dpi
re : Hexagones 27-05-14 à 06:58

Bonjour,

On apprécie le travail de Weierstrass !
On attend une autre méthode.

Ou j'en suis:
1/somme de 1 à 24 (n*n+1)/2 =300
2/sommets uniques  u (abcfgjorsvwx)
3/sommets doubles  d(dehiklmnpqtu)
4/total logique 450 (150 u +300 d)
5/chaque hexagone a 2u+4d ---> 75
6/on décide d'un seul cas englobant toutes les symétries.
7/on teste sur un tableur pour obtenir 75
et en réduisant les différences par groupes.
de 2 si possible.
8/le hasard fera le reste..

Posté par
weierstrass
re : Hexagones 27-05-14 à 07:06

Il y avait un problème, l'algorithme ne changeait pas de nombre si il était déjà présent dans la grille. je crois avoir réglé le problème, à checker...

 Cliquez pour afficher

Posté par
dpi
re : Hexagones 27-05-14 à 14:01

Bonjour,

je donne une solution avec une petite erreur...
abcdefghijklmnopqrstuvwxy
22 3 9 7 11 5 1 14 18 16 20 24 6 19 10 8 12 6 21 13 17 15 2 23

Posté par
weierstrass
re : Hexagones 27-05-14 à 19:29

Si j'ai bien compris ta méthode dpi, elle permet de trouver facilement une solution au problème.
Malheureusement, le but est un peu plus dur, c'est trouver l'ensemble des solutions...

Posté par
dpi
re : Hexagones 28-05-14 à 06:50

Bonjour,

En en trouvant une ,on en déduit un
ensemble par permutations et autres symétries.

Mais je pense qu'il n'y a pas de méthode générale,
mais plutôt comme au sudoku des séries de sous-méthodes
pour arriver à réduire la grille.

Ici par exemple, une sous méthode qui ne marche pas...
c'est de coupler les sommets voisins de telle sorte
que leur total soit 25 (en cherchant le fameux 12.5 de moyenne)

C'est le genre de topic qui irait bien en "énigme" n'est-ce
pas Godefroy ?

Posté par
weierstrass
re : Hexagones 28-05-14 à 18:09

Posté par
weierstrass
re : Hexagones 28-05-14 à 18:10

une infime partie des solutions:

 Cliquez pour afficher

moi non plus je m'attendais pas à ça...

Posté par
dpi
re : Hexagones 28-05-14 à 18:56

>Weierstrass

J'ai regardé et mis sur mon tableur...
tu dois avoir une erreur dans ton algorithme car
1/sur mon tableur cela ne fait pas des totaux identiques
2/le 24 sort 2 fois

Posté par
weierstrass
re : Hexagones 28-05-14 à 19:08

effectivement, je n'avais pas remarqué.
pour les totaux, je les trouves identiques, avec mon système de numérotation.
(enfin, j'en ai essayé deux et ça marchait...)

Posté par
weierstrass
re : Hexagones 28-05-14 à 19:16

Quel boulet, j'ai mis des plus au lieu de virgules...
Il en reste néanmoins beaucoup:

 Cliquez pour afficher


j'espère qu'ils sont bons cela...

Posté par
weierstrass
re : Hexagones 28-05-14 à 20:37

J'en suis à
Je vous fait la liste ou ça ira?

Citation :
L'exploration systématique des solutions via un ordi me semble assez difficile vu le nombre de possibilités ...

tu l'as dit (et surtout vu le nombre de solutions...)

Citation :
C'est le genre de topic qui irait bien en "énigme" n'est-ce
pas Godefroy ?

déjà que ca râle quand deux solutions sont possibles, je ne crois pas que certains en apprécieraient plus d'un million!

si la réponse de l'énigme se compte en Téraoctets, non merci...
Merci quand même pour cette énigme qui fut sympa à programmer, si tu en as d'autres dans le genre(avec moins de solutions, quand même ), je suis preneur...

Posté par
weierstrass
re : Hexagones 28-05-14 à 20:48

pardon, j'en suis à 1500000 solutions en à peine 1/2heure (sans compter les symétries...)

un résultat remarquable qui aurait pu améliorer mon programme:
notons:
S1 la somme des nombres au sommets n'appartenant qu'à 1 hexagone
S2 ---------------------------------------------------2 hexagones
S3 ---------------------------------------------------3 hexagones

on à S1+S2+S3 = 24*25/3 = 300
7*75-S2-2S3 = 300

trivialement, S3 = 75
On en déduit:
S2 = 75
S1 = 150

Posté par
Diablow
re : Hexagones 28-05-14 à 22:14

En ce qui me concerne, pour générer les différentes possibilités, en tenant compte des différentes symétries, j'utilise la numérotation des sommets ci-dessous.

ix represente le nombre affecté au sommet x

i1 est compris entre 1 et 11
i1 < i2
i1 < i3 et i3<>i2
i1 < i4 et i4<>i3 et i4<>i2
i1 < i5 et i5<>i4 et i5<>i3 et i5<>i2
i2 < i6 et i6<>i5 et i6<>i4 et i6<>i3
i1+i2+i3+i4+i5+i6 compris entre 65 et 85

On génère les noeuds intermédiaires (i7 à i12)
i7 de 1 à 24 et différent de  i1,i2,i3,i4,i5,i6
i8 de 1 à 24 et différent de  i1,i2,i3,i4,i5,i6,i7
i9 de 1 à 24 et différent de  i1,i2,i3,i4,i5,i6,I7,i8
i10 de 1 à 24 et différent de  i1,i2,i3,i4,i5,i6,i7,i8,i9
i11 de 1 à 24 et différent de  i1,i2,i3,i4,i5,i6,i7,i8,i9,i10
i12 est calculé, doit être compris entre 1 et 24 et différent de  i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11

On calcule ensuite les noeuds externes...

Après avoir réalisé quelques tests sur l'ordre de générer les sommets, je pense que procéder de cette manière est est la façon la plus efficace...

Hexagones

Posté par
weierstrass
re : Hexagones 28-05-14 à 22:30

ta méthode à l'avantage de ne pas compter plusieurs fois les grilles où les sommets n'appartenant qu'à un sommet sont intervertis(enfin je pense)
on peut aller un peu plus vite en considérant les inégalités sur ou  sommets, et en utilisant le résultat montré dans mon précédent post.
Quoi qu'il en soit, ton algorithme ne te sera pas très utile car je fais tourner mon algo depuis plus de 2 heures, et je viens de dépasser les 5 millions de possibilités...
Pourtant, mon algo n'est pas près de s'arrêter, car les listes créées commencent par 1,2,5,21,22...
ce qui montre que ça en est pas loin dans l'exécution...
ajoutons à ça les symétries, les 3 positions possibles pour le 1, et la somme des sommets différente de 75, je pense que l'on n'est pas près de savoir le nombre de solutions...
En tout cas, pour moi, le problème est classé, à moins qu'un rebondissement inattendu le rende un peu plus intéressant...

Posté par
Diablow
re : Hexagones 28-05-14 à 22:40

Pour le calcul de i12, le calcul est simple puisque la somme des ix pour x de 7 à 12 est égal à 5*S-300 où S est la somme sur l'hexagone central (sommets de 1 à 6).

La clef de ce problème est bien sûr d'évaluer le moins de configurations possibles (La méthode débile consisterait à examiner les 24! possibilités).

Pour cela, deux pistes:
- générer les solutions en affectant des valeurs aux sommets dans l'ordre le plus judicieux possible
- appliquer des relations qui permettent d'éliminer à priori des configurations. Par exemple toute configuration telle que la somme(ix avec x de 7 à 12) est différente de 5 * somme (ix avec x de 1 à 6) - 300 ne peut pas convenir. Cette simple relation permet d'éliminer très rapidement certaines solutions avant d'affecter les 24 sommets.

Pour moi, il faut arriver à trouver des relations entre les ix qui sont vérifiées uniquement quand la configuration est ok et appliquer ces relations pour éliminer des configurations le plus tôt possible dans la génération.

Posté par
weierstrass
re : Hexagones 28-05-14 à 23:12

Une question:
A quoi ça va te servir de déterminer les milliards de solutions?

Posté par
Diablow
re : Hexagones 28-05-14 à 23:36

Une réponse:
A rien. Mais comme dirait dpi, à quoi cela sert de faire un sudoku, ... Se prouver que l'on arrive à résoudre un problème que l'on juge au départ pas évident, pour lequel je n'ai trouvé aucune piste sue internet, à échanger quelques réflexions avec des personnes sur un fofo...
Pour ce problème, je ne me suis pas fixé comme but de lister les solutions mais juste de les compter...

Posté par
weierstrass
re : Hexagones 29-05-14 à 09:25

Ah d'accord, je croyais que tu voulais la liste de toute les solutions...
pour ma part, je chercherais plutôt d'un côté théorique, le nombre de solutions m'a l'air encore trop grand pour être traité par mon ordi...

Posté par
dpi
re : Hexagones 29-05-14 à 10:01

>Weierstrass

Tu as le record des lignes sur l'île et il faut
demander au gestionnaire de réduire tes octets
D'autant plus que j'ai passé la dernière à la moulinette
et je trouve pour les 6 hexagones
107 113 90 48 74 61 ...vous avez dit somme égale??

J'ai aussi testé celle de diablov
et je trouve:
45 53 73 61 77 169

Quant à "énigme" je dirai que le poseur devrait se contenter
d'une seule solution pour l'égalité hexagonale(tiens tiens !)

Posté par
weierstrass
re : Hexagones 29-05-14 à 10:20

1+2+3+22+23+24 = 75
1+12+20+19+2 = 75
1+21+15+18+16+3 = 75
...

je fais avec le système de numérotation proposé dans mon algorithme
(la flemme de tout remettre dans l'ordre )

Posté par
weierstrass
re : Hexagones 29-05-14 à 10:32

dpi
Je suis encore loin du record: Joute n°135 : Les nombres robustes

Posté par
dpi
re : Hexagones 29-05-14 à 12:49

Bonjour,

Mon test est dans l'ordre alphabétique du dessin initial,je ne vois pas dans quel ordre vous répondez ??

Posté par
weierstrass
re : Hexagones 29-05-14 à 13:05

celui de mon deuxième message

Posté par
weierstrass
re : Hexagones 29-05-14 à 13:20

J'ai modifié mon algo pour ne plus tenir compte des symétries, et des doubles sur les sommets n'appartenant qu'à un hexagone

 Cliquez pour afficher

ça trouve des solutions beaucoup moins vite(37000 en 8 min...), mais ça balaie beaucoup plus vite le nombre de configurations possibles...
Toutefois je suis encore loin de les compter toutes.
Diablow, ou en est ton algo, que l'on compare quelle numérotation est la plus efficace?

Posté par
castoriginal
re : Hexagones 29-05-14 à 14:18

Bonjour à tous,

considérons tout d'abord le dessin de départ amélioré pour scinder les hexagones ( la numérotation est la même que celle de l'énoncé.)

On ne considère pas  les 6 symétries obtenues par la rotation de la figure ni celles par retournement.

Hexagones

on voit qu'il y 6 points qui apparaissent 3 fois, 6 points qui apparaissent 2 fois et 12 points qui n'apparaissent qu'une fois.
Si l'on prend les hexagones 1,2,3, on a 13 points (nombres) qui sont définis sur les 24.
Le nombre de combinaisons est donc de C2413= 24!/(13!*11!) = 2496144 solutions
Si l'on examine maintenant l'hexagone 4, on peut encore définir 3 points f,j,n. Comme il reste 24-13=11 points non encore attribués
le nombre de combinaisons pour f,j,n est ce C113= 11!/(8!*3!) = 66 solutions
Passons à l'hexagone 5, on peut encore de finir les points r,u,v.
Il reste 24-16 = 8 points non attribués. Le nombre de combinaisons pour r,u,v est C83= 8!/(5!*3!) = 56 solutions
Il reste 3 points à définir pour l'hexagone 6: x,w,t.
On a déjà défini 19 points, il reste 5 points. Donc on a pour x,w,t un nombre de combinaisons égal à  C53=5!/(2!*3!) = 10 solutions.
Les deux derniers points de l'hexagone 7,  o et s sont alors déterminés.
Finalement, le nombre de solutions total est de :
2496144 * 66 * 56 * 10 *1 = 92.257.482.240  solutions

Amitiés

Posté par
castoriginal
re : Hexagones 29-05-14 à 14:23

J'ai oublié d'ajouter qu'il s'agit d'un nombre maximal sans tenir compte de l'égalité des sommes de chaque hexagone.

La méthode pour ce calcul suivra !

Posté par
weierstrass
re : Hexagones 29-05-14 à 20:07

pourquoi faire ces détours pour en arriver là?
Un peu de souci avec le dénombrement?

imaginons que tu veuilles placer tes 24 chiffres dans 13 emplacements,
plaçons le 1 dans le premier, le 2 dans le deuxième, ..., le douzième dans le douzième.
Pour le treizième emplacement, il reste 24-12 = 12 possibilités.
Imaginos maintenant que tu n'est fixé que les 11 premiers, le douzième peut prendre 13 valeurs possibles. On a alors 1312 possibilités.
Et ainsi de suite...
On arrive à 2423...1312 = 24!/11!
Eh oui, c'est un arrangement...


Faisons le calcul:
24!/(24-13)!11!/(11-3)!8!/(8-3)!5!/(5-3)!2 = 6.204481023

mais pourquoi ne pas calculer directement le nombre de possibilités?
24!/1! = 6.204881023

(notons qu'il était logique que ça ne pouvait être la combinaison. Pour l'ensemble, on aurait eu 24!/(24!1!) = 1, ce qui était peu probable )

en tout cas, merci quand même de ta contribution.

cordialement.

Posté par
Diablow
re : Hexagones 31-05-14 à 08:56

Merci de toutes ces contributions.
Voici quelques résultats donnés par un programme en C qui évalue systématiquement configuration en partant de l'hexagone central, puis de l'intermédiaire.Le prog a tourné une heure environ, les résultats sont pour des hexagones de somme 75 uniquement. Toute interpolation des résultats me semble assez aléatoire vu la variation du nombre de solution en fonction du triplet (1, 24, X) choisi.

Je donne aussi ces résultats pour comparer, histoire de voir si les programmes sont buggués.

Dans le tableau ci-dessous on peut lire que pour le triplet initial (AWR)=(1,23,18) il existe 481891 solutions en tenant compte des régles de symétries deja définies plus haut:
i1 < i2, i1 < i3, i1 < i4, i1 < i5, i2 < i6,
i13 < i14, i15 < i16, i17 < i18, i19 < i20, i21 < i22, i23 < i24

Théoriquement, je peux lancer sur chaque processeur de mon ordi un calcul avec des triplets différents (1xx), (2xx), etc... et additionner les résultats... mais bon...

Hexagones

Posté par
dpi
re : Hexagones 31-05-14 à 19:06

Bonjour,

Dommage qu'il n'y ait pas eu plus de participants..
Je pense que 75 est la seule somme qui fonctionne,
mais de là à le démontrer...

Posté par
weierstrass
re : Hexagones 31-05-14 à 19:09

tu as testé les autres sommes?
parce que vu le nombre de solutions pour 75, ça ne m'étonnerait pas que l'on en trouve quelques unes pour 74 ou 76.
Après, pour 67,68, je pense effectivement que l'on en trouvera pas.

Posté par
Diablow
re : Hexagones 31-05-14 à 22:30

Non, il existe des solutions pour tous les nombre entre 65 et 85.
Ci dessous quelques exemples pour

Hexagones

Posté par
Diablow
re : Hexagones 31-05-14 à 22:34

Avec des notations identiques, la suite ci-dessous

Hexagones

Posté par
dpi
re : Hexagones 01-06-14 à 06:59

Bonjour,

Ceci élimine définitivement ma comparaison avec
le sudoku qui en japonais signifie solution unique

Posté par
weierstrass
re : Hexagones 01-06-14 à 15:39

Je sens que l'on ne s'en sortira pas...
J'ai utilisé toute les symétries possibles, toutes les résultats établis,j'ai fixé un point, je n'ai considéré que les sommes égales à 75, j'ai fait toutner mon programme plusieurs heures et trouver des millions de solutions (bien qu'en tenant compte des symétries, et j'ai l'impression de toujours en être au même point. (mon algo n'est pas près d'avoir passé en revue toutes les solutions...)



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !