brainbuster no. 25 - Remove Digits

This competition closed on Sunday 30 March 2008.

the brainbuster

"Using each of the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9 only once, form a nine digit number A that can satisfy the following criteria:

- A is exactly divisible by 9.

- Removing the rightmost digit from A forms an eight digit number B that is exactly divisible by 8.

- Removing the rightmost digit from B forms a seven digit number C that is exactly divisible by 7.

- Removing the rightmost digit from C forms a six digit number D that is exactly divisible by 6.

- Removing the rightmost digit from D forms a five digit number E that is exactly divisible by 5.

- Removing the rightmost digit from E forms a four digit number F that is exactly divisible by 4.

- Removing the rightmost digit from F forms a three digit number G that is exactly divisible by 3.

- Removing the rightmost digit from G forms a two digit number H that is exactly divisible by 2.

What is A?

Show how you produced B, C, D, E, F, G & H."

the solution

Here is the answer as provided by our winner (another entrant pointed out some typos in the original text - these have now been corrected):

A=381654729

Solution:

Let A=ihgfedcba with abcdefghi some permutation of 123456789.

The conditions on H,F,D and B imply that h,f,d and b are even.

The condition on G implies that 3|i+h+g (by considering the condition
ihg=0 (mod3)).

The condition on F implies that 4|2g+f since 100 = 0 (mod 4), 10 = 2
(mod 4). If g=1,3,7 or 9, then 2g=2 (mod 4). Hence in order for 4|2g+f we must have f=2 or 6 (mod 4).

Since E is divisable by 5 we have e=5.

The divisibility criterion for D require that 4(i+h+g+f+e)+d = 0 (mod
6). Since 3 divides i+h+e and e=5 we see that 6 divides 4f+20+d and
hence 4f+d+2 = 0 (mod 6). If f=2 we see that d=8 and if f=6 then it
follows that d=4. Note that in both these cases d+f=10.

The condition on C requires that 7 divides i+5h+4g+6f+2e+3d+c. We know
that e=5 and that d+f=10 so this reduces to 7|i+5h+4g+3f+c+5.

The condition on B requires that 8 divides 4d+2c+b. We know that d=4 or
8, so it follows from the above relation that 8 divides 2c+b. Trying
out all possibilities for c in {1,3,7,9} we see that b=2 or 6, from
which we deduce that h=4 or 8.

We now plug in the possible values for h in to the equation obtained by
considering C: 7|i+5h+4g+3f+c+5. If h=4 then we must have d=8 and f=2. Otherwise we have h=8, d=4 and hence f=6.

In the first of these cases i+5h+4g+3f+c+5=i+4g+c+4(mod 7) and we
therefore require that 7 divides i+4g+c+4. By checking for i,g,c in
{1,3,7,9} we see that the only possibilities are (i,g,c)=(9,7,1) and
(1,7,9). In the first of these possibilites we have i+g+h=20, which is
not divisable by 3 (contradicting the condition for H). Using the
second of these triples we construct the nine didgit number:
147258963. However, this does not satisfy the equation for C: that 7
divides i+5h+4g+6f+2e+3d+c (the remainder is 6). Interestingly, this
number does satisfy all the conguences apart from this one.

We conclude that h=8, d=4 and f=6 and hence b=2. The congruence
condition for C reduces to "7 divides i+4g+c". The solutions to this
equation are (i,g,c)=(7,1,3),(3,1,7),(7,3,9) and (9,3,7). The
condition "i+h+g is divisable by 3" only holds for the triple (3,1,7)
from which we obtain A=381654729.

It is easily shown that this satisfies all the required congruence relations.

and the lucky winner is...

Congratulations to Lawrence Taylor, a mathematician (appropriately enough) currently based in Germany, who wins £200 of Firebox vouchers.

Many thanks to all entrants - do try brainbuster no. 26!

thinkingpeoplefirst