Maths Olympiad Tips and Tricks

[youngyew]

Another thread I am reviving (I spent many hours typing out those stuff)

I promised that I would put up some of the basic concepts useful for Maths olympiad, so I will try to begin here... Sorry I have forgotten most of the malay translation for the terms, but I will try my best to explain them, together with relevant links.

Let's begin with number theory, which is my favourite field.

Number theory is a field of pure maths which study the relationships and properties of numbers (particularly integers). One of the examples of number theory would be like this: If a and b are two positive integers, prove that the product (multiplication) of a and b is the same as the product of their greatest common denominator (FSTB) and their least common multiple (GSTK).

Firstly I would like to introduce some terminology..

Types of Numbers

• Integer / round number (commonly represented by the symbol Z): -10000, -3, , 1, 2, 5, 7, 9...
• Natural number / nombor asli (N): Positive integers (1, 2, 3, 4, ... )
• Whole number / nonnegative integer / number bukan-negatif (W): Positive integers and zero. (0, 1, 2, 3, ...)
• Rational number (Q): Numbers which can be expressed by a / b, where a and b are integers.
• Real numbers (R): Any number that can be found along the number line (pi, square root of 2, 3.5, 7/8, 10000 etc)
• Irrational Numbers: Real numbers which are not rational.
• Complex numbers (C): Numbers which is in the form of a + bi, where i is defined as the square root of -1, while a and b are real numbers.

• Divisor / factor / faktor / pembahagi: If x is a divisor of y, then y can be divided by x without a remainder / decimal places. E.g. 4 is a divisor / factor of 20, but not a divisor of 95.
• Prime number / prime / nombor perdana: Natural numbers that can only be divided by 1 and itself. (2, 3, 5, 7, 11, 13, 17 etc) Note that 1 is not considered a prime number.
• Coprime / relatively prime / saling perdana (not sure about the malay term): a and b are relatively prime if they don't share the same divisor except 1, or in other words, their GCD is 1. For example, 14 and 27 are relatively prime. Note that when two numbers are coprime, they don't necessarily are prime numbers themselves (e.g. 14 and 27); but two prime numbers must be coprime.

Phrases / Notations:

a divides b / a membahagi b: a is a factor of b. E.g. 5 divides 45.

Originally Posted by mad

Tunjukkan bahawa 5^4 + 4 x 3 ^4n, (in nombor asli), bukan nombor perdana.



May i know what are the normal steps or ways to prove a certain expression is not a prime number?

If you can factorise it algebraically, and show that the factors you have got cannot be 1, you have already proved that it's not prime. For example, we know that 3x^2 + 5x + 2 must be composite (non-prime) because it can be factorised into (x+1)(3x+2) and both (x+1) and (3x+2) cannot be 1. EDIT: Also, either x+1 or 3x+2 must be even, and therefore the product must also be even.



Another useful identity would be a^2 + b^2 = (a+b)^2 - 2ab. This identity is a derivation of the expansion of (a+b)^2.



If you proceed using these hints the problem can be solved using no more than basic algebra operation.

Originally Posted by mad

I've got it...thanks to youngyew

[youngyew]

Will continue with number theory. The very basic stuff of number theory are those that we have learnt in secondary school (knowingly or unknowingly).

Fundamental theorem of arithmetic
First of all, there is this Fundamental Theorem of Arithmetic / unique factorisation theorem(name not important) which states that any natural number greater than one is either a prime number itself, or can be written as a unique product of prime numbers. For example, 1200 = 2^4 x 3 x 5^2 is the only way we can factorize 1200 into its prime factors. Whichever way you choose to factorise it, you will end with the same thing. While this may sound obvious, the formulation of this theorem is important and it is one of the basis of further theorems in number theory.

Divisibility
Read Wikipedia's article on divisor to get an idea of the basic rules on divisibility. Remember that x|y means that y is divisible by x. For example, valid relationships would include 2|266, 5|75.

Quoting some important properties from Wikipedia:

