How Can I Succeed in the Math Olympiad?

[Thenewguy2]

How can I go far in the national mathematical olympiad? Do you need to be born with an insane IQ, or born a genius or something like that? Any tips about how I can increase my problem solving skills if it's even possible? Examples of problems you will have to solve in the second round of the national olympiad are like this one: Find the last three digits in the product 1 * 3 * 5 * 7 * ... * 2009 * 2011 I mean how can I ever be able to solve that problem? I bet even people with masters and Ph.D's in mathematics struggles on these tasks and lots of high school kids can solve it... Will I ever be able to make it far in the Olympiad? I think I mainly need to practice my problem solving skills, but not sure if it's possible.

 

[mfb]

I mean how can I ever be able to solve that problem?

The result is a multiple of 125. 1000 is a multiple of 125, so there are just 8 possible results for the last 3 digits. 4 of them are even, this just leaves "125", "375", "625" and "875". If you calculate the first few products mod 8, you can see a pattern, and the result is not hard to find out.

Intelligence certainly helps to find pattern like that, but I think practice is much more important.

 

[verty]

How can I go far in the national mathematical olympiad? Do you need to be born with an insane IQ, or born a genius or something like that? Any tips about how I can increase my problem solving skills if it's even possible? Examples of problems you will have to solve in the second round of the national olympiad are like this one: Find the last three digits in the product 1 * 3 * 5 * 7 * ... * 2009 * 2011 I mean how can I ever be able to solve that problem? I bet even people with masters and Ph.D's in mathematics struggles on these tasks and lots of high school kids can solve it... Will I ever be able to make it far in the Olympiad? I think I mainly need to practice my problem solving skills, but not sure if it's possible.

Don't feel bad, stuff like this is extremely difficult. Luckily you just have to beat your competitors, not the paper itself.

I failed to solve it myself, I was looking for a recurrence relation but that fails miserably.

 

[verty]

No, sorry, I had posted my workings here but they definitely fail.

 

[Bill Simpson]

How can I go far in the national mathematical olympiad?

1. Buy or borrow "Problem Solving Strategies" by Engel and study every word in that. That is a training manual for the olympiad.

2. Buy or borrow "Talent is Overrated" by Colvin and study enough of that to understand his point. That says paying for an excellent coach who is going to understand what you are weak on and will teach you a particular style of practice that will dramatically increase your skill IF you put in enormous amounts of effort. (I'm not sure where to find tutors for math which are skilled at this method. If anyone knows of a source I'd like to hear about it.)

3. Go talk to professors who have taken lots of students to high scores in the olympiad. Decades ago I listened to a talk by someone who had done this and who had been a grader for the Putnam. He explained that for the Putnam most people either get zero points for a problem, one point for a problem or almost five points for a problem and you needed to understand what was needed to make the difference between a one point answer and a five point answer. Then he went on to explain some of what you needed to do. I expect the olympiad may have similar kinds of things, but only an expert with lots of experience will be able to tell you how to get from a poor score to an exceptional score.

Now I'm out of my depth here, but I'll take a chance that I won't make a mess of this.

Since you only want to know the last 3 digits then the fourth digit makes no difference. So the product from 1 to 999 is the same as the product from 1001 to 1999, and then you have to fudge in the 1*3*5*7*9*11 from the 2xxx. So instead of having 1005 numbers to find a product you only have 500, square that and include the fudge. Can you use this same idea to dramatically reduce the size of the calculation even further? (Go forth and factor. That is a hint) And I hope I haven't made a mess of this.

Edit: It does work, but under a clock I'd be too slow and error prone to get all the details correct. I'd need to do all the things I suggested and probably more to have a chance of doing well.

 

[mfb]

@Bill Simpson: With the method I suggested the problem can be solved within a minute (or at least within 5 minutes, including double-checking the answer).

 

[Thenewguy2]

The result is a multiple of 125. 1000 is a multiple of 125, so there are just 8 possible results for the last 3 digits. 4 of them are even, this just leaves "125", "375", "625" and "875". If you calculate the first few products mod 8, you can see a pattern, and the result is not hard to find out.

Intelligence certainly helps to find pattern like that, but I think practice is much more important.

The correct answer was 875. I just don't know how one is able to solve such problems :()

Another example can be: Let n be the number that is produced by concatenating the numbers 1, 2, ..., 4022, that is, n=123456781011...40214022.

a.) Show that n is divisable by 3.

We consider the sum of the digits of a positive integer. For example, the sum of the digits of 2536 is 16, since 2+5+3+6=16.

b.) Let a_1 = n^2011, and let a_i be the sum of the digits of a_(i-1) for i > 1. Find a_4

a_1 = a and a small 1 next to it if you know what I mean, don't know how to type it in here and a_(i-1) means that both i and -1 are small and they are next to the a.

Just had to throw this one out here for you math interested guys :D (national olympiad level). Just don't understand how people my age can solve them when my teachers with masters can't :(

 

[mfb]

The correct answer was 875. I just don't know how one is able to solve such problems :()

See my posts for a possible method. The interesting task is to find the right method.

a)

Spoiler

A number is divisible by 3 if and only if the sum of its digits is divisible by 3 (I guess you can use this without proof, but the proof is not so complicated). In addition, the remainders are the same for the original number and the digit sum. Let's group digits: n=(12)(3)(45)(6)(78)(9)(1011)(12)...(4020)(40214022). Every group is (1) a number divisible by 3 or (2) two numbers, one with remainder 1 and one with remainder 2. As 1+2=3, both groups have digits sums divisible by 3. As a result, the total digit sum is divisible by 3.

Are you sure (b) does not depend on n?

You can write a₁ as [noparse]a₁[/noparse] or ##a_1## with LaTeX.Edit: Oh, n in part b is supposed to be the n of part a. How obvious... I missed that.

 

[verty]

Let n be the number that is produced by concatenating the numbers 1, 2, ..., 4022, that is, n=123456781011...40214022.

a.) Show that n is divisable by 3.

To see if 3 divides a number, sum the digits because the sum will have the same remainder modulo 3 as the original number. Is 18 a multiple of 3? 18 -> 9, yes. Is 2832 a multiple of 3? 2832 -> 15 -> 6, yes.

Does this help to answer part A?

 

[Thenewguy2]

a₁ (Test)

Ok it worked

 

[Thenewguy2]

This is the answer on a): (Btw I didn't know how to translate one thing to english.. I just translated it to "digit sum" the digit sum of 123 is 1+2+3 = 6.

The difference between a positive integer and its digit sum is always divisible
with 9. We illustrate the proof idea for a three digit number 100a + 10b + c, where a, b
and c are digits. The sum is a + b + c, and the difference thus 99a + 9b =
9 * (11a + b). In particular, this difference is divisible by 3, and the familiar
rule that says that a number is divisible by 3 if and only if the digits are
it, and the corresponding rule for divisibility by 9, following light of this.
Let m = (1 +2 +3) + (4 +5 +6) + · · · + (4018 4019 4020) + (4021 4022),
where we have grouped the numbers three and three consecutive numbers with two digits to spare
eventually. The sum of three consecutive integers is always divisible by 3, and
is the sum of two consecutive integers is not divisible by 3, so
amount of each parenthesis is divisible by 3 - thus m
Let t be cross sum of n Then m - t divisible by 3, because m - t =
(1 + 2 + · · · + 4021 + 4022) - (1 + 2 + · · · + 4 + 0 + 2 + 1 + 4 + 0 + 2 + 2) =
(1-1) + (2-2) + · · · + (4021-4-0-2-1) + (4022-4-0-2-2) - each joint
in parentheses is the difference between a number and its digit sum, thus divisible
with 3 Since m and m - t is divisible by 3, is also not there - and thus also n
Alternatively, we can take account of cross sum more directly. The figures
0, 1,. . . , 999 each digit occurs 300 times (if we fill in with 0 in
the start of each number so all the three digit) so that the sum of all digits of
All these numbers are divisible by 3 - let's say that the sum is 3a. The sum of all
digits 0, 1,. . . , 3999 is thus 4 · 3a + 1000 · (1 + 2 + 3) = 3 · (4a + 2000)
thus also divisible by 3 The sum of all digits in 4000, 4001,. . . , 4022 is
23 · 4 + (10 · 1 + 3 · 2) + (2 · (1 + 2 + ... 9) + 1 + 2) = 102 + 3 · 2 + 2 · 45 + 3,
which is also divisible by 3 The sum of n - sum of all digits 1,
2,. . . , 4022 - is therefore divisible by 3, hence n

My english is not that good so I used google translate to help me, if something doesn't make sense please tell me. (I don't really understand it not even in my main language, this is just the solution they put up on the olympiad site..

Just double chcked b) and it's correctly typed in the question and everything else. I am not really this much of a genius in maths, I don't understand how a kid in my class can solve this.. :(

SPOILER: ANSWER ON B)

The digit sum t of a number with k er less digits fulfill 0 < t <= 9k < 10k. The number n has less than 4 * 4022 < 10^5 digits, so n < 10^10^5, and a₁ = n^2011 < (10^10^5)^10^4 = 10^10^9, and a₁ has therefore less digits than 10^9 and a digit sum that's less than 10^10. So a₂ <10^10, has less than 10 digits and a digit sum that's less or equal to 81. So a₃ <= 81 has the digit sum less than 18. (The only 2 digits number with such a huge digit sum is 99). So a₄ <18. But a number is divisable by 9 if and only if the digit sum is divisable by 9, and a₁ =n^2011 is divisiable with 9 since n is divisible with 3 - therefore is also a₂, a₃ and a₄ divisible with 9. So 0 < a₄ < 18 and a₄ is divisible by 9, so a₄ =9.

Note: If you see x <= 3 this just means that x is larger or equal to 3 (dunno how to type it properly in here)

Dunno is this makes any sense, makes zero sense to me (these tasks...)

 

[Boorglar]

A lot of math olympiad problems are based on some "trick" that, once found, makes solving the problem fairly straightforward. Kinda like a puzzle.

I think those problems also require some amount of practice. My suggestion is to take a bunch of olympiad questions and attempt to solve them. If you get really stuck on a problem, only then, look at the solution or the first few steps. It is not shameful to read the solutions (if you've put some effort before), because they may give you valuable insights and you will be able to solve similar problems after that. Compare your ideas/work with the solution. You might realize you weren't so far from the solution, after all. I admit I've got trouble with most olympiad level questions, but I have performed reasonably well in provincial/national competitions (no top rankings, though ). But practicing and reading the solutions gives you a general idea of what kind of solutions are expected.

It also doesn't hurt to have a bag of theorems and identities. For example, a lot of problems are based on the Pidgeonhole Principle, or on modular arithmetic. Make sure you understand these. Again, if the solutions refer to specific theorems, look them up. They may provide the "big picture" and you'll understand the problem much better.