Inscription / Connexion Nouveau Sujet

1 2 +


Posté par
LeDino
re : Enigmo 265 : Neuf chiffres pour deux multiplications 18-04-12 à 11:28

gagnéSkep : "Reprend moi si je me trompe..."

Je ne voudrais pas créer une habitude ...

Non désolé Skep, ta remarque n'est pas fausse en soi, mais dans le cas qui nous intéresse tu te plantes : l'agorithme de gryfo demande au moins 100 fois plus d'itérations (et probablement plusieurs centaines en pratique car de nombreux cas seront testés aléatoirement plusieurs fois...).

Et l'algorithme n'est certainement pas 100 fois plus simple dans les calculs qu'il effectue à chaque itération. Il est donc très largement moins performant qu'une recherche exhaustive.

Au départ, il n'avait d'ailleurs pas vocation a être plus performant, mais juste à être programmé plus vite ou plus "naturellement", dans l'esprit de Gryfo. Du moins j'imagine...

Posté par
Skep
re : Enigmo 265 : Neuf chiffres pour deux multiplications 18-04-12 à 11:37

gagnéOui ici je pense aussi que la brute force est plus rapide mais ce que je voulais dire c'est qu'on ne peut pas dire que ce programme est plus rapide parce qu'il fait moins d'iterations.
Enfin c'est ce que j'ai deduis après quelques programmes

Posté par
LeDino
re : Enigmo 265 : Neuf chiffres pour deux multiplications 18-04-12 à 12:11

gagnéSi Skep, dans ce cas précis on peut parfaitement dire que l'exhaustif est nettement plus rapide que l'aléatoire.

Parce que la disproportion entre les nombres d'itérations est considérable : l'aléatoire demande plusieurs centaines de fois plus d'itérations !

Et si tu regardes les traitements effectués à chaque itération, il n'y a aucune raison pour que l'exhaustif soit plus couteux que la recherche aléatoire : la condition pour détecter une solution étant la même à tester...

On peut même supposer que la génération des neuf nombres, requise à chaque itération de l'algorithme aléatoire, induise un surcoût et donc un désavantage supplémentaire.

Donc si j'avais à parier sur l'un ou l'autre des algorithmes, je mets un gros billet sur la méthode exhaustive.
Si tu crois l'inverse, je t'invite cordialement à miser sur ton hypothèse : j'accepte d'avance le pari, à une hauteur qui ne mette toutefois pas sérieusement en péril tes économies ...

Posté par
LeDino
re : Enigmo 265 : Neuf chiffres pour deux multiplications 18-04-12 à 13:36

gagnéAprès analyse, je rectifie une de mes hypothèses sur le nombre d'itérations requises pour l'algorithme aléatoire de Gryfo :

A chaque cycle de recherche à partir du moment où il a trouvé une valeur MAX qui semble stable par la suite, le nombre d'itérations requises pour tomber sur la valeur MAX en tirant aléatoirement parmi N=9! combinaisons possibles, est en moyenne de... N=9!.

Il en résulte que le nombre d'itérations requises en 100 cycles, sera en moyenne de 100 fois N, donc environ 36 millions.

Démonstration :

Pn = Probabilité de trouver un nombre donné 'X' à la n-ième itération
Pn = p.(1-p)^(n-1)    (on tire n-1 fois à coté du nombre X, et 1 fois sur le nombre X).
Avec p=1/N (N: taille de l'échantillon)

Donc l'espérance mathématique n (nombre d'itérations requises pour trouver X) sera :
E(n) = Somme 1,infini[ n.Pn ]
E(n) = Somme 1,infini[ n.p.(1-p)^(n-1) ]
E(n) = p.Somme 1,infini[ n.(1-p)^(n-1) ]
E(n) = p.Somme 1,infini[ -(1-p)^n ]'       (dérivée...)
E(n) = -p.[1-(1-p)^infini]/[1-(1-p)]'      (série géométrique...)
E(n) = -p.[1/p]'
E(n) = -p.[-1/p²]
E(n) = 1/p
E(n) = N
Ce qu'on voulait démontrer...

