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

[NumTh Expository] Divisibility Tests for 7 and other digits

Introduction
     Let  n = ...ABCDEFG = ... + A´106 + B´105 + C´104 + D´103 + E´102 + F´10 + G
I invent the notation  ‘n ¸ d’  to mean  “n  is divisible by  d”  (as integers).  For a definition
n ¸ d   Û   d | n   Û   n = kd  for some integer  k
Many of you may have heard of the following divisibility tests:-
  n ¸ 1   is always true
  n ¸ 2   Û   the last digit  G ¸ 2   Û   the last digit  G Î {0, 2, 4, 6, 8}
  n ¸ 3   Û   the sum of digits  ... A+B+C+D+E+F +G ¸ 3
  n ¸ 4   Û   the last digits  FG ¸ 4
  n ¸ 5   Û   the last digit  G ¸ 5   Û   the last digit  G Î {0, 5}
  n ¸ 6   Û   n ¸ 2  and  n ¸ 3  (see above)
  n ¸ 8   Û   the last digits  EFG ¸ 8
  n ¸ 9   Û   the sum of digits  ... A+B+C+D+E+F+G ¸ 9
n ¸ 10   Û   the last digit  G = 0
What about divisibility by 7?

Modulo Arithmetic
     Divisibility tests are all based on modular arithmetic (a.k.a. clock arithmetic), as part of number theory.  This arithmetic was developed initally by a very clever mathematician
called Carl Friedrich Gauss.  The key idea is that numbers can be grouped into separate classes.  For example, when considering division by  3,  we can split the integers into three equivalence classes called residue classes
     [0] = { ..., -3, 0, 3, 6,   9, 12, ... }
     [1] = { ..., -2, 1, 4, 7, 10, 13, ... }
     [2] = { ..., -1, 2, 5, 8, 11, 14, ... }
The members of each class have the same remainder when divided by  3.  For example 
     10 ¸ 3 = 3r1,  7 ¸ 3 = 2r1,  4 ¸ 3 = 1r1  (all the remainders are equal to 1).
So  10, 7, 4, 1 ... etc are all members of the class  [1]  represented by  1.  Members of the same class are called congruent.  For example  10 º 4 (mod 3),  read as “10 is congruent to  4  modulo 3” and it means  10  and  4  have the same remainder when divided by  3.
a º b (mod m)   Û   (ab) ¸ m   Û   a = b + km  for some integer  k
As you know,  “a ¸ m  gives a remainder of zero”  means  “a  is divisible by  m”.  Hence
a º 0 (mod m)   Û   a ¸ m
Congruency (for a given modulo m) is a type of equivalence relation.  We have these laws
Reflexivity:   For every integer aa º a
Symmetry:    If  a º b,  then  b º a.
Transitivity: If  a º b  and  b º c,  then  a º c.
These properties are similar to ‘=’.  We also have some very neat arithmetical laws.
Suppose  a º b (mod m)  and  c º d (mod m).  Then
     a + c º b + d  (mod m)
     ac º bd  (mod m)
         ac º bd      (mod m)

For a given number  n = ...ABCDEFG,  we can write  n = 1000x + y   where  x = ...ABCDy = EFG.  With the above laws, modular arithmetic helps simplify calculations and provide powerful insights.  For example, in modulo 8,
         10 º 2,  100 º 102 º 22 º 4,  1000 º 10 ´ 102  º 2 ´ 4 º 0.  Hence
         n = 1000x + y  º  0×x + y  º  y.
This explains the divisibility test by  8:  To see if a number is divisible by  8, we just need to look at the last  3  digits  y = EFG.

Test for divisibility by 7
     Using modulo 7,  10 º 3,  100 º 32 º 2,  1000 º 3 ´ 2 º 6 º -1.
     n = 1000x + y º  -1×x + y º  yx.  Thus
     n ¸ 7   Û   n º yx º 0   Û   x º y   Û    x y ¸ 7.  We have the rule
n ¸ 7   Û   ...ABCD º EFG (mod 7)
This means that a number is divisible  7  if (and only if) after breaking off the last three digits, both resulting pieces have the same remainder when divided by  7.

Example 1
       For 12 516:  12 º 5  and  516 º 5 (mod 7).  So  12 516 ¸ 7.

