Problème de maths vietnamien posé à des enfants de 8 ans...

[Adriweb]

Exercice qui a enflammé le net dernièrement...



"Neuf cases sont à remplir avec des chiffres de 1 à 9 (qu'il ne faut utiliser qu'une fois chacun). En ajoutant, multipliant, soustrayant et divisant au fur et à mesure (en suivant l’ordre des opérations –multiplications et divisions en priorité)" (Via http://www.slate.fr/story/101809/puzzle-maths-vietnam)

Question simple, mais résolution assez ardue

Pour le fun, j'ai fait ce petit code en C qui bruteforce la chose pour avoir toutes les solutions, et il m'en a trouvé et affiché 136 (en ≈ 22 ms. quand compilé en -Ofast).

Code: Select all

#include <stdio.h>
#include <stdint.h>

uint32_t solutionsFound = 0;

inline void swap(uint8_t *x, uint8_t *y) { if (x != y) { *x ^= *y; *y ^= *x; *x ^= *y; } }

void checkPermuts(uint8_t* array, uint8_t i, uint8_t length)
{
    if (length == i) {
        uint8_t* p = array;
        float result = p[0] + 13.0 * (float)p[1] / (float)p[2] + p[3] + 12.0 * (float)p[4] - p[5] - 11.0 + (float)p[6] * (float)p[7] / (float)p[8] - 10;
        if (result == 66.0) {
            printf("%d+13*%d/%d+%d+12*%d-%d-11+%d*%d/%d-10  =  66\n", p[0], p[1], p[2], p[3], p[4], p[5], p[6], p[7], p[8]);
            solutionsFound++;
        }
        return;
    }
    for (uint8_t j = i; j<length; j++) {
        swap(array+i, array+j);
        checkPermuts(array, i+1, length);
        swap(array+i, array+j);
    }
}

int main(int argc, char* argv[])
{
    uint8_t possibleInts[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    checkPermuts(possibleInts, 0, 9);
    printf("%d solutions found\n", solutionsFound);
    return 0;
}


Solutions trouvées :

Show/Hide spoilerAfficher/Masquer le spoiler

1+13*2/6+4+12*7-8-11+5*3/9-10 = 66
1+13*2/6+4+12*7-8-11+3*5/9-10 = 66
1+13*3/2+4+12*5-8-11+7*9/6-10 = 66
1+13*3/2+4+12*5-8-11+9*7/6-10 = 66
1+13*3/2+9+12*5-6-11+7*4/8-10 = 66
1+13*3/2+9+12*5-6-11+4*7/8-10 = 66
1+13*3/4+7+12*6-5-11+2*9/8-10 = 66
1+13*3/4+7+12*6-5-11+9*2/8-10 = 66
1+13*3/6+2+12*7-9-11+5*4/8-10 = 66
1+13*3/6+2+12*7-9-11+4*5/8-10 = 66
1+13*3/9+4+12*7-8-11+5*2/6-10 = 66
1+13*3/9+4+12*7-8-11+2*5/6-10 = 66
1+13*4/8+2+12*7-9-11+5*3/6-10 = 66
1+13*4/8+2+12*7-9-11+3*5/6-10 = 66
1+13*5/3+9+12*4-2-11+7*8/6-10 = 66
1+13*5/3+9+12*4-2-11+8*7/6-10 = 66
1+13*5/2+3+12*4-8-11+7*9/6-10 = 66
1+13*5/2+3+12*4-8-11+9*7/6-10 = 66
1+13*5/2+8+12*4-7-11+3*9/6-10 = 66
1+13*5/2+8+12*4-7-11+9*3/6-10 = 66
1+13*8/3+7+12*4-5-11+6*2/9-10 = 66
1+13*8/3+7+12*4-5-11+2*6/9-10 = 66
1+13*9/6+4+12*5-8-11+7*3/2-10 = 66
1+13*9/6+4+12*5-8-11+3*7/2-10 = 66
1+13*9/6+7+12*5-2-11+4*3/8-10 = 66
1+13*9/6+7+12*5-2-11+3*4/8-10 = 66
2+13*1/4+3+12*7-9-11+5*6/8-10 = 66
2+13*1/4+3+12*7-9-11+6*5/8-10 = 66
2+13*3/6+1+12*7-9-11+5*4/8-10 = 66
2+13*3/6+1+12*7-9-11+4*5/8-10 = 66
2+13*4/8+1+12*7-9-11+5*3/6-10 = 66
2+13*4/8+1+12*7-9-11+3*5/6-10 = 66
2+13*6/9+8+12*5-1-11+7*4/3-10 = 66
2+13*6/9+8+12*5-1-11+4*7/3-10 = 66
2+13*8/6+9+12*4-1-11+7*5/3-10 = 66
2+13*8/6+9+12*4-1-11+5*7/3-10 = 66
2+13*9/6+3+12*5-1-11+7*4/8-10 = 66
2+13*9/6+3+12*5-1-11+4*7/8-10 = 66
3+13*2/1+5+12*4-7-11+8*9/6-10 = 66
3+13*2/1+5+12*4-7-11+9*8/6-10 = 66
3+13*2/4+8+12*5-1-11+7*9/6-10 = 66
3+13*2/4+8+12*5-1-11+9*7/6-10 = 66
3+13*2/8+6+12*5-1-11+7*9/4-10 = 66
3+13*2/8+6+12*5-1-11+9*7/4-10 = 66
3+13*1/4+2+12*7-9-11+5*6/8-10 = 66
3+13*1/4+2+12*7-9-11+6*5/8-10 = 66
3+13*5/2+1+12*4-8-11+7*9/6-10 = 66
3+13*5/2+1+12*4-8-11+9*7/6-10 = 66
3+13*6/4+9+12*5-8-11+7*1/2-10 = 66
3+13*6/4+9+12*5-8-11+1*7/2-10 = 66
3+13*9/6+2+12*5-1-11+7*4/8-10 = 66
3+13*9/6+2+12*5-1-11+4*7/8-10 = 66
3+13*9/2+8+12*1-5-11+7*6/4-10 = 66
3+13*9/2+8+12*1-5-11+6*7/4-10 = 66
4+13*2/6+1+12*7-8-11+5*3/9-10 = 66
4+13*2/6+1+12*7-8-11+3*5/9-10 = 66
4+13*3/2+1+12*5-8-11+7*9/6-10 = 66
4+13*3/2+1+12*5-8-11+9*7/6-10 = 66
4+13*3/9+1+12*7-8-11+5*2/6-10 = 66
4+13*3/9+1+12*7-8-11+2*5/6-10 = 66
4+13*9/6+1+12*5-8-11+7*3/2-10 = 66
4+13*9/6+1+12*5-8-11+3*7/2-10 = 66
5+13*2/1+3+12*4-7-11+8*9/6-10 = 66
5+13*2/1+3+12*4-7-11+9*8/6-10 = 66
5+13*3/1+7+12*2-6-11+8*9/4-10 = 66
5+13*3/1+7+12*2-6-11+9*8/4-10 = 66
5+13*4/1+9+12*2-7-11+8*3/6-10 = 66
5+13*4/1+9+12*2-7-11+3*8/6-10 = 66
5+13*4/8+9+12*6-7-11+1*3/2-10 = 66
5+13*4/8+9+12*6-7-11+3*1/2-10 = 66
5+13*1/2+9+12*6-7-11+3*4/8-10 = 66
5+13*1/2+9+12*6-7-11+4*3/8-10 = 66
5+13*7/2+8+12*3-9-11+1*6/4-10 = 66
5+13*7/2+8+12*3-9-11+6*1/4-10 = 66
5+13*9/3+6+12*2-1-11+7*8/4-10 = 66
5+13*9/3+6+12*2-1-11+8*7/4-10 = 66
6+13*2/8+3+12*5-1-11+7*9/4-10 = 66
6+13*2/8+3+12*5-1-11+9*7/4-10 = 66
6+13*3/1+9+12*2-5-11+7*8/4-10 = 66
6+13*3/1+9+12*2-5-11+8*7/4-10 = 66
6+13*9/3+5+12*2-1-11+7*8/4-10 = 66
6+13*9/3+5+12*2-1-11+8*7/4-10 = 66
7+13*2/8+9+12*6-5-11+1*3/4-10 = 66
7+13*2/8+9+12*6-5-11+3*1/4-10 = 66
7+13*3/2+8+12*5-9-11+1*6/4-10 = 66
7+13*3/2+8+12*5-9-11+6*1/4-10 = 66
7+13*3/4+1+12*6-5-11+2*9/8-10 = 66
7+13*3/4+1+12*6-5-11+9*2/8-10 = 66
7+13*3/1+5+12*2-6-11+8*9/4-10 = 66
7+13*3/1+5+12*2-6-11+9*8/4-10 = 66
7+13*5/2+8+12*4-9-11+1*3/6-10 = 66
7+13*5/2+8+12*4-9-11+3*1/6-10 = 66
7+13*6/4+8+12*5-9-11+1*3/2-10 = 66
7+13*6/4+8+12*5-9-11+3*1/2-10 = 66
7+13*1/4+9+12*6-5-11+2*3/8-10 = 66
7+13*1/4+9+12*6-5-11+3*2/8-10 = 66
7+13*8/3+1+12*4-5-11+6*2/9-10 = 66
7+13*8/3+1+12*4-5-11+2*6/9-10 = 66
7+13*9/6+1+12*5-2-11+4*3/8-10 = 66
7+13*9/6+1+12*5-2-11+3*4/8-10 = 66
8+13*2/4+3+12*5-1-11+7*9/6-10 = 66
8+13*2/4+3+12*5-1-11+9*7/6-10 = 66
8+13*3/2+7+12*5-9-11+1*6/4-10 = 66
8+13*3/2+7+12*5-9-11+6*1/4-10 = 66
8+13*5/2+7+12*4-9-11+3*1/6-10 = 66
8+13*5/2+7+12*4-9-11+1*3/6-10 = 66
8+13*5/2+1+12*4-7-11+3*9/6-10 = 66
8+13*5/2+1+12*4-7-11+9*3/6-10 = 66
8+13*6/4+7+12*5-9-11+3*1/2-10 = 66
8+13*6/4+7+12*5-9-11+1*3/2-10 = 66
8+13*6/9+2+12*5-1-11+7*4/3-10 = 66
8+13*6/9+2+12*5-1-11+4*7/3-10 = 66
8+13*7/2+5+12*3-9-11+1*6/4-10 = 66
8+13*7/2+5+12*3-9-11+6*1/4-10 = 66
8+13*9/2+3+12*1-5-11+7*6/4-10 = 66
8+13*9/2+3+12*1-5-11+6*7/4-10 = 66
9+13*2/8+7+12*6-5-11+3*1/4-10 = 66
9+13*2/8+7+12*6-5-11+1*3/4-10 = 66
9+13*3/2+1+12*5-6-11+7*4/8-10 = 66
9+13*3/2+1+12*5-6-11+4*7/8-10 = 66
9+13*3/1+6+12*2-5-11+7*8/4-10 = 66
9+13*3/1+6+12*2-5-11+8*7/4-10 = 66
9+13*4/8+5+12*6-7-11+3*1/2-10 = 66
9+13*4/8+5+12*6-7-11+1*3/2-10 = 66
9+13*4/1+5+12*2-7-11+8*3/6-10 = 66
9+13*4/1+5+12*2-7-11+3*8/6-10 = 66
9+13*5/3+1+12*4-2-11+7*8/6-10 = 66
9+13*5/3+1+12*4-2-11+8*7/6-10 = 66
9+13*6/4+3+12*5-8-11+7*1/2-10 = 66
9+13*6/4+3+12*5-8-11+1*7/2-10 = 66
9+13*8/6+2+12*4-1-11+7*5/3-10 = 66
9+13*8/6+2+12*4-1-11+5*7/3-10 = 66
9+13*1/4+7+12*6-5-11+3*2/8-10 = 66
9+13*1/4+7+12*6-5-11+2*3/8-10 = 66
9+13*1/2+5+12*6-7-11+4*3/8-10 = 66
9+13*1/2+5+12*6-7-11+3*4/8-10 = 66
136 solutions found

Je suis bien conscient qu'un langage plus approprié peut probablement résoudre ça en 3 lignes (Python, hum hum ?)... mais bon, j'aime bien le C (et puis, l'algo en lui-même doit prendre 10 lignes de C, le reste... c'est pas la résolution en elle-même) - vous n'avez qu'a proposez votre bruteforceur en réponse à ce topic

[Adriweb]

Ce petit code Python équivalent me trouve 276 résultats au lieu de 136, et je sais pas trop pourquoi... (des histoires de mauvais typages et d'arrondis peut-être...)

Code: Select all

import itertools

solutionsFound = 0
for p in list(itertools.permutations([1, 2, 3, 4, 5, 6, 7, 8, 9])):
    if (p[0] + 13.0 * p[1] / p[2] + p[3] + 12.0 * p[4] - p[5] - 11.0 + p[6] * p[7] / p[8] - 10 == 66.0):
        print(p)
        solutionsFound += 1
print "Solutions found : " + str(solutionsFound)


[Adriweb]

En python, les calculs sur les réels peuvent être délicats à cause des arrondis (0.1+0.2<>0.3)...

Voici une solution qui donne les 136 réponses en 1s22 et... une ligne et demi:

Code: Select all

s={1,2,3,4,5,6,7,8,9}
[(a,b,c,d,e,f,g,h,i) for a in s for b in s-{a} for c in s-{a,b} for d in s-{a,b,c} for e in s-{a,b,c,d} for f in s-{a,b,c,d,e} for g in s-{a,b,c,d,e,f} for h in s-{a,b,c,d,e,f,g} for i in s-{a,b,c,d,e,f,g,h} if round(a+13*b/c+d+12*e-f-11+g*h/i-10,6)==66]

Le round permet de régler les pbs d'arrondis de calcul. Sans lui, on obtient que 128 réponses.

[Bisam]

Il me semble que vous trouvez bien trop de solutions !
Ce sont des enfants de 8 ans... Ils ne connaissent pas les nombres à virgule ou à peine et ne connaissent pas non plus les fractions.
Il ne faut (probablement) garder que les cas où les divisions sont exactes.

Comme on utilise les règles de priorité de calcul, on peut même tester avant de faire le calcul si cela va être divisible.
Pour améliorer, on pourrait se contenter de générer les permutations qui vérifient cela... et c'est sûrement ce que font les petits vietnamiens. On peut même encore diviser par 4 ce nombre en remarquant que les valeurs des cases p[6] et p[7] de la dernière multiplication peuvent être échangées, ainsi que les valeurs p[0] et p[3].

Code: Select all

import itertools

def findall():
    solutions = []
    envisageables = 0
    for p in itertools.permutations(range(1,10)):
        if (p[1] % p[2] == 0 and (p[6]*p[7]) % p[8] == 0):
           envisageables += 1
           if p[0] + 13*p[1]//p[2] + p[3] + 12*p[4] - p[5] - 11 + p[6]*p[7]//p[8] - 10 == 66:
               solutions.append(p)
    print("Nombre de permutations envisageables", envisageables)
    print("Nombre de solutions : ", len(solutions))
    return solutions

On trouve seulement 20 solutions (5 solutions différentes si on supprime les doublons dus aux permutations que j'évoquais plus haut). Voici les 5 solutions différentes (j'ai choisi à chaque fois p[0] < p[3] et p[6] < p[7] ) :
(3, 2, 1, 5, 4, 7, 8, 9, 6)
(5, 3, 1, 7, 2, 6, 8, 9, 4)
(5, 4, 1, 9, 2, 7, 3, 8, 6)
(5, 9, 3, 6, 2, 1, 7, 8, 4)
(6, 3, 1, 9, 2, 5, 7, 8, 4)

[Adriweb]

Bien sûr
(Lionel avait fait la même remarque, d'ailleurs)

Et pour le Python, il me manquait l'usage du "//", que j'avais déjà vu dans des codes à toi en plus