Posté par
LeDino
re : Enigmo 265 : Neuf chiffres pour deux multiplications 18-04-12 à 14:00

gagnéEn résumé, et à retenir à l'avenir pour qui serait tenté par une méthode aléatoire (pour s'épargner la programmation d'un algorithme exhaustif qui serait jugé trop complexe à écrire ou trop lourd à exécuter...), sur un problème de recherche d'optimum dans un espace de N possibilités à évaluer :

Lorsque l'agorithme aléatoire aura sélectionné après quelques cycles un MAX candidat plausible à être l'optimum (c'est à dire à partir du moment ou la meilleure solution trouvée reste stable), il faut compter encore dix cycles supplémentaires pour être sûr à 99,9% que c'est la solution, vingt cycles pour une certitude à 99,9999% et trente cycles pour un seuil d'erreur de l'ordre du milliardième (2^-30).

Chaque cycle coutera en moyenne autant qu'une recherche exhaustive.
Donc l'aléatoire serait dix à trente fois moins performant (selon le seuil d'erreur attendu : de 1 sur mille à 1 sur 1 milliard).

Posté par
Skep
re : Enigmo 265 : Neuf chiffres pour deux multiplications 18-04-12 à 17:38

gagnéSympa le calcul pour connaître la probabilité sur un algorithme basé sur l'aléatoire, merci
par contre je n'ai jamais dit que l'algorithme de gryfo était plus rapide justement ici le brute force était adéquate comme je l'ai dit au dessus mais dans certains cas comme les nombres premiers (toujours le même exemple ) il vaut mieux utiliser l'aléatoire
et non je ne miserai pas ma maudique fortune sur la rapidité de l'algorithme de Gryfo (sans être méchant bien sur )

Citation :
Oui ici je pense aussi que la brute force est plus rapide

Posté par
Benwat
re : Enigmo 265 : Neuf chiffres pour deux multiplications 18-04-12 à 18:07

Ouais... Merci de m'avoir répondu.

Du coup, faire 9! opérations, si ça reste la solution la plus fiable, c'est pas non plus insurmontable pour un PC, mais niveau mathématique, c'est pas très porté sur le raisonnement.  ^^

Bien sur, il y a moyen de reflechir avec le 5 notemment, ou sur les diviseurs, ou je sais pas trop quoi, et de réduit le nombre de calcul à faire.

Posté par
Skep
re : Enigmo 265 : Neuf chiffres pour deux multiplications 18-04-12 à 18:15

gagnédésolé avec LeDino on était dans notre trip
bah pour ce genre de problème soit tu utilises l'outil informatique et tu trouves ton résultat en 10 min (temps de reflexion + temps d'execution ) ou sinon tu veux te faire plaisir avec tes outils mathématiques mais tu vas mettres 2h minimum.
Et bon comme quelqu'un te la dit il faudra que tu fasse 9! itérations pour être sur et certain de ton résultat .. Donc ici un programme s'impose à mon avis

Posté par
Benwat
re : Enigmo 265 : Neuf chiffres pour deux multiplications 18-04-12 à 19:03

Me faire plaisir... ouais... bah ouais, justement, c'est réfléchir qui me fait plaisir, pas écrire for i from 1 to 9.
J'adores l'algo, mais bon là c'est un peu bourrin.

Posté par
Skep
re : Enigmo 265 : Neuf chiffres pour deux multiplications 18-04-12 à 19:25

gagnéc'est le concept de la brute force
mais tu peux toujours trouvé des petites conditions pour te faire réfléchir et gagner en temps d'execution

Posté par
LeDino
re : Enigmo 265 : Neuf chiffres pour deux multiplications 18-04-12 à 19:54

gagné@ Skep : Bon c'est dommage que tu ne paries pas ...
Mais je te chambrais un peu, j'avais bien capté que tu avais compris que l'algorithme aléatoire était moins performant ici.

