Hacker les maths avec l’algorithmie

Publié le par
(Last Updated On: 28 juillet 2021)

Saurez-vous résoudre ce problème de maths vietnamien donné à des enfants de 8 ans?SlateFR

La correction du problème de maths qui rend fou le webLe Figaro

Le titre vous évoque sûrement quelque chose, soit parce que vous avez l’habitude de voir passer ce genre de casse-tête sur les réseaux sociaux ou alors parce que vous êtes vietnamien et que le CE2 vous a traumatisé. Dans tous les cas, vous vous doutez bien qu’il s’agit d’un casse-tête loin d’être agréable à résoudre.

Le problème

C’est ce petit échiquier qui va vous rendre fou. L’objectif est de remplir les 9 cases vides en utilisant uniquement une seule fois tous les chiffres de 1 à 9. Le bon enchainement de chiffres choisi devra vous conduire au résultat 66. Vous pouvez essayez de le compléter à la main, mais sachant qu’il s’agit d’une équation à 9 inconnues, vous allez devoir faire preuve de beaucoup de patience. Attention ! les multiplications et divisions sont prioritaires sur les additions et soustractions…

Vous remplissez l’échiquier au hasard ? Vous avez une chance sur 2835 de trouver une bonne solution…

Dans les articles de presse, et les réactions d’internautes qui s’essaient à la résolution de ce problème, ça semble être la panique. Certains proclament qu’il y aurait deux solutions, d’autres plusieurs centaines. Bien que résoudre « mathématiquement » ce problème, par une mise en équation(s) quelconque ou tâtonnement pourra amuser les plus « matheux », il est frustrant de ne jamais obtenir la réponse finale et complète au problème posé.

Nous verrons dans cet article qu’un algorithme de base peut facilement résoudre ce genre de problème…

La/les solution(s)

Pour être honnête, je n’ai même pas essayé de chercher la solution à la main. Peut-être par fainéantise ? Quoi qu’il en soit, cela ne m’a pas empêché de trouver une solution au problème en quelques secondes uniquement. Et cela, à l’aide de mon ordinateur et d’un peu d’algorithmie ! C’est à dire qu’un programme va en quelque sorte travailler pour moi afin de trouver une solution au problème. L’avantage, c’est qu’il saura le faire très rapidement 1, et sans se tromper !

Le principe

Pour résoudre le problème, je sais que chaque case vide de l’échiquier devra être remplie par une des solutions prise dans l’ensemble suivant :  \(\{1,2,3,4,5,6,7,8,9\}\). Ainsi pour résoudre ce problème, je (ou plutôt mon ordinateur) vais résonner comme cela :

Imaginons que chaque chiffre est écrit sur une boule que je place dans une urne. Il y a donc 9 boules dans l’urne. Je ne vois pas quelle est la boule piochée.

– Algorithme 1 –
  1. Je place les 9 boules numérotées dans l’urne.
  2. Je pioche une boule au hasard, et je rempli la première case de l’échiquier avec le numéro inscrit sur la première boule. Comme je dois utiliser chaque chiffre une seule fois, je ne replace pas la boule piochée dans l’urne. Il reste alors 8 boules dans l’urne.
  3. Je pioche la deuxième boule et rempli la deuxième case.
  4. Je continue à remplir l’échiquier en piochant les boules jusqu’a ce que l’ soit vide (aka, l’échiquier rempli).
  5. Je vais calculer le résultat de mon opération :
    • \(case1+13*case2/case3+case4+12*case5-case6-11+case7*case8/case9-10\)
  6. Deux possibilités s’offrent à moi :
    • Le résultat fait 66, j’ai donc trouvé la solution au problème et peut m’arrêter là !
    • Le résultat ne fait pas 66, je recommande à l’étape 1, et ce autant de fois qu’il m’est nécessaire avant que le résultat fasse 66.

Bingo ! Je viens de décrire ce qui va constituer l’algorithme. Le problème, c’est que mon ordinateur ne parle pas français. En programmation, ces opérations peuvent être traduites en pseudo-code. Un pseudo code pourra être ensuite écrit dans un langage de programmation pour être interprété par un ordinateur. Dans cet exemple, le pseudo code sera le suivant :

Les réponses

