A puzzle has been floating round the internet, apparently impossible and assigned to 8-year olds in Vietnam. How impossible is it? Here’s a quick look.

The format of the puzzle is the following:

Place the numbers 1-9 without repetition in the ‘snake’ below such that they form the correct answer.

Photograph: VN Express

where the colon symbol represents division. If, in order, the numbers are represented by the letters , the problem we are trying to solve is:

While a little intimidating perhaps in this form, by noticing that all of the variables and the ‘answer’ are integers, one can reduce the number of possibilities drastically. Even that, though, requires some thought which I’m far too lazy to apply. No, instead I’ll just brute-force the whole thing – try every possible combination of the numbers 1-9 until I get the right answer.

This takes less than a second on my laptop, and it turns out there are 128 different answers for the ‘solution’ 66. The distributions of the numbers for this solution look like the following:

You’ll notice that we can never have or being 5 or 7 in the solution, as they are the denominators of fractions. As 5 and 7 are prime numbers with no multiples under 10, dividing by one of them will result in a non-integer. Also, as is multiplied by 12, it can’t be too high if we want to reach a solution.

What if you plugged in numbers randomly, hoping to get the right answer? Your chances would be 128/9! = 0.035%, which aren’t great. Some mathematical thinking required then.

**Other solutions**

What if the teacher had picked a different target – are there any other solutions which are easier to reach? Below I plot the number of solutions for different targets, other than 66.

We can see that the teacher was perhaps being a tad mean – the ‘easiest problem is for a target of 97, where there are 320 solutions – twice as easy! The smallest target you can reach is -1, with 12 solutions, and the largest is 219, with 4 solutions. Can anybody get these?

**General solutions**

What about non-integer targets? Below I just plot the histogram of the values of the equation above, for all possible permutations

It’s quite interesting that the shape is different than just the integer solutions. In fact, solutions resulting in an integer target represent only 27,336 of the possibilities, just 7.5% of all possible solutions. Where before we had a ‘triangular’ distribution which was fairly symmetric, here we have a much broader plateau, falling off asymmetrically on either side. Looking at the logarithm of the above, we see that the slow fall off at larger solutions is approximately exponential:

The red line is . There is presumably a way to derive this fact, based on the probability of picking solutions which result in larger numbers. I’m about to go on holiday however, so I’ll leave that challenge for someone else.

I disagree : there are 136 solutions, not 128. If you give me your 128 results, I can tell you which ones are missing. Do you have this one ? ‘1 8 3 7 4 5 2 6 9’

LikeLike

See all 136 solutions at http://pastebin.com/1gJEMugJ

LikeLike

I believe you may have a rounding error… took me a while, because I was using excel+notepad++ to check my answers against your answers… but the first one you have that I don’t have is “1, 8, 3, 7, 4, 5, 2, 6, 9, 66”

If I set a break-point on that particular solution I end up with 65.999999999999986

The other solutions you have that I don’t are

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

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

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

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

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

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

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

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

LikeLike

Interestingly enough I do get 136 solutions if I use float instead of double… I suspect there may be other cases for which there may also be a rounding error…

LikeLike

OK, I’ve gone through the 136 solutions which one obtains using single precision. I’ve taken these 136 solutions and calculated them exactly using the symbolic manipulation functions in Matlab… and I get exactly 66 for all of them. In particular, for the solution 1, 8, 3, 7, 4, 5, 2, 6, 9, doing this calculation by hand I get

30 + 104/3 + 12/9 = 66

which is correct.

Similarly, for 1, 8, 3, 7, 4, 5, 6, 2, 9 the 12/9 factor is unchanged, and the total is 66.

For 8, 6, 9, 2, 5, 1, 7, 4, 3, you get 48 + 26/3 + 28/3 = 66

I think with double precision small rounding errors are able to accumulate. With single precision each rounding error is too small to make a difference, and you end up with the correct answers.

Thanks both for having a look at this!

LikeLike

To follow up, for fun I tried to find the closest near-miss I could. The best I could do was 1, 7, 9, 4, 6, 2, 5, 3, 8, which results in 4751/72 = 65.98. This indicates that there aren’t any ‘accidental’ answers very very close to 66.

LikeLike