Math puzzle for Vietnamese eight-year-olds | Hacker News Reader

Math puzzle for Vietnamese eight-year-olds

theguardian.com

17 pointsghosh22 comments

It's not that bad to do by hand. It took me a few minutes, while I was also busy consuming a tasty snack [1].

The keys are the 13 x _ / _ and the _ x _ / _.

Those are the only terms that involve division, and since we need to come out with an integer in the end, we must either have those two terms each individually be integers, or they must both be fractions that add to an integer.

I focused on that second possibility, because that's the kind of sneaky thing people who make puzzles to do.

There are a couple ways to do this. I started with 13 x _ / 3 for the first and _ x 6 / 9 for the second.

Then I simply started going through the possibilities for 13 x _, and for each picking the smallest value using the remaining digits for _ x 6 / 9 that made the sum of these two terms an integer.

There are only 6 cases here. For each of those cases, you finally end up with something of the form _ + _ - _ + 12 x _ = I, where I is an integer. There will only be one or two possible values from the digits remaining that can go in the 12 x _ part and get you close enough to I that it is even worth continuing with that case. It's then trivial to see if the remaining 3 digits can be fit into _ + _ - _ to give what you need (and sometimes you can even skip that by doing a parity check).

Annoyingly, it is the last of the 6 cases that works, giving

  1 + 13 x 8 / 3 + 7 + 12 x 4 - 5 - 11 + 2 x 6 / 9 - 10 = 66
  _        _   _   _        _   _        _   _   _

[1] Tim's Cascade Style Potato Chips, Original Lightly Salted; Hostess Cupcakes (the orange ones, not the chocolate ones); Pepsi

I used a similar strategy, but assumed to puzzle maker was a nice person and each of the 13 x _ / 3 and _ x 6 / 9 resulted in a whole number.

I ended up with:

[6] + 13 x [3] / [1] + [9] + 12 x [2] - [5] - 11 + [8] x [7] / [4] - 10 = 66

Great snack btw.

The obligatory Python says that there are 120 solutions, or %0.03 of the possible permutations. It seems almost cruel to subject 8 year-olds to a problem like this, even if they have enough intuition to reduce the problem space a bit. Maybe it says more about the teacher than the students.

    from itertools import permutations
    
    def f(a, b, c, d, e, f, g, h, i):
        return a + 13 * b / c + d + 12 * e - f - 11 + g * h / i - 1
    
    solutions = [p for p in permutations(range(1, 10)) if f(*p) == 66]
    
    print(len(solutions))

Agreed. I kept holding out hope that there was some clever solution I just couldn't see, but no, the only sane solution is to do exactly what you did and write a script. What's the point in making students slog through endlessly plugging numbers into a weirdly formatted equation?

Raise them to be diligent workers who never complain about boring tasks?

You need to swap the 1 at the end for an 11.

Also, this code for me returns 2672 solutions although I don't believe all are valid due to integer division. Perhaps a python 2 -> python 3 difference? (py2 here)

At the end should be 10.

And with checks to have only divisions without the remainder I get 20 solutions, the first one being (3, 2, 1, 5, 4, 7, 8, 9, 6)?

Yes, I get the same.

Edit - Ah yes, 10, sorry.

I have the same number, do you think there is a reason why they are not all valid? EDIT: actually the number I calculate is 2796. Also using Python 2..

Partly it might be due to needing "-10" at the end rather than -1 (I think I may have corrected it to -11 by mistake).

However, larger is the difference in how division works.

Python2: 3 / 2 => 1

Python3: 3 / 2 => 1.5

Would forcing the integer result fix this problem? Something like:

    def f(a, b, c, d, e, f, g, h, i):
        return a + int((13 * b * i + g * h * c) / (i * c)) + d + 12 * e - f - 11 - 10

If I try it like this, I still have the same number of solutions... Maybe I'm missing something..

EDIT: code formatting...

No, the problem is the other way around. Keeping them as integers and just using '/' is what's causnig the problem. You can either force them to be floats (not the result, the parameters in the calculation), or you can explicitly look for divisions that have remainders.

128 actually, you missed the last char of your snake. ( -1 should be -10 )

That script (with the -1 at the end replaced with the correct -10) does not work, at least on Python2. It misses the solution (1, 8, 3, 7, 4, 5, 2, 6, 9).

Here's a fixed script:

    from itertools import permutations

    def f(a, b, c, d, e, f, g, h, i):
        return a + (13 * b * i + g * h * c) / (i * c) + d + 12 * e - f - 11 - 10

    solutions = [p for p in permutations(range(1, 10)) if f(*p) == 66]

    print(len(solutions))

How does operator precedence work in the snake? Is it normal or does it proceed purely sequentially?

From the article it follows normal order of operations. (Although the snake presentation certainly made me think otherwise at first.)

It's easy enough to write it as an equation with 9 variables. Collect the integer terms, etc. There are a few constrains you can come up with knowing that they're all natural numbers. Beyond that though, I don't see a clever way to solve it beyond plugging in combinations, of which there would be a lot. Could write a script in 5 minutes to do it, but I guess that'd be cheating.