Après avoir traduit ce pseudo code dans un langage de programmation (le language R 2, dans mon exemple), voici quelques exemples de solutions obtenues :

  • 7 – 6 – 4 – 8 – 5 – 9 – 3 – 1 – 2
  • 9 – 3 – 2 – 1 – 5 – 6 – 4 – 7 – 8

pour vérifier ces solutions, il suffit de faire l’opération. Par exemple pour la première solution :

7+13*6/4+8+12*5–9-11+3*1/2-10 = 66. C’est réussi !

Pour aller plus loin...

Probabilité d’avoir la bonne réponse ?

Déjà, il faut savoir qu’il y a 362880 façons d’écrire tous les chiffres de 1 à 9 dans un ordre différent. Mathématiquement, ça s’appelle le nombre d’arrangements. Avec 9 chiffres il se calcule avec 9 « factorielle », qui est noté avec un point d’exclamation \(9! = 9*8*7*6*…*2*1 = 362880\). Sur tous ces arrangements, il y en a certain nombre qui vont bien donner le résultat 66, nous en avons vu 3 exemples ci-dessus.

Là encore, c’est un algorithme qui nous permettra de dire combien de solution différentes il existe. Voici comment nous allons procéder :

Je vais exécuter l’algorithme 1 (présenté ci-dessus) un très grand nombre de fois, noté \(nbtirages\) et je vais  :

  • compter le nombre de fois que j’obtiens \(case1+13*case2/case3+case4+12*case5-case6-11+case7*case8/case9-10 = 66\), qu’on appellera \(nbcorrect\).
  • l’ensemble des ordres de chiffres « tirés dans l’urne » qui permettent d’arriver à 66, que l’on appellera \(solutions\).

Avec ces résultats, je peux déjà dire que la fréquence d’apparition de la bonne solution est :

\(freq =  \frac{nbcorrect}{nbtirages}\)

Par exemple, quand en réalisant 5 millions de fois l’algorithme 1, j’obtiens 1750 fois le nombre 66, la fréquence d’apparition de la bonne solution est donc \(1750/5000000 = 0.00035\). Plus le nombre d’exécutions de l’algorithme (\(nbtirages\)) est grand, plus cette fréquence a du sens. On peut dire que quand (\(nbtirages\)) tend vers l’infini, la fréquence d’apparition devient la probabilité d’obtenir 66 en tirant aléatoirement et sans répétition les chiffres de 1 à 9. C’est ce que vous avez pu lire dans le premier encart : une chance sur 2835

Solutions Uniques

Mais alors combien existe-t-il de solutions différentes pour arriver à 66 ?

Nous avons gardé en mémoire l’ensemble des ordres de chiffres qui permettent d’arriver à 66 dans l’objet \(solutions\). Il suffit alors de compter le nombre de solutions uniques. Cela revient à parcourir l’objet \(solutions\). A chaque fois que l’on rencontre solution nouvelle, jamais rencontrée auparavant, on incrémente notre compteur de 1. Un ordinateur sait très bien le faire pour nous !

Pour  5, 6 ou ou 8 millions de tirages, on obtient toujours 128 solutions uniques !  Le code associé est donné en bas de la page, pour ceux qui veulent vérifier.

La probabilité d’obtenir 66 en remplissant la grille au hasard est donc :

\(\frac{128}{9!} = 0.000352734 = \frac{1}{2835}\), donc une chance sur 2835 (tiens tiens, on retrouve la statistique de la partie précédente).

Les 128 solutions...

