Monday, May 16, 2016

A quick note on the MathCounts final question

http://q13fox.com/2016/05/09/seattle-13-year-old-wins-national-math-bee/

"Competition officials said in a news release the 13-year-old won the final round by answering the question, “What is the remainder when 999,999,999 is divided by 32?”
Wan gave the correct answer of 31 in just under seven seconds."


I heard about the MathCounts results a week ago and my first reaction to this  question was "Huh doesn't seem like a very deep question, its so computation focused."  My second thought was I wonder how long just doing the long division would really take and then I immediately followed that up with  I could type this into python (or the google address bar nowadays) and find the answer very quickly.




However, I thought about it again while trying to fall asleep last night and there is actually a lovely (and accessible) piece of number theory contained within it.  This time, I started by musing  "How did he do it so quickly."  The easiest way I thought of was to build up a divisibility rule for 32.  Since 32 is 2^5 multiplying it by 5^5 produces a nice power of 10. But I was in bed so I actually went 32, 160, 800, 4000, 20000, 100000.  This means, you can ignore all the digits past the 5th one i.e. this is the same as 99999 mod 32.  I then thought let's subtract the largest multiple of 20000 to get 19999 left over. Then lets take the largest multiple of 4000 to get 3999 leftover. At which point I noticed the pattern (mind you I didn't have any paper).

99999  remainder for 100000
19999  remainder for 20000
3999 remainder for 4000
799 remainder for 800
159 remainder for 160

What's occuring here is that 999,999,999 is 1 less than 1,000,000,000 which is divisible by  32 based on my first observation since its a multiple of 100,000.  So clearly 999,999,999 mod 32 is -1 or adding 32 to it the remainder must be 31. This basic fact was showing up in all the partial sums as well.  In fact, with any pure power of 2 a sufficiently large number made only of 9's will have this property! 999,999,999 mod 64 is 63, 999,999,999 mod 16 is 15 etc.   So I've completely changed my mind, I think this will make a fun white board group exercise where the kids can look for patterns to solve the problem an easier way. (Maybe I'll even show a video snippet of the Math Counts finale)  Oh and congratulations to Wan who still totally creamed me.

4 comments:

  1. Similarly: Since 8 divides evenly into 200, it also divides evenly into 1000. Then 32 divides evenly into 4000, so also 100000, etc.

    Wen probably had the answer faster than 7 seconds, but was checking.

    Related question: how many zeros at the end of 30!?

    ReplyDelete
  2. I like that idea. Its a good followup with the focus on terms containing fives in the sum.

    Btw: I still find it amazing that I can do things like this trivially nowadays vs even 10-15 years ago:

    >> import math
    >>> math.factorial(30)
    265252859812191058636308480000000L
    >>>

    ReplyDelete
  3. Is there a video that shows the last question? This is the best I could find (final w/o final question).

    My plan is to pose the question to my kids and see how they work through it. I'd like to show the video, so we can see how long it took Wan. Then, go back and see if we can figure out other strategies that might be very fast.

    Maybe a dangerous game, since I don't want to create the impression that speed is important. What I'm going for is an interest in looking for a sharper insight and desire to see the critical element of the problem.

    In the Beast Academy books, there is a character (Max) who solves problems very quickly in math competitions. We had a lot of fun talking through a relay set-up where a team has a chain of questions with the answer from one used as a key piece of data in the subsequent question. Max figures out the answer to his question without needing the input data. I'd love to find more relay examples and explore more cases where it is possible to skip ahead like that.

    ReplyDelete
  4. There's the ESPN version: http://espn.go.com/watchespn/player/_/id/2810794/ which seemed pretty good. Its around 1:21 into the stream.

    I was surprised how quickly my kids reached the insight here as well. I'd emphasize how did he save himself doing all the work of the long division.

    ReplyDelete