Thursday, May 28, 2015

[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 theorywhich 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
     Þ                          3ca + 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
                               3ca + 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!


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

No comments:

Post a Comment