1-2-6-4-7-8-5-3-9
3-2-4-8-5-1-7-9-6
8-6-4-7-5-9-1-3-2
7-6-4-8-5-9-1-3-2
5-3-1-7-2-6-9-8-4
1-3-4-7-6-5-9-2-8
5-2-1-3-4-7-9-8-6
2-1-4-3-7-9-6-5-8
9-3-2-1-5-6-4-7-8
9-5-3-1-4-2-7-8-6
8-7-2-5-3-9-6-1-4
4-3-2-1-5-8-9-7-6
3-2-1-5-4-7-9-8-6
3-1-4-2-7-9-5-6-8
3-9-6-2-5-1-7-4-8
9-1-4-7-6-5-2-3-8
2-3-6-1-7-9-4-5-8
5-4-1-9-2-7-3-8-6
1-9-6-7-5-2-4-3-8
3-9-2-8-1-5-6-7-4
1-2-6-4-7-8-3-5-9
1-3-2-9-5-6-4-7-8
3-6-4-9-5-8-7-1-2
9-3-1-6-2-5-8-7-4
1-3-2-9-5-6-7-4-8
7-3-4-1-6-5-2-9-8
1-3-4-7-6-5-2-9-8
8-5-2-7-4-9-1-3-6
6-9-3-5-2-1-8-7-4
4-3-9-1-7-8-5-2-6
9-4-1-5-2-7-8-3-6
9-4-8-5-6-7-1-3-2
7-9-6-1-5-2-3-4-8
6-3-1-9-2-5-8-7-4
5-7-2-8-3-9-6-1-4
7-3-2-8-5-9-1-6-4
8-9-2-3-1-5-7-6-4
1-5-2-3-4-8-9-7-6
8-2-4-3-5-1-7-9-6
3-5-2-1-4-8-7-9-6
7-3-2-8-5-9-6-1-4
5-9-3-6-2-1-7-8-4
7-1-4-9-6-5-2-3-8
4-2-6-1-7-8-3-5-9
7-3-1-5-2-6-9-8-4
1-3-6-2-7-9-5-4-8
3-2-4-8-5-1-9-7-6
7-5-2-8-4-9-1-3-6
1-3-2-4-5-8-7-9-6
6-9-3-5-2-1-7-8-4
7-5-2-8-4-9-3-1-6
2-9-6-3-5-1-7-4-8
8-6-4-7-5-9-3-1-2
2-9-6-3-5-1-4-7-8
4-9-6-1-5-8-7-3-2
7-9-6-1-5-2-4-3-8
5-4-8-9-6-7-1-3-2
1-3-2-4-5-8-9-7-6
2-3-6-1-7-9-5-4-8
2-4-8-1-7-9-5-3-6
8-5-2-7-4-9-3-1-6
3-2-1-5-4-7-8-9-6
5-4-8-9-6-7-3-1-2
8-9-2-3-1-5-6-7-4
1-3-6-2-7-9-4-5-8
9-2-8-7-6-5-1-3-4
5-9-3-6-2-1-8-7-4
3-9-2-8-1-5-7-6-4
5-4-1-9-2-7-8-3-6
5-2-1-3-4-7-8-9-6
6-2-8-3-5-1-9-7-4
9-1-2-5-6-7-3-4-8
4-2-6-1-7-8-5-3-9
7-3-4-1-6-5-9-2-8
7-1-4-9-6-5-3-2-8
9-1-2-5-6-7-4-3-8
3-6-4-9-5-8-1-7-2
4-3-2-1-5-8-7-9-6
1-9-6-7-5-2-3-4-8
9-5-3-1-4-2-8-7-6
1-3-9-4-7-8-5-2-6
3-9-6-2-5-1-4-7-8
7-6-4-8-5-9-3-1-2
9-6-4-3-5-8-1-7-2
1-4-8-2-7-9-5-3-6
6-3-1-9-2-5-7-8-4
9-4-1-5-2-7-3-8-6
9-4-8-5-6-7-3-1-2
7-2-8-9-6-5-3-1-4
9-8-6-2-4-1-7-5-3
4-9-6-1-5-8-3-7-2
2-4-8-1-7-9-3-5-6
9-1-4-7-6-5-3-2-8
3-2-8-6-5-1-9-7-4
1-5-2-8-4-7-9-3-6
1-5-3-9-4-2-7-8-6
8-3-2-7-5-9-6-1-4
2-8-6-9-4-1-7-5-3
3-5-2-1-4-8-9-7-6
5-7-2-8-3-9-1-6-4
8-3-2-7-5-9-1-6-4
9-8-6-2-4-1-5-7-3
5-1-2-9-6-7-4-3-8
1-5-2-8-4-7-3-9-6
9-3-1-6-2-5-7-8-4
2-8-6-9-4-1-5-7-3
9-3-2-1-5-6-7-4-8
8-7-2-5-3-9-1-6-4
5-3-1-7-2-6-8-9-4
3-1-4-2-7-9-6-5-8
1-9-6-4-5-8-7-3-2
8-2-4-3-5-1-9-7-6
1-4-8-2-7-9-3-5-6
2-1-4-3-7-9-5-6-8
4-3-9-1-7-8-2-5-6
3-2-8-6-5-1-7-9-4
5-1-2-9-6-7-3-4-8
7-2-8-9-6-5-1-3-4
1-5-3-9-4-2-8-7-6
7-3-1-5-2-6-8-9-4
9-2-8-7-6-5-3-1-4
8-5-2-1-4-7-9-3-6
8-5-2-1-4-7-3-9-6
6-2-8-3-5-1-7-9-4
9-6-4-3-5-8-7-1-2
1-9-6-4-5-8-3-7-2
1-5-2-3-4-8-7-9-6
1-3-9-4-7-8-2-5-6

