Math Olympiad Preparation II

In this post I am going to talk mainly about how to prepare for Math Olympiad. I am going to discuss two different approaches.  At the bottom of this post are two videos I created with more information on me, Math Olympiad prep, and my online tutoring services.

The first method is to start off with solving Olympiad-type questions. You can, for example, find past IMO exams here and see how well you can do. There are many other websites and books containing Olympiad-type problems and solutions. In this method I'd suggest you start with old exams. They tend to be much easier. In the process, you will find out which subjects you need to work on. Try to spend at least 2 hours on each problem before looking up their solutions. You will most probably not be able to solve many of the problems and you will find some subjects in the solutions that you might not be familiar with. Then you can work on those subjects and theorems. This method is good if you feel confident that you know the subjects in Math Olympiad fairly well or you are at least fairly comfortable with the materials. Otherwise this method won't work for you. Many solutions to Olympiad problems have similar ideas. So the more problems you solve the more experienced you get.

The second method is to try to learn all subjects well before starting to solve any problems. This method is a lot more time consuming and I'd suggest it to 10th or 11th grade students who have enough time to prepare for Olympiad. The advantage of this method is that what you learn not only helps you with Olympiad preparation, but it is also helpful for you in the future as it gives you a better understanding and insight of Math. Also this method ensures you that you have covered all the materials needed for Math Olympiad. In contrast the first method makes you a problem solver which is very good and may be enough to be successful in Math Olympiad. However it may not give you a good mathematician or may not give you a good understanding and insight of Math.

These two general approaches remain valid for Putnam preparation or any similar exams.

In the end, if you want to be successful you need to do A LOT of problems. Even if you find a solution to a problem, look at the solutions and try to understand all different solutions in case there are more than one solutions. Each solution gives you a new method. Have all these methods in mind as they are going to help you some day in solving a problem.

Try to keep a few latest official exams from IMO, USAMO or similar exams untouched. When you are a few weeks away from you official exam give yourself 9 hours and solve these exams separately. This would help you understand how you are doing. However, keep in mind that you won't necessarily perform the same in the actual exam.

I enjoy working with students to help them prepare for advanced mathematics competitions.   The first video below presents my approach towards mentoring students.  The second video discusses more my credentials and then demonstrates how I work with students online using Tutor Hero's professional technology for 1-on-1 tutoring.  Click here if you'd like to sign-up for a tutoring session with me.

Pick's Theorem

In one of my classes I was asked if I could give a proof for the Pick's Theorem. I decided to share the proof here. This is an interesting proof that anybody who is preparing for Math Olympiad would find interesting. But first what is the Pick's Theorem? To state the Pick's Theorem I need to first define "lattice points".

Definition: Any point on the $xy$-plane with integer coordinates is called a lattice point.

Here is the statement of the Pick's Theorem:

Pick's Theorem: For any polygon on the $xy$-plane whose vertices are lattice points we have $A=I+B/2-1$ where $A$ is the area of the polygon, $I$ is the number of its interior lattice points and $B$ is the number of its boundary lattice points.

Here is an elementary proof for the Pick's Theorem.

First of all one can show this equality holds for any lattice rectangle whose sides are parallel to the axes. This is not very hard but needs a bit of calculation.

Now, for any polygon $P$ lets call the RHS by $C(P)$, i.e., $C(P)=I+B/2-1$ for the polygon $P$. We need to show $A(P)=C(P)$. It is easy to show if a polygon $P$ if the union of two polygons $R$ and $Q$ then $C(P)=C(R)+C(Q)$ and $A(P)=A(R)+A(Q)$. Since any polygon can be divided into triangles we only need to prove Pick's Theorem for triangles. Now again if you use this additivity you can see that you only need to show this equality for a triangle when there is no interior or boundary lattice points except for the vertices.

Now, I first show $A(P)\geq C(P)$. Again by induction you only need to show this inequality for when $P$ is a triangle with no interior or boundary lattice points except for its vertices. One can calculate $C(P)$ to get $C(P)=1/2$ so we need to show $A(P)\geq 1/2$. To show this we only need to show $2A(P)\geq 1$ but $2A(P)$ is the area of a parallelogram with lattice point as its vertices. But the area of a parallelogram is the the magnitude of the cross product of two vectors forming this parallelogram. This can be easily shown to be at least 1.

If you don't know what a cross product is try this alternative method for evaluating the area of the triangle. Lets say we have a triangle $ABC$ whose vertices are lattice points. As shown in the picture below draw a vertical line from A so that this line intersects $BC$ at $D$.

Use coordinated of $B$ and $C$ to write down an equation of the line $BC$. Find coordinates of $D$ using the equation of this line and the $x$-coordinate of $A$. Now using this information evaluate the area of $ABC$ as the sum of two areas of triangles $ADC$ and $ADB$ and show this area is at least $1/2$.

This shows that for any polygon $P$, $A(P)\geq C(P)$.

Now assume for a triangle $P$, we have $A(P)>C(P)$. Using two vertices of this triangle you can draw a rectangle whose sides are parallel to the axes and contains this triangle and two of its vertices are the vertices of this triangle as shown in the following picture.