* If a | b and a | c, then a | (b + c), in fact, a | (mb + nc) for all integers m, n.
* If a | b and b | c, then a | c
* If a | b and b | a, then a = b or a = −b. [normally we don't really consider the negative values)
* If a | bc, and gcd(a,b) = 1, then a | c. (Euclid's lemma)


I have highlighted the more important ones with bold font. Note that some names such as Fundamental theorem of arithmetic, Euclid's lemma etc are not important, so don't waste time trying to remember the names. All the relationships above are almost trivial and we can easily prove them in our heads.


Greatest Common Divisor (Faktor Sepunya TerBesar)

We all have learnt GCD in secondary school, but we didn't really learn its properties. There are a lot of properties which may sound obvious but some of them are particularly useful and worth listing out. I will quote the wikipedia article below:

* Every common divisor of a and b is a divisor of gcd(a, b).

* gcd(a, b), where a and b are not both zero, may be defined alternatively and equivalently as the smallest positive integer d which can be written in the form d = a?p + b?q where p and q are integers. This expression is called B?zout's identity.

* If a divides the product b?c, and gcd(a, b) = d, then a/d divides c. [another result from Euclid's lemma, don't spend time memorising it but it is a good exercise to work on]

* The gcd is a multiplicative function in the following sense: if a1 and a2 are relatively prime, then gcd(a1?a2, b) = gcd(a1, b)?gcd(a2, b).

* The gcd of three numbers can be computed as gcd(a, b, c) = gcd(gcd(a, b), c) = gcd(a, gcd(b, c)). Thus the gcd is an associative operation.

* gcd(a, b) is closely related to the least common multiple lcm(a, b): we have

gcd(a, b)?lcm(a, b) = a?b.

The last property is something good to practise on. This is also an important identity which is worth memorising.


Try the first IMO, first question. Without looking at the solution.

Originally Posted by Kalva Demon site

Prove that (21n+4)/(14n+3) is irreducible for every natural number n.

It can be solved by one of the identity given in my previous post.


Note: Irreducible fraction means fraction that cannot be simplified. E.g. 6/8 is reducible (and becomes 3/4) but 9/16 is irreducible.



Hint 1: If a fraction is irreducible, what are the relationship between the denominator and numerator?



Hint 2: What is the relationship equivalent to, in terms of GCD?



Hint 3: What are the identity / theorem that can establish the relationship in hint 2?

Off to cooking... Will recover more after that.

[youngyew]

NUMBER THEORY

Least Common Multiple (Gandaan Sepunya TerKecil)

I can't really remember any interesting identities related to LCM, and some of the properties has already been included in the description of GCD.


Modular Arithmetic
This is the one thing you would lament nobody has taught you before, if you come out from OMK and somebody tells you the solution of the number theory question which is so easy, using modular arithmetic.

Before I start talking about modular arithmetic, some may complain that "What? The OMK problems require some theorems which are not in secondary school syllabus??? So unfair!!" (Note: Modular arithmetic is found in form 6 further maths syllabus, if im not mistaken) Well, this is not what really happens. The fact is, as you will see below, modular arithmetic is actually something you can figure out by yourself, and it is only a systematic representation of the knowledge. More importantly, I think number theory questions in OMK has so far avoided ones that must require modular arithmetic. Therefore, even if you know nothing about modular arithmetic, you will still be able to solve OMK number theory questions, you will only find it harder.

To begin with the usefulness of modular arithmetic, first try to prove this using your preexisting knowledge. I would recommend spending about 10 minutes on this, and try to appreciate the question's nature.

Originally Posted by One of the past OMK ques

If a and b are odd numbers (nombor ganjil), prove that a^2 + b^2 cannot be a square number.

Eerm, I will come back to that, now we will move on with modular arithmetic. It's quite hard to give a definition for arithmetic modular, but it will be clear using examples. We know when we divide 12 by 5, the remainder (baki) is 2; if we divide 22 by 5, the remainder is 2 as well. So, 12 and 22 share the property that "when divided by 5, remainder is 2". Now, modular arithmetic is a system to make us of this kind of properties (of remainders after division) in order to solve number theory questions.

In notation, the previous example would be expressed as:
12 ≡ 2 (mod 5)
22 ≡ 2 (mod 5)

We can also write like this:
12 ≡ 22 ≡ 2 (mod 5)

(note: mod is the short form of modulo)

In other words, when we are saying that a number is equal to (actual term is congruent to) another number in modulo 5, it just means that when those numbers are divided by 5, they will all end up with the same remainder. So, we have 3 ≡ 8 ≡ 13 ≡ 18 ≡ 23 ≡ 28 (mod 5).

Of course the usage of modulo is not constrained to modulo 5 alone, you can use it for any other natural numbers larger than 1. For example, odd numbers are all 1 (mod 2), even numbers are all 0 (mod 2).

Now, what's the use of all those mod thingy? The use is, we can perform some operation on them!

Firstly, it is important to note that when we know that x ≡ 3 (mod 5), it means that x must be a number which is a multiple of 5, with 3 added on top of it. In algebraic form, x = 5m + 3 where m is a integer.

Secondly, we can perform addition, subtraction and multiplication (but not division) using modular arithmetic. For example, say we have 12 ≡ 2 (mod 5), and 34 ≡ 4 (mod 5). So what is 46 (which is 12 + 34) mod 5? We can simply add up 2 and 4, and we will get 6 (mod 5). Next, what is 408 (which is 12 x 34) mod 5? We can simply multiply 2 and 4, and we will get 8 (mod 5), which is also equal to 3 (mod 5).

Now.... Let's observe some interesting phenomenon: In modulo 4, what can we say about all odd square numbers and all even square numbers? let's see, 1, 9, 25, 49, 81 etc... Tada! They are all 1 (mod 4)! What about 4, 16, 36, 64, 100 etc.. They are all 0 (mod 4)...

The reason of this is that, all odd number can be expressed as (2n + 1) and all even number (2n), where n is an integer. So the square of even number is 4n^2, which is obviously 0 (mod 4); while the square of odd number is 4n^2 + 4n + 1, which is obviously 1 (mod 4)

And so, we have a fast solution to the abovementioned problem! Now that odd square must be 1 (mod 4), and so a^2 + b^2 ≡ 2 (mod 4). And as we have shown above, a number which is 2 (mod 4) can't be a square. QED.


I will try to find some number theory questions which can be solved using modular arithmetic, and you will be amazed by its power.

With regard to the question on the previous post, I would like to show that it's still possible to solve without the usage of modular arithmetic:

Let a = (2n + 1) and b = (2m + 1). where n and m are positive integers.

So a^2 + b^2

= 4 (m^2 + n^2) + 4 (m + n) + 2

= 4K + 2 (where K is a positive integer)

Now, an even square must be a square of an even number. So it must be (2L)^2 = 4L^2.

Therefore, we arrive at a contradiction, which means that it is impossible to satisfy the condition stated in the question.

Originally Posted by colis

Youngyew, i can understand neither of your Maths solutions. Is it university level or i'm too poor(I'm in lowel six)?

NUMBER THEORY

I will show a simple example of how modular arithmetic can be useful in a number theory proof.

If we want to see whether a natural number is divisible by 3, just add up its digits. If the sum of the digits is divisible by 3, then the number itself is also divisible by 3. Show why this is true.

I think this is one of the most well-known divisibility checking method out there. For example, if we want to know whether 711 is divisible by 3, just do the summation (7 + 1 + 1 = 9). Since 9 is divisible by 3, then 711 is also divisible by 3.

The proof is as follows:

First of all, notice that 10 (mod 3) = 1, 100 (mod 3) = 1, 1000 (mod 3) = 1 and so on and so forth. In short, 10^n = 1 (mod 3) where n is a non-negative integer.

So, now let represent our number by its digit. If our number is 711, it can be broken up to 700 + 10 + 1. So if our three-digit number is a_0a_1a_2, it can also be broken up as (100 a_0) + (10 a_1) + (a_2). In general form, if a natural number is a_0a_1a_2a_3....a_i, then it can be broken up to (10^i a_0) + (10^(i-1) a_1) + ... + (10^1 a_(i-1)) + (a_i).

Now, we have:

a_0a_1a_2a_3....a_i (our original number)
= (10^i a_0) + (10^(i-1) a_1) + ... + (10^1 a_(i-1)) + (a_i) (mod 3)
= a_0 + a_1 + a_2 + ... + a_i (mod 3)

The final step is true since multiplication and addition is legitimate for modular arithmetic.

[youngyew]

Originally Posted by colis

Youngyew, i can understand neither of your Maths solutions. Is it university level or i'm too poor(I'm in lowel six)? Confused