[collapse]

Autres solutions

Et si on change le résultat final ?

Admettons que vous ne voulez plus

\(case1+13*case2/case3+case4+12*case5-case6-11+case7*case8/case9-10 = 66\)

mais

\(case1+13*case2/case3+case4+12*case5-case6-11+case7*case8/case9-10 = \textbf{183}\)

Vous voilà bien embarrassés. Est-ce un résultat possible en utilisant toujours une seule fois tous les chiffres de 1 à 9 ?

Cette fois ci, la démarche est différente. On va garder le même principe de tirage dans une urne, mais on va systématiquement, à chaque tirage, s’intéresser au résultat final. A chaque tirage, on garde donc le résultat des opérations en mémoire.

Pour 400.000 de tirages, on va obtenir la distribution des solutions suivante :

Késako ? c’est la répartition en fréquence pour toutes les solutions obtenues. Le pic le plus haut (qui donne un résultat final de 96) est le résultat le plus fréquent (0.01, bon, ça reste quand même très minime). On remarque aussi qu’il n’est jamais arrivé de tomber sur un résultat final supérieur à 219. Vu le nombre de répétitions élevé, on peut considérer que ce tirage est un résultat impossible.

Pour rappel, nous avons 362.880 façons d’écrire tous les chiffres de 1 à 9 dans un ordre différent, mais ce n’est pas parce que nous avons fait 400.000 tirages que nous avons explorés toute les solutions !

Voici les codes qui permettent d’obtenir ces résultats. Le lecteur souhaitant se familiariser avec ce langage de programmation peut le faire ici.

Le code R pour obtenir une solution: (Algorithme 1)

urne = seq(1:9)
op = 0
cpt=0
while (op != 66){
  urne = sample(urne)
  op = urne[1]+13*urne[2]/urne[3]+urne[4]+12*urne[5]-urne[6]-11+urne[7]*urne[8]/urne[9]-10
}
print(urne)

Le code R pour compter les solutions uniques:

urne = seq(1:9)
op = 0
cpt=0
urnes = matrix(ncol = 9) #la matrice ajoute une ligne de "NA's", que l'on retirera dans l'affichage final.
nbrepetitions = 5000000
for (i in 1:nbrepetitions){
   urne = sample(urne)
  op = urne[1]+13*urne[2]/urne[3]+urne[4]+12*urne[5]-urne[6]-11+urne[7]*urne[8]/urne[9]-10
  if(op==66){
cpt = cpt+1
urnes <- rbind(urnes,urne)
  }
}

print(length(urnes)/9-1) #nombre total de solutions
print(length(unique(urnes))/9-1) #nombre de solutions uniques
print(unique(urnes)) #les solutions !

Le code R pour afficher toutes les solutions possibles:

urne = seq(1:9)
op = 0
cpt=0
ops = vector()
urnes = matrix(ncol = 9)
for (i in 1:400000){
  urne = sample(urne)
  op = urne[1]+13*urne[2]/urne[3]+urne[4]+12*urne[5]-urne[6]-11+urne[7]*urne[8]/urne[9]-10
  ops <- append(ops,op)
}

hist(ops,breaks = 100,las = 1, main = "Distribution des solutions",freq = F, ylab ="fréquence", xlab = "résultat")
Partager ce post

Sources

  1. en moins de 0.1 seconde !
  2. https://fr.wikipedia.org/wiki/R_(langage)