As shown in the above picture, divide this rectangle into four triangles. For each one of this triangles we know that $A(P)\geq C(P)$, but for the rectangle we already showed that $A(P)=C(P)$ which shows for the triangle $ABC$ the equality should hold also.

Some parts of this proof needs a bit of work that is left to the reader.

Auto Draft

Solution of FLT for $n=4$.

I discussed FLT in an earlier post and stated a problem that if solved FLT for $n=4$ will be deduced from there. Below is a solution to that problem.

Assume $(a, b, c)$ is a “non-trivial” triple of integers that satisfies

$a^4+b^4=c^2$ (1) .

By “non-trivial” we mean “$abc\neq 0$". Obviously we can assume that $a, b$ and $c$ are positive. If we show for any such triple, there is another triple satisfying the same equation with a smaller $c$, then using the method of “infinite descent” we get a contradiction, and therefore we can deduce that there is no “non-trivial” solutions for $a^4+b^4=c^2$.

Now one can show that $a, b$ and $c$ are relatively prime. Otherwise you can find a “smaller” solution for the equation (1). Therefore $(a^2, b^2, c)$ is a Pythagorean triple and we have two relatively prime integers $x$ and $y$ such that:

$a^2 = 2xy, b^2=x^2-y^2, c=x^2+y^2$

Using the fact that $b$ is odd (why?) and the equation $b^2=x^2-y^2$ we can deduce that $x$ is odd and $y$ is even (why?). Now since $x$ and $y$ are relatively prime and $2xy$ is a perfect square we can deduce that $2y$ and $x$ are perfect squares (why?). Therefore there are two relatively prime integers $m$ and $n$ such that $x=m^2$ and $2y=n^2$.

Now look at the equation $x^2=y^2+b^2$ and use the formula for Pythagorean triples. So there are relatively prime integers $u$ and $v$ such that:

$x=u^2+v^2, y=2uv, b=u^2-v^2$

Now since $2y$ is a perfect square, $uv$ should be a perfect square. Therefore both $u$ and $v$ are perfect squares. Therefore there are integers $r$ and $s$ such that $u=r^2$ and $v=s^2$. Combine this with the equations $x=u^2+v^2$ and $x=m^2$ and you get $m^2=r^4+s^4$. So, the triple $(r, s, m)$ is a triple satisfying (1) which is what we were looking for. We only need to show this triple is “non-trivial” and that $m<c$. I leave this to the reader, but it is fairly easy.

Try to fill in the gaps in the above solution.

Mathematics Olympiad Preparation

International Mathematics Olympiad is a highly respected competition which is held yearly. It is a place where many mathematicians are hoping to motivate the best students to continue their studies in Math. A lot of participants end up becoming the best mathematicians later in their career. My Ph.D. adviser Professor Gregory Margulis who won the Fields Medal in 1978- among many other prestigious Math prizes- won a silver medal in the 4^th IMO. Two other examples of these mathematicians are 2006 and 2010 winners of Fields Medal, Terence Tao and Elon Lindenstrauss.

Different countries have different policies toward IMO. Some countries like China and my home country Iran train their teams for a long time, up to a year. Others may only hold a few exams and select their teams with a brief training.

This year the USA Math Olympiad exam is going to be held on April 27-28, 2011. As you might know, the exam is a 9 hour, 2 day exam with 3 questions each day. Generally, each day the 3 problems are sorted in the order of their difficulty. Meaning that you can generally expect the first and fourth problems to be the easiest problems. The third and sixth problems are usually the hardest ones. You can get more information about USAMO from their website here.

For more information about Math Olympiad Preparation, including some videos I made to help students, go here.  If you'd like to sign-up for online tutoring with me, you can schedule a session with me here.

Fermat's Last Theorem

One of the most important achievements of the 20th century in Math is a proof of the Fermat's Last Theorem. It states:

Fermat's Last Theorem. Let $a, b, c$ and $n$ be 4 integers such that $n\geq 3$ and $a^n+b^n=c^n$. Then $abc=0$.

In our previous post we discussed all solutions of this equation for $n=2$ as Pythagorean Triples. Proof of FLT involves advanced Mathematics. Here I would like to bring up a especial case of this theorem for $n=4$. More generally one can prove the following.

Problem. If $a^4+b^4=c^2$ for 3 integers $a, b$ and $c$, then $abc=0$.

One can prove the above statement using infinite descent and combining it with Pythagorean Triples. Think about it if you get a chance. A proof will be posted later.

Pythagorean Triples

Any three integers $a, b,$ and $c$ that can be lengths of sides of a right triangle is a called Pythagorean triple. But we can also think of negative numbers as Pythagorean triples when they satisfy the equation $c^2=a^2+b^2$. Here I would like to show you a simple method to find all Pythagorean triples.

