21 Questions
Question 1
Multiple Choice
Prove that there are no integers x, y such that x^2 = y^5 + 3.
Question 2
Multiple Choice
Show that if a set of n integers has the property that the sum of any n-1 elements is divisible by some integer k, then all elements are congruent modulo k.
Question 3
Multiple Choice
Let f: R -> R be a function such that f(x+y) + f(x-y) = 2f(x)f(y). If f(x) is not identically zero, prove that f(0)=1.
Question 4
Multiple Choice
Prove that for any prime p > 3, p^2 - 1 is divisible by 24.
Question 5
Multiple Choice
Prove that for any positive integer n, there exists a multiple of n whose decimal representation contains only the digits 0 and 1.
Question 6
Multiple Choice
Prove that in any set of 6 people, there exist either 3 mutual acquaintances or 3 mutual strangers.
Question 7
Multiple Choice
Let a, b, c be positive real numbers such that abc=1. Prove that 1/(a+b+1) + 1/(b+c+1) + 1/(c+a+1) <= 1.
Question 8
Multiple Choice
Let P(x) be a polynomial with integer coefficients such that P(a)=P(b)=P(c)=P(d)=-1 for four distinct integers a, b, c, d. Prove that P(x) has no integer roots.
Question 9
Multiple Choice
Show that the equation x^2 + y^2 = 3(z^2 + w^2) has no integer solutions other than (0,0,0,0).
Question 10
Multiple Choice
Prove that for any positive integer n, the number 2^n does not divide n!.
1 Question was hidden because it is incomplete or invalid.
IMO Shortlist
Flashcards generated with inquiziti.com. Cut along the dashed lines. Fold in half on the solid line.
Prove that there are no integers x, y such that x^2 = y^5 + 3.
Consider the equation modulo 11. The fifth powers mod 11 are 0, 1, -1. Thus y^5+3 is 2, 3, or 4 mod 11. However, squares mod 11 are 0, 1, 3, 4, 5, 9.
Show that if a set of n integers has the property that the sum of any n-1 elements is divisible by some integer k, then all elements are congruent modulo k.
Let S be the sum of all elements. Then S-a_i is divisible by k for all i. Thus S-a_i = m_i*k. Subtracting two such equations gives a_i - a_j = (m_j-m_i)k.
Let f: R -> R be a function such that f(x+y) + f(x-y) = 2f(x)f(y). If f(x) is not identically zero, prove that f(0)=1.
Setting x=0 and y=0 gives 2f(0) = 2f(0)^2, so f(0) is 0 or 1. If f(0)=0, then f(x)=0 for all x, contradicting the non-zero assumption.
Prove that for any prime p > 3, p^2 - 1 is divisible by 24.
Since p is not divisible by 2 or 3, p is congruent to 1 or 5 mod 6. Thus p^2 is 1 mod 12, and since p is odd, p^2-1 is divisible by 8.
Prove that for any positive integer n, there exists a multiple of n whose decimal representation contains only the digits 0 and 1.
Consider the n+1 numbers 1, 11, 111, ..., 11...1 (n+1 ones). By the Pigeonhole Principle, two must be congruent modulo n, and their difference is a multiple of n consisting only of 0s and 1s.
Prove that in any set of 6 people, there exist either 3 mutual acquaintances or 3 mutual strangers.
Pick one person; they have either 3 friends or 3 strangers among the other 5. If they have 3 friends, either two are friends (forming a triangle) or all are strangers.
Let a, b, c be positive real numbers such that abc=1. Prove that 1/(a+b+1) + 1/(b+c+1) + 1/(c+a+1) <= 1.
Use the substitution a=x^3, b=y^3, c=z^3 and apply the Cauchy-Schwarz inequality or Jensen's inequality on the convex function f(t)=1/(e^t+e^u+1).
Let P(x) be a polynomial with integer coefficients such that P(a)=P(b)=P(c)=P(d)=-1 for four distinct integers a, b, c, d. Prove that P(x) has no integer roots.
If P(k)=0 for some integer k, then (k-a), (k-b), (k-c), and (k-d) must divide P(k)-P(a)=1, which is impossible for four distinct integers.
Show that the equation x^2 + y^2 = 3(z^2 + w^2) has no integer solutions other than (0,0,0,0).
Consider the equation modulo 3. Squares are 0 or 1 mod 3. For the sum to be 0 mod 3, all variables must be divisible by 3, allowing for infinite descent.
Prove that for any positive integer n, the number 2^n does not divide n!.
Legendre's Formula states the exponent of 2 in n! is n - s_2(n), where s_2(n) is the sum of binary digits. Since s_2(n) >= 1, the exponent is always less than n.
Generating Functions
A way of encoding a sequence of numbers as coefficients of a formal power series.
Euler's Totient Theorem
A generalization of Fermat's Little Theorem relating powers modulo n to the totient function.
Jensen's Inequality
A statement relating the value of a convex function of an integral to the integral of the convex function.
Cauchy-Schwarz Inequality
A fundamental inequality relating the inner product of two vectors to the product of their norms.
AM-GM Inequality
The arithmetic mean of a set of non-negative real numbers is greater than or equal to their geometric mean.
Vieta's Formulas
Relationships between the coefficients of a polynomial and the sums and products of its roots.
Lucas's Theorem
A result for calculating binomial coefficients modulo a prime p.
Pigeonhole Principle
If n items are put into m containers, with n > m, then at least one container must contain more than one item.
Inversion Transformation
A geometric mapping that sends points inside a circle to points outside, preserving angles.
Pick's Theorem
A formula for the area of a polygon whose vertices are on an integer grid.