USAMO Practice Session
Berkeley Math Circle 2001-2002
Kiran Kedlaya

The practice problems for the April 28 session can be found at the end of this handout. If you are reading this beforehand, I strongly encourage you to try as many of the problems as you can before the session; we will go through as many as we can during the session, and student input on how you approached the problems will be most helpful! If you need more practice problems in a hurry: the American Mathematics Competition web site carries the problems (but no solutions) for the USA and International Mathematical Olympiads for the past few years.

General advice for new Olympians.

• Practice, practice! The only way to develop your skills is to try Olympiad-level problems.
• One way to test whether you really understand the solution to a problem is to explain it to someone else, especially someone who isn't familiar with the problem.
• Lears from your peers! Most problems have multiple solutions. Compare notes with others; they may have ideas that you missed or vice versa.
• Make sure to consume a ``balanced diet'' of problems, including your ``recommended daily allowance'' of each of the following: algebra, combinatorics, geometry, inequalities, number theory.
• Don't despair! Many great problem solvers started slowly. Again, practice is critical.

Solving tips.

• Keep your scratch paper organized; you never know where good ideas will come from. Have a separate set of scratch sheets for each problem.
• In Olympiad situations, you usually have several problems to work on at once (three for each USAMO session, five for BAMO). It's a good idea to spend a little time at the beginning trying each of the problems; the easiest problem is not always the one listed first, and is sometimes a matter of personal taste.
• One useful preparation strategy is to make a mental ``toolbox'' of tricks that you have seen in other problems. (Example: for geometry, this might include similar triangles, cyclic quadrilaterals, etc.)
• If the problem you're given looks too hard, try a special case or a variant that looks easier; it may give you some insight toward the original problem. (If the problem asks about general $n$, try a small value, say 2 or 3; if the problem asks about a triangle, try an isosceles triangle; etc.)
• Work backwards. Ask yourself what you could deduce if you already knew what you were trying to prove. (This is especially useful in geometry.)
• For geometry problems, draw careful diagrams; they may show you something you didn't know. (In particular, make sure to bring a compass and ruler.)
• Beware of ``bogosity'', the belief that you have a correct proof when you don't. Many a solver (including your presenter) has been prevented from finding a correct proof by the belief that they already have one! This is most dangerous with inequalities; there are many false proofs of true statements which founder on a single flipped inequality.

Writing tips.

• Proofs are essays, plain and simple. That doesn't mean you'll be marked off for grammar or spelling. It does mean that being able to communicate your arguments effectively is a big advantage, and that expressing your thoughts in a fragment, incoherent manner may hurt you if the graders can't figure out what you meant.
• In a similar vein, some simple steps can make the lives of the graders easier. (And anything that makes the lives of the graders easier makes it more likely that you will get the points you deserve.) Some such: leave margins at the edges of the page. Write neatly.
• If you have to remove a significant amount of text (say, more than a sentence), don't erase or obliterate it; cross it out lightly so that it is still possible to read what is underneath. Even the crossed-out material may be useful to the graders!
• Often, a small amount of partial credit will be given for something that you might find ``obvious''. (E.g., in some cases, giving the correct answer to a question without a proof may be worth a point.) If you're completely stuck on a problem, it's still worth pointing out anything you've noticed in case it's relevant. (But please don't turn in heaps and heaps of unintelligible scratch work!)
• If you have to define a word or symbol for your own use, by all means do it, but put the definition in a prominent place. In a similar vein: if you refer to a diagram, make sure to define in the text anything you labeled on the diagram that isn't given in the problem.

Some practice problems. These problems (and their solutions) appear in Mathematical Contests 1996-1997, part of a series published by the American Mathematics Comptetions (and more recently by the Mathematical Association of America).

1. (Turkey) Let
   
   $$\prod_{n=1}^{1996} \left( 1 + n x^{3^n} \right) = 1 + a_1 x^{k_1} + a_2 x^{k_2} + \cdots + a_m x^{k_m},$$
   
   
   where $a_1, a_2, \dots, a_m$ are nonzero and $k_1 < k_2 < \cdots < k_m$. Find $a_{1996}$.
2. (Turkey) In a convex quadrilateral $ABCD$, triangles $ABC$ and $ADC$ have the same area. Let $E$ be the intersection of $AC$ and $BD$, and let the parallels through $E$ to the lines $AD, DC, CB, BA$ meet $AB, BC, CD, DA$ at $K,L,M,N$, respectively. Compute the ratio of the areas of the quadrilaterals $KLMN$ and $ABCD$.
3. (Japan) Let $m$ and $n$ be positive integers with $\gcd(m,n) = 1$. Compute $\gcd(5^m+7^m, 5^n+7^n)$.
4. (Bulgaria) The sequence $\{a_n\}_{n=1}^\infty$ is defined by
   
   $$a_1 = 1, \qquad a_{n+1} = \frac{a_n}{n} + \frac{n}{a_n}, \qquad n \geq 1.$$
   
   
   Prove that for $n \geq 4$, $\lfloor a_n^2 \rfloor = n$.
5. (China) Eight singers participate in an art festival where $m$ songs are performed. Each song is performed by 4 singers, and each pair of singers performs together in the same number of songs. Find the smallest $m$ for which this is possible.
6. (Russia) In isosceles triangle $ABC$ ($AB=BC$) draw the angle bisector $CD$. The perpendicular to $CD$ through the center of the circumcircle of $ABC$ intersects $BC$ and $E$. The parallel to $CD$ through $E$ meets $AB$ at $F$. Show that $BE=FD$.
7. (Russia) Find all natural numbers $n$ such that there exist relatively prime integers $x$ and $y$ and an integer $k>1$ satisfying the equation $3^n = x^k + y^k$.