Thursday, 28 July 2005

Mindbender 2: solution

Backdated post, to avoid spoiler to puzzle.

The above puzzle, from the Western Morning News's daily Mindbender series, comes down to this: find a 8-digit number such that stripping the outer two digits off leaves you with that number divided by 83.


If you call the outer digits a and c, and the middle number b, then this can be expressed as the equation:

(10^7)a + 10b + c = 83b ... which reduces to:

(10^7)a - 73b + c = 0

As is very often the case with these Mindbender puzzles, this is a Diophantine equation: an integer relation with multiple variables and constraints. There are formal ways to tackle these, as well as "quick and dirty" number-crunching by computer. But as I mentioned earlier - see Mindbender 1: solution - iterative solutions often give much faster results.

If an equation can be expressed as a relation x = f(g(x)) (where f(x) is an ascending function and g(x) a descending function, or vice versa) then repeatedly applying x -> f(g(x)) can often converge on a solution. This looked a promising route here.

Define g(x) = 83*x
and f(x) = DIGSTRIP(x) ... where DIGSTRIP removes the outer two digits from an 8-digit number.
gives x -> DIGSTRIP(83*x)

For example, start with x = 666666.
x -> DIGSTRIP(83*666666) = DIGSTRIP(55333278) = 533327
DIGSTRIP(83*533327) = DIGSTRIP(44266141) = 426614
DIGSTRIP(83*426614) = DIGSTRIP(35408962) = 540896
DIGSTRIP(83*540896) = DIGSTRIP(44894368) = 489436
and so on ...

This rapidly turned out to be a dead end. Even though it has one of the required properties - it generally stays in range - whatever the seed, it simply refused to converge. I think the problem is that DIGSTRIP is not a well-behaved function; while it reduces an 8-digit number by two orders of magnitude, the result can actually be anywhere in the range of 6-digit numbers. So it isn't actually a function useful for homing in on a result.

So a different approach was needed. Returning to the equation ...

(10^7)a - 73b + c = 0

... another possibility is to try to reduce it to the smallest search space. In this case, the 6-digit number b is not what you want to search through, so I tried expressing b in terms of a and c (since a is in the range 1-9, and c in the range 0-9):

b = ((10^7)a + c)/73 ... or in short ... (10^7)a + c ≡ 0 modulo 73

This has brought the problem to very simple form. All that's needed is to search through 9 cases -  (10^7)a for a=1...9 - and see if any have a multiple of 73 that's less than 9 greater. This is plain calculator territory.

10000000/73 = 136986.3014... 
136986*73 = 9999978, next multiple is 10000051 ... no

20000000/73 = 273972.6027...
273972*73 = 19999956, next multiple is 20000029 ... no

30000000/73 = 410958.9041...
410958*73 = 29999934, next multiple is 30000007 ... yes!

So a=3, c=7, and b = 30000007/73 = 410959

And confirming: 34109597 = 410959*83 ...the solution sought.

- Ray

No comments:

Post a Comment