Question
Introduction
This is a pretty nasty-looking
challenge. It is like Sudoku, but only
worse. You probably cannot avoid some
degree of trial-and-error (or [H07] guess and check). There is a solution posted somewhere, but it
is very long and chases many dead-ends before arriving at the solution.
So how do we avoid making so many wild
guesses? We do so by making good use of number theory, which includes modular arithmetic. In what follows, I
am going to use the theory and notations as in my article (“Divisibility Tests for 7 and other digits”).
Please read the article to remind yourself of the various divisibility
tests.
Solution
It
is easy to see that j = 0.
Since
abcde ¸ 5, e Î {0, 5}. But
0 is already taken, so e =
5.
Since
divisibility is transitive (x ¸ y and y ¸ z Þ x ¸ z), anything divisible by 4,
6 and 8 is
also divisible by 2. So b, d, f,
h
are all the even digits 2, 4, 6,
8 in some order, and a, c, g,
i
are the odd digits 1, 3, 7,
9 in some order. From the divisibility tests for 3,
6 and 9,
a+b+c º 0 (mod 3)
a+b+c+d+e+f º 0 (mod 6) Þ a+b+c+d+e+f
º 0 (mod 3)
a+b+c+d+e+f+g+h+i º 0 (mod 9)
Þ a+b+c+d+e+f+g+h+i º 0 (mod 3)
we get
a+b+c º d+e+f
º g+h+i
º 0 (mod 3)
To
narrow down the search space, we always test the group of digits that contain
the most clues and the least unknowns (if possible). Currently,
this seems to be the middle group d5f.
Using
modulo 3, d+5+f º 0 Þ d+f
º 1 Þ d+f = 7, 10, 13 (because
2+4 < d+f < 6+8)
Since
d and f
are even digits, we can cross out
7 and 13. So
{d, f} = {6, 4}.
abcd ¸ 4 Þ cd ¸ 4 Þ 10c + d
º 2c + d º 0 (mod
4)
If d = 4,
then 2c º 0 (mod
4) Þ c º 0 (mod
2). Not possible, as c is odd.
Now we know
d = 6 and f = 4.
The number is abc654ghi0, and {b,
h} = {2, 8}.
Can h = 8?
If so, we would have 4g8 º 4´100+g´10+8 º 2g º 0
(mod 8). g º 0 (mod 4)
g ¸ 4 ¸ 2. But
this is not possible, since g
is an odd number. Hence know h = 2
and b = 8. The number is a8c654g2i0.
Now
4g2 ¸ 8 Þ 4´100+g´10+2 º 2g+2 º 0 (mod 8)
Þ g+1 º 0 (mod 4)
Þ g º -1 (mod 4)
Þ g Î {3, 7}.
If g = 3, then working in mod 7, we have a8c6 º 543,
and then
Þ a´1000+8´100+c´10+6 º 5´100+4´10+3
Þ -a+8´2+c´3+6 º 5´2+4´3+3
Þ 3c – a + 1 º 4
Þ a – 3(c – 1) º 0 (mod 7)
Note that a
is an odd digit and c is odd,
c – 1 is even,
3(c – 1) is even and so a –
3(c – 1) is odd.
a – 3(c – 1) ¹ 0 because 0 is
even. Since 1 < a < 9, a – 3(c – 1) = 7. We need a =
7 and
c = 1. This would mean i =
9. But
g+h+i º 3+2+9 º 2 (mod 3). It
is supposed to be 0 (mod 3). So g ¹ 3 i.e. g =
7. The number is a8c65472i0.
Going back to mod 7, a8c6 º 547
3c – a + 1 º 1
a
º 3c
(a,
c) = (3, 1) or (9, 3). But if
(a, c) = (9, 3), i = 1.
g+h+i º 7+2+1 º 1 (mod 3), which is incorrect. So we must have a =
3 and c = 1. The remaining digit
is i
= 9.
H03. Make a
systematic list
H04. Look for pattern(s)
H05. Work
backwards
H07. Use guess
and check
H08. Make
suppositions
H09. Restate
the problem in another way
H10. Simplify
the problem
H11. Solve part
of the problem
H13* Use
Equation / write a Mathematical Sentence
Hxx* At each step,
try to attack the part that has most clues and the least unknowns.
Suitable Levels
* Primary School Mathematics
* anyone game for a challenge requiring
modular arithmetic