@ Benwat : Toi tu proposes quoi comme approche mathématique ?
T'as bossé un peu le truc ?
Parce qu'apparemment, ici tout le monde a utilisé l'ordi (sauf erreur)...
Si quelqu'un avait eu une démarche mathématique, j'imagine qu'il aurait pris plaisir à la présenter, parce qu'elle doit être assez balaise...

Posté par
LeDino
re : Enigmo 265 : Neuf chiffres pour deux multiplications 18-04-12 à 22:42

gagné@ Benwat :

J'avais directement cherché une solution sous Excel pour être tranquille...
Mais puisque tu poses la question, il y avait au moins une manière de résoudre le problème à la main.

L'idée est rechercher un produit maximal tel que :
ab * cde = fg * hi

Les unités b, e, g, i ne doivent pas être un 5.
a et c ne doivent pas être trop grands de sorte que leur produit ne doit pas dépasser 8 (sans quoi ab * cde dépasserait 100000 et aurait un chiffre de trop pour être atteignable par fg * hi).

Il est tentant d'essayer de choisir f, g, h, i parmi 6, 7, 8, 9...
pour que le produit ait toutes les chances d'être maximal.

Dans cette hypothèse, il faut calculer simplement 4!/2 = 12 produits possibles pour fg * hi, pris parmis 6789.

Puis on compare les résultats produits ainsi avec les résultats produits par les combinaisons issues de ab * cde pris parmi 12345.

Il n'y a qu'une vingtaine de cas à évaluer qui respectent 6 <= a*c <= 8.
12 * 534,  12 * 543
13 * 524,  13 * 542
14 * 523,  14 * 532
21 * 354,  21 * 453
23 * 451,  24 * 351
31 * 254,  31 * 245,  
34 * 251,  
41 * 253,  
43 * 251,  
52 * 134,  52 * 143,  
53 * 124,  53 * 142,  
54 * 123,  54 * 132,  

En calculant ces différents produits, on en trouve un qui est également présent dans la liste des produits issus des 24 combinaisons de fg*hi.

Le tour est joué, puisque nous tenons une solution, et qu'elle ne saurait être dépassée puisque nous avons tenté tous les cas possibles avec les chiffres maximums pour fg et hi.

Donc le problème était trouvable à la main...
Le coup de chance c'est qu'une solution existe avec fg * hi parmi 6789.
Non seulement la recherche est rapide de ce fait, mais la confirmation qu'il s'agit de l'optimum en découle également.

Si nous n'avions pas eu ce "coup de chance", peut-être que le procédé présenté aurait quand même été généralisable en étendant de proche en proche las élection defg * hi à plus de nombres (choisis parmi 56789 à l'étape suivante et ainsi de suite).

Posté par
Benwat
re : Enigmo 265 : Neuf chiffres pour deux multiplications 19-04-12 à 18:41

Bossé "un peu" oui, mais bon. Conclure que 5 n'est pas une unité, que le produit est pair, que le chiffre des centaines est "assez petit", j'ai pas trop trop poussé plus loin, parce qu'ensuite je suis partie sur l'idée suivante :

il faut que b*e et h*i ait le même chiffres des unités. Et je voulais étendre ça au chiffre des dizaines etc... mais ça marche pas trop bien à cause des retenues (normal !).

Merci beaucoup en tout cas.  ^^

Posté par
totti1000
re : Enigmo 265 : Neuf chiffres pour deux multiplications 21-04-12 à 03:44

gagnéMerci LeDino et RickyDadj pour vos félicitations !

Posté par
Gryfo
re : Enigmo 265 : Neuf chiffres pour deux multiplications 21-04-12 à 13:35