Asssume $d$ is the greatest common divisor of $a, b$ and $c$, i.e. $g.c.d.(a,b,c)=d$. If we divide $a, b,$ and $c$ with $d$ obviously we get another Pythagorean triples. Therefore to find all Pythagorean triples it is enough to find all triples with g.c.d.=1.  Therefore we may assume $a,b,$ and $c$ have no common factors.  One can check that one of $a$ or $b$ has the same parity as $c$.  (why?) Assume $a$ and $c$ have the same parity. Now write the equation as: $b^2 = (c-a)(c+a)$. Now one can show $(c-a)/2$ and $(c+a)/2$ are co-prime integers. (why?)  Therefore both of them are perfect squares. (why?) Therefore there are  integers $m, n$ such that:

$c-a = 2n^2$ and $c+a = 2m^2$.  Therefore $b^2 = 4m^2n^2$. Hence we have the following:

$a = m^2-n^2$

$b=\pm 2mn$

$c=m^2+n^2$

We may drop $\pm$ for $b$ since $m$ and $n$ range over all integers. If we multiply these by $d$ we get a formula for all Pythagorean triples. Therefore any Pythagorean triple is of the following form:

$a = d(m^2-n^2)$

$b=2dmn$

$c=d(m^2+n^2)$

where $m, n$ and $d$ are three integers.

Try to fill in the gaps of this proof. This is especially important if it is your first time seeing this proof or similar proofs.

Infinite Descent

Infinite descent is a common mathematical method that we use in solving problems and proofs. It is based on a very simple and intuitive fact: every non-empty set of natural numbers has a smallest number. This means if you show a set of natural numbers has no smallest number that set should be empty. This method is commonly used to attack some problems in number theory. Especially for finding solutions to some specific Diophantine equations.

I understand that wikipedia is not the most reliable source of information out there, but a lot of their articles are very useful, so I suggest you take a look at this wiki article to find out more about Infinite Descent. Make sure to look at the examples.

Solution of the previous problem

Here is the solution to the problem that I posted earlier.

By Sylow Theorem we know that the number of $p$-Sylow subgroups should divide $p(p+1)$. On the other hand this number is congruent to $1$ modulo $p$. So, we have either $1$ or $p+1$, Sylow $p-$subgroups. If there is no normal subgroup of order $p$ we should have $p+1$ Sylow $p-$subgroups.

Let $\{ H_i | 1\leq i \leq p+1 \}$ be the set of all $p$-Sylow subrgoups of $G$. One can check the number of elements in $\cup_{1\leq i \leq p+1}H_i$ is $p^2$. Notice that all $H_i$'s are conjugate. Therefore, we have $[G:N_G(H_i)] = p+1$, where $N_G(H)$ is the normilizer of $H$ in $G$. Hence, $|N_G(H_i)|=p$, which means $N_G(H_i)=H_i$ for any $i$.

Take an element $x$ outside of all $H_i$'s and take an element $1\neq a\in H_1$. We have $H_1 = <a>$. One may check that all elements $a^i x a^i$ are different when $0\leq i \leq p-1$. These are $p$ elements that are conjugate to $x$, hence none of them is inside any $H_i$. Since there is only $p$ elements outside of all $H_i$'s these are the only elements outside of $H_i$'s. Therefore $x$ has exactly $p$ conjugates. Hence, $[G:C_G(x)]=p$. therefore $|C_G(x)|=p+1$. Since elements of $H_i$'s have order $1$ or $p$, $C_G(x)$ intersects all $H_i$'s at the identity element. Therefore $C_G(x)$ consists of the identity and all elements of $G$ outside of all $H_i$'s. Obviously no conjugate of $C_G(x)$ has an element of order $p$, therefore $C_G(x)$ is normal in $G$.

A Group Theory Problem

I remember as a freshman in college I was given a group theory problem in an exam that I couldn't solve at the time. (There was no hints though ) I may have heard the solution later but a few days ago I was thinking about that problem. So here is the problem and some hints. It is a nice and challenging problem. You might want to think about it before looking at the solution. The solution will be posted later.

Problem. Let $G$ be a group of size $p(p+1)$ where $p$ is a prime number. Show that $G$ has a normal subgroup of size either $p$ or $p+1$.

Hint #1: Use the Sylow theorem and count the number of $p$-Sylow subgroups of $G$. Show that if a $p$-Sylow subgroup is not normal then there is only $p$ elements outside of these Sylow subgroups which form a group.

Hint #2: Prove that these elements commute and deduce they form a normal subgroup. To show this, count the number of conjugates of an element outside of all of these $p$-Sylow subgroups.

I will post a complete solution later.

Some notations and basics

Before posting my solution to the first problem I thought I'd post some basic facts and notations that I am going to use. If you are not familiar with these basic facts it is good to check them. Everybody should check these at least once in their lifetime.

Let $G$ be a group and $H$ its subgroup. $N_G(H)$ denotes the set of all elements $x\in G$ such that $H=xHx^{-1}$. One can check that $N_G(H)$ is a subgroup of $G$ containing $H$. $xHx^{-1}$ is called a conjugate of $H$. You can check that the number of conjugates of $H$ is $[G:N_G(H)]$.

$C_G(x)$ is the set of all elements in $G$ that commute with $x$. One can check this forms a subgroup of $G$. Furthermore, the number of conjugates of $x$ equals $[G:C_G(x)]$.