PHP program to solve this puzzle. <?php while(1) { $numbers = '123456789'; $numStringLength = strlen($numbers); $num1=$numbers[rand(0, $numStringLength - 1)];

$numbers=str_replace($num1,'',$numbers); $numStringLength = strlen($numbers); $num2=$numbers[rand(0, $numStringLength - 1)];

$numbers=str_replace($num2,'',$numbers); $numStringLength = strlen($numbers); $num3=$numbers[rand(0, $numStringLength - 1)];

$numbers=str_replace($num3,'',$numbers); $numStringLength = strlen($numbers); $num4=$numbers[rand(0, $numStringLength - 1)];

$numbers=str_replace($num4,'',$numbers); $numStringLength = strlen($numbers); $num5=$numbers[rand(0, $numStringLength - 1)];

$numbers=str_replace($num5,'',$numbers); $numStringLength = strlen($numbers); $num6=$numbers[rand(0, $numStringLength - 1)];

$numbers=str_replace($num6,'',$numbers); $numStringLength = strlen($numbers); $num7=$numbers[rand(0, $numStringLength - 1)];

$numbers=str_replace($num7,'',$numbers); $numStringLength = strlen($numbers); $num8=$numbers[rand(0, $numStringLength - 1)];

$numbers=str_replace($num8,'',$numbers); $numStringLength = strlen($numbers); $num9=$numbers[rand(0, $numStringLength - 1)];

$sum=$num1+13$num2/$num3+$num4+12$num5-$num6-11+$num7*$num8/$num9-10;

if($sum == 66) echo "Math Puzzle Answer String::".$num1.$num2.$num3.$num4.$num5.$num6.$num7.$num8.$num9."||Sum::".$sum."\n"; }

I'm surprised at people here suggesting that brute force is the only solution. There are better ways of searching.

Let's make an assumption that we only ever deal with integers.

Also, 66 is pretty small given we've got to multiply by 13 at one point and multiply by 12 at another.

Let's simplify it a little too.

    a + ((13 * b) / c) + d + 12 * e - f - 11 + ((g * h) / i) - 10 == 66
    a + ((13 * b) / c) + d + (12 * e) - f + ((g * h) / i) == 87

Rearrange a little for clarity

    (a + d - f) + (12 * e) + ((13 * b) / c) + ((g * h) / i) == 87

What can we tell about this? Well, most of this is additive, apart from f.

That means we're going to be increasing our answer at each stage. If we set e to be 9, then we're definitely going to overshoot. In fact, it'd be probably impossible for it to be 7 (since that'd get us to 84 already). 6 would leave us with only 15 spare.

The greatest reduction would be 6 (1 + 2 - 9) so the rest of the equation can't be above 93 in total. The most we can add at the start is 16, so the rest of the equation can't be below 71. That's a fairly narrow band.

Is anything hugely constrained? Well, how about ((13 * b) / c)? If that's an integer then we've got to have b as a multiple of c. Therefore we really can only have c <= 4. c only has 4 values, and unless it's 1 then b only has a small number of possible values too.

Neither g or h can be 1 either, since then we'd never find a multiple of i.

Finally, since we know how changing our answer affects the result (up or down) we can mix up the numbers until it starts to work or get close. Maybe, like countdown, the answer isn't to simply give up but see how close you can get. In fact, we can make a further assumption that the problem is reasonably solvable, which suggests it's not actually that far from what is a reasonable first guess.

So. Start with something obvious, then lets try and tweak it until we start to pass all the conditions above.

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

b is not a multiple of c. Swap c for a.

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

Ok, so fine up through the first four. Let's leave those as they are until we have a better reason to change them.

e could be 5, yep.

f can be anything.

((g * h) / i) => 7 * 8 / 9 nope.

We can move around 5 and 6 into this. The 8 / 6 looks nice together, both even, the only one that works is 9 * 8 / 6. I can't actually see another solution without making a bigger difference elsewhere.

    3,2,1,4,5,7,9,8,6 => 98

Pretty close! We're 11 over. We've got a fairly unrestricted "multiply by 12" in there, so let's see if we can decrease it.

    e = 5 -> e = 4

All we're changing is d then, which is fine since it's another unrestricted one, and it'll change our results elsewhere by 1.

    3,2,1,5,4,7,8,9,6 => 87

Let's double check that

    a + ((13 * b) / c) + d + (12 * e) - f - 11 + ((g * h) / i) - 10 == 66

    3 + ((13 * 2) / 1) + 5 + (12 * 4) - 7 - 11 + ((8 * 9) / 6) - 10 == 66
        valid multiple                           valid multiple

I'm not going to pretend I hadn't already seen some answers, and I definitely think this is a hard problem, but it's certainly not something that you have to brute force. We can make clear and obvious steps towards solutions, several paths are guaranteed dead ends and there are a neat set of variables we can set to basically anything so we'll regularly actually be able to at least try our answer before tweaking it again.

Edit -

Anyone want to start a pool for when this will find its way into an interview question set?

I think this would be a great interview question, as it would be a signal to the applicant that they probably don't want the job. ;) Yes, there are ways to constrain things so you can work it out without trying thousands of possibilities, but it's still basically a slog doing it by hand, as you demonstrated.

> it's still basically a slog doing it by hand, as you demonstrated.

Well, it requires some work, yes, but there's not actually that much blind trial and error.

You can only brute force it.

Reply on news.ycombinator.com