gagnéLa vérité c'est que je savais que manuellement avec ma petite tête je n'aurais jamais été capable de trouver la solution de l'énigme.
Alors je me suis tout simplement donné les moyens de la réussir en créant un programme qui faisait le sale boulot à ma place (la création du programme en elle-même n'est vraiment pas difficile avec des bases)
Effectivement on peut trouver ça un peu... "Flemmard" comme attitude mais je ne pouvais pas faire autrement

Le programme n'avait qu'un défaut : celui de n'être pas sûr à 100%. Il y avait une probabilité qu'il y aie une solution plus grande que le MAX (comme l'appelle LeDino). Probabilité infime, effectivement, mais elle était bien là. Donc mon "97%" correspond bien à de la quasi-certitude et ne constitue pas une valeur rigoureuse, je n'ai d'ailleurs absolument pas le niveau pour trouver l'exacte valeur

En tout cas ça me fait plaisir de voir que mon petit programme vous intéresse

Posté par
LeDino
re : Enigmo 265 : Neuf chiffres pour deux multiplications 21-04-12 à 15:33

gagnéBonjour Gryfo,

Je pense qu'une large majorité de joueurs a utilisé un programme ou Excel pour trouver la solution.

Ce serait intéressant que ceux qui ont trouvé la solution "à la main" le disent, en indiquant éventuellement la démarche qu'ils ont suivie (probablement une approche similaire à celle que j'ai proposée juste au-dessus...).

Juste un détail sur le niveau de confiance :

97% ne constitue pas de la "quasi certitude".

Si je dois t'injecter un vaccin qui a des effets secondaires potentiels et qui te laisse 97% de chances de survivre, tu feras une sérieuse grimace avant d'accepter l'injection ... 97% est un seuil de confiance qui est acceptable pour une prise de décision dont les conséquences ne sont pas dramatiques en cas d'erreur.

En l'occurrence, pour t'éviter le poisson (qui est assurément le degré le plus élevé dans l'échelle des événements dramatiques )...), tu avais pris soin de prendre de larges précautions en répétant 96 fois le cycle de recherche d'un optimum meilleur que ton MAX.

En procédant ainsi, tu t'es convaincu (à juste titre) d'avoir trouvé l'optimum. Ton degré de conviction, purement intuitif puisque tu n'as pas fait le calcul, était très élevé et bien meilleur que 97%.

97% est une présentation "trompeuse", car en matière de seuil de confiance, il y a une grande différence pratique entre 97% ("je suis assez sûr de moi") et 99,9% ("je suis très sûr de moi") et 99,9999% ("le doute est infime")...

Et toi tu as carrément prouvé ton résultat avec un seuil de :
99.999999999999999999999999999% !
Soit un doute quasi infinitésimal...


Pour ce qui est du calcul de ce seuil de confiance, je l'ai présenté plus haut.
Il est tout à fait à ta portée.

A chaque cycle à partir du moment où tu as atteint la valeur MAX, ton programme aléatoire a autant de chances de tomber à nouveau sur MAX que de tomber sur un hypothétique optimum supérieur à MAX. Donc chaque cycle supplémentaire qui retombe invariablement sur MAX, divise par deux la probabilité que MAX ne soit pas l'optimum. Tous les dix cycles, cette probabilité est divisée par 2^10 = 1024 ~ 10^3.

La difficulté ici est de comprendre comment procède l'algorithme et d'identifier les cas équiprobables possibles (tomber sur MAX ou tomber sur mieux que MAX).
Mais le calcul au final s'avère très simple... et il confirme spectaculairement l'intuition que tu as eu au départ d'avoir trouvé le bon résultat.

Posté par
Chatof
re : Enigmo 265 : Neuf chiffres pour deux multiplications 21-04-12 à 19:06

gagnéBravo Totti pour cette cinquième victoire de suite.
Même si Nofutur n'avait pas chuté, Totti restait en tête.
Rapide et sans faute, encore bravo !

Posté par
totti1000
re : Enigmo 265 : Neuf chiffres pour deux multiplications 21-04-12 à 21:24

gagnéMerci Chatof

Bravo à toi aussi, car tu n'as commis qu'une seule erreur depuis début 2012, et donc deux sans faute sur les deux derniers mois !

1 2 +


Challenge (énigme mathématique) terminé .
Nombre de participations : 0
:)0,00 %0,00 %:(
0 0

Temps de réponse moyen : 107:16:27.


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 !