Thursday, 28 July 2005

Mindbender 4: solution

Backdated post to avoid spoiler to Mindbender 4.

This is an interesting one: find a number of indeterminate length (the puzzle doesn't say what kind of phone number it is) that's one less than the 200 x its last four digits.

?????number = 200*(number) - 1

You could fiddle around for ages trying to find analytical solutions for various assumptions of the length of the unknown segment (it'll come down to a Diophantine equation with two variables). You could equally try a deductive method to work out what 4 digits will produce themselves in the rightmost place when 200*x - 1 is applied: for starters, any number of the form 200*x - 1 is going to end in 99.

But this one looked far more readily amenable to an iterative method, finding a stable solution to the iteration x -> f(g(x)) ... where f(x) is a decreasing function and g(x) is an increasing one. The beauty of it is that the functions don't have to be continuous (e.g. polynomials); they can be integer functions, and even bit operations such as removing the leading digits.

In this case, g(x) = 200*x - 1 and f(x) = "take last four digits"

That is, start with any 4-digit number x, find 200*x - 1, select the last four digits to get new x, and repeat.

This is the first one I tried:

1234 ... 1234*200 - 1 = 246799
6799 ... 6799*200 - 1 = 1359799
9799 ... 9799*200 - 1 = 1959799
9799 ... 9799*200 - 1 = 1959799 ... solution!

It doesn't seem to matter what seed you choose to start the iteration; the iteration always rapidly converges to 1959799.

- Ray

No comments:

Post a Comment