Auteur Sujet: math et molkky  (Lu 1064 fois)

Hors ligne varzil

  • Christophe
  • Appelez moi maître
  • *****
  • Messages: 576
math et molkky
« le: octobre 28, 2022, 11:11:04 am »
Parce que je ne vais pas répondre par SMS à la question que Didier m'a posé, je vais poster ici.
La question est de savoir combien il y a de combinaisons au molkky pour atteindre 50 sachant que 12+12+12+12+2 est différent de 12+2+12+12+12

Pour répondre rapidement à Didier, j'ai déjà un algorithme de début 2020 puisque qqn m'avait demandé (suite à un entretien d'embauche), le nombre de façons d'obtenir 14 en faisant des sommes de 1,2 et 3. C'est pareil en remplacant 14 par 50 et 3 par 12
Le problème se rapproche du nombre de compositions d'un entier https://fr.wikipedia.org/wiki/Composition_(combinatoire) qui est très simple à dénombrer sauf qu'ici, on veut se limiter à des valeurs plus petites que 12.
Notons que les 2^49 compositions fournissent une borne supérieure au problème de environ 5,6*10^14 soit 560 mille milliards (c'est peu par rapport au nombre de parties d'échecs ;))

Mon algorithme c'est que je calcule toutes les compositions, parce que c'est facile, et ensuite je garde seulement celles qui utilisent les valeurs acceptables (ici entre 1 et 12). Sauf que le temps de calcul est doublé à chaque fois qu'on augmente de 1 et si je trouve environ 1 million de possibilités pour jouer au molkky en 21 points en 16 sec de calculs, pour avoir la réponse pour 50 il me faudrait environ 272 ans ( on peut sans doute diviser par 10-50 en réécrivant le code dans un autre langage plus rapide mais sans doute que la mémoire de l'ordi saturerait avant puisqu'il me faudrait environ 1 million de téra-octets...)
Bref, je n'ai pas la réponse pour des raisons pratiques mais on devrait se situer autour de 100 à 500 mille milliards je pense
« Modifié: octobre 28, 2022, 11:21:18 am par varzil »

Hors ligne Didshrek

  • Didier en vrai !
  • Administrator
  • Hardcore master
  • *****
  • Messages: 4275
  • Et si on jouait... juste pour le plaisir de jouer?
Re : math et molkky
« Réponse #1 le: octobre 28, 2022, 11:54:59 am »
Je savais que je pouvais compter sur toi  :)
Ceux qui disent : "Il y a un temps pour jouer et un temps pour travailler", ne jouent jamais.