[OlymPri20150527NTSD] Sudoku with Modular Arithmetic?

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. 

The mystery number is 3816547290.  Bingo!

Heuristics Used

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