Example 2
       For 654 321:  654 º 3  and  321 º 6 (mod 7).  So  654 321 not ¸ 7.

Example 3
       For 1 494 787:  787 º 3 º 1494 (mod 7).  So  1 494 787 ¸ 7.
       Alternatively, 1 494 – 787 = 707 ¸ 7.  So  1 494 787 ¸ 7.


Works like magic, doesn’t it?

Wednesday, May 27, 2015

[OlymPri20150527AGSQ] Three Angles and Three Squares

Question

Introduction
     This question, from a Facebook forum, is essentially the same problem as the one in a previous article.  However, here we are not allowed to use any advanced mathematics like arctangent (inverse tangent).  It must be a solution that a primary school pupil can come up with, or at least understand.

Solution 1
     Refer to the article “Angles with nice tans add up nicely”.  Ðb + Ðc  = Ða = 45°.  So  Ða + Ðb + Ðc  = 2 Ða = 90°.  But using this method is “cheating”.

Solution 2a
     I happened to be watching this YouTube video that solves this problem.  What a coincidence!  The presenter is Professor Zvezdelina Stankova from the University of California, Berkeley.  I liked the way she used the “Act it out” heuristic by using a pair of scissors to cut out the angles on paper, and then putting them together to see if  they actually add up to  90°.  The trouble with this approach is: How do you know that they add up exactly to 90°?  So Stankova proceeded to give an elementary but rigorous proof.  Her proof is elegant, but I think the demonstration of the fact that  ÐEHD  is a right angle can be tightened using the idea of rotation.

Solution 2b
     I am going to follow Stankova’s naming of the vertices, except that our problem is the mirror image of the one that is shown in the video.  Ðc  is easily seen to be  45°.  This is because  DBAE  is an isosceles triangle with  ÐBAE = 90°Ðc = (180° – 90°) ¸ 2 = 45°.  We extend the grid to a  2  by  3  grid, and construct  HD  and  HE

Obviously  HD  = HE = CE,  because they are all hypothenuses (that is the correct plural form, not “hypotheni”.  I checked)  of right-angled triangles with some length of  1  unit and another length of  2  units including the right angle in between.  Another way to think about it is that they are all diagonals of a  2  by  1  rectangle of some orientation.

Notice that  ÐIDH = ÐFHE = ÐECA = Ðb,  for the same reason.  Observe also that the rectangle  HCDI  is rectangle  HFEK  rotated by  90°  clockwise.  Every point and every line of the original rectangle is rotated by the same amount.  In particular,  HE  is rotated by  90°  to get  HD.  Hence  ÐEHD = 90°,  and since  DHDE  is an isosceles triangle,  ÐHDE = 45° = Ðc.   Ða + Ðb + Ðc = ÐEDA + ÐIDH + ÐHDE = ÐJDC = 90°©

Solution 3
     One of the viewers, Ian Agol, contributed a solution, which I think is the most elegant solution.  It is a proof without words.  If you just stare at the picture and think, you should “get it” without explanation.  The diagram below is an adaptation of his solution.

If you want an explanation:  Ðc = ÐJDK  = 45°, obviously.  The red grid is constructed at a  45°  angle to the black grid, but has a bigger length.  Nevertheless,  ÐEDQ = ÐECA = Ðb,  because  DQDE  is just an enlarged version of  DACE.  [They are similar triangles.  The enlargment factor is Ö2,  but we do not need this.]  By looking at  ÐJDC,  you will see that  Ða + Ðb + Ðc  = 90°.

Remarks
     Unlike the usual examination-based school “mathematical” practices, real mathematics is not just about getting the answer.  It is about creativity, seeking understanding and seeking elegance.  We prefer short and sweet solutions to long and complicated solutions.  Sometimes when we finish solving a problem, another solution or a few other solutions pop-up.  Having different approaches to a mathematical problem allows us to understand the problem and the inter-relationships better.


H01. Act it out
H02. Use a diagram / model
H04. Look for pattern(s)
H05. Work backwards
H09. Restate the problem in another way
H10. Simplify the problem
H11. Solve part of the problem

Suitable Levels
Primary School Mathematics Olympiad
* other syllabuses that involve angles