Sorry for being confusing... I did make a few typo mistakes in my original post, and that might have been the reason you can't understand the solution. I have already corrected them, and please read through them again (and also the introduction parts). Also read up the wikipedia links, they are quite helpful. If you stil can't get it, tell me which specific part you don't get and I will try to explain.

NUMBER THEORY

I will end here today. Probably this will end my series of gibberish scribblings, since I am really short of time for my exam revision.

Euclid's Algorithm

The last thing I would like to introduce is "Euclid's Algorithm", which is a method for finding gcd of two numbers.

This is how Euclid's algorithm works:
Say you want to find the GCD of 124 and 28. First of all, divide 124 by 28, and the remainder is 12. Now, divide 28 by 12, and the remainder is 4. Divide 12 by 4, and the remainder is 0. So the GCD is 4.

Another example:
GCD of 1024 and 906. Divide 1024 by 906, remainder is 118. Divide 906 by 118, remainder is 80. Divide 118 by 80, remainder is 38. Divide 80 by 38, remainder is 4. Divide 38 by 4, remainder is 2. Divide 4 by 2, remainder is 0. Now, the GCD is 2.

In Euclid's algorithm,
1. We first divide the larger number by the smaller number, and get the remainder.
2. Then, divide the smaller number by the remainder, and get the remainder again.
3. Repeat step 2 until you get no remainder (remainder = 0).
4. The GCD would be the last number you used for the divisions. (refer to the examples above).


Euclid's algorithm is a fantastic tool in number theory. The wonderful thing is, you can even apply the same process on algebraic expressions! Try it on the first question of the first IMO (mentioned in one of the previous posts). You will solve it in no time.

That's all for today, good luck with your attempts!!

[youngyew]

Originally Posted by mad

I can't understand why 46 mod 5 will becomr 6. won't the remainder of 46 divide by 5 is 1?

They are all the same, 1 = 6 = 46 (mod 5). When two numbers are congruent in modulo 5, it just means that they have the same remainder while divided by 5.

Therefore, it's right to say 46 = 6 (mod 5) or 46 = 1 (mod 5). They mean the same. And which one you want to write really depends on the context.

I should have said, "We can simply add up 2 and 4, and we will get 6 (mod 5), which is also the same as 1 (mod 5).

[Seiryu]

Goodie. . i bookmarked the previous page but it's GONE!!!!

Thx youngyew

[youngyew]

Originally Posted by Seiryu

Goodie. . i bookmarked the previous page but it's GONE!!!!

Thx youngyew

No worries, I had only needed to look under my Google Desktop Search cache and weed out the html codes.

[markwongsk]

Originally Posted by youngyew

With regard to the question on the previous post, I would like to show that it's still possible to solve without the usage of modular arithmetic:

Let a = (2n + 1) and b = (2m + 1). where n and m are positive integers.

So a^2 + b^2

= 4 (m^2 + n^2) + 4 (m + n) + 2

= 4K + 2 (where K is a positive integer)

Now, an even square must be a square of an even number. So it must be (2L)^2 = 4L.

Therefore, we arrive at a contradiction, which means that it is impossible to satisfy the condition stated in the question.

Youngyew, your posts are great!!! I love them!!! Why haven't you been posting more =(

Anyway, (2L)^2 = 4L^2 right? (it doesnt change the veracity of the answer but there's a mistake )

[youngyew]

Corrected, thanks for pointing it out! I haven't got time to type more since I last did this, but there are many people in ReCom who can contribute in this thread so I would invite everyone to join the effort.

[youngyew]

Suhaimi Ramly, one of the ex-Olympiad contestor and currently one of the Malaysian IMO team leader, wrote about his experience in Maths Olympiad competition at the national leven and international level:

http://suhaimiramly.wordpress.com/20...mk-bahagian-1/
http://suhaimiramly.wordpress.com/20...mk-bahagian-2/
http://suhaimiramly.wordpress.com/20...mk-bahagian-3/