IMO 1996 Shortlisted Problems with Solutions

Algebra

A1. Find all polynomials \(P(x)\) with integer coefficients such that \[ P(x^2+1)=xP(x)+xP(-x)+2x^2 \] for all integers \(x\). S

A2. Let \(x_1,x_2,\ldots,x_n>0\). Prove \[ \frac{1}{1+x_1}+\frac{1}{1+x_2}+\cdots+\frac{1}{1+x_n}\ge\frac{n}{1+\sqrt[n]{x_1x_2\cdots x_n}}. \] S

A3. Let \(a,b,c\) be positive integers such that \(abc+1\) divides \((a+1)(b+1)(c+1)\). Show that \[ \frac{(a+1)(b+1)(c+1)}{abc+1} \] is a perfect square. S

Combinatorics

C1. Let \(S\) be a segment of positive integers. Show that among any \(2|S|-1\) distinct integers there are three, either in increasing or in decreasing order, whose pairwise differences all lie in \(S\). S

C2. A row of \(n\) lamps is given, each either on or off. In a move, you may choose any two adjacent lamps and toggle both. Determine for which \(n\) it is possible to switch all lamps off. S

C3. Find the number of ordered pairs \((A,B)\) of subsets of \(\{1,2,\ldots,n\}\) such that \(A\cap B=\emptyset\) and \(A\cup B=\{1,2,\ldots,n\}\). S

C4. A pile of \(n^2\) stones is split into \(n\) piles of \(n\) each. A move consists of choosing two piles of stones and moving a single stone from one to the other. Show that after finitely many moves, all the piles will have the same number of stones. S

Geometry

G1. In triangle \(ABC\), let \(P\) be any point inside. Prove \[ PA+PB+PC\le2(s-a), \] where \(s\) is the semiperimeter and \(a=BC\). S

G2. In triangle \(ABC\), point \(D\) on \(BC\) satisfies \(BD=DC\). The circumcircle of \(ABD\) meets \(AC\) again at \(E\). Prove \(\angle BDE=\angle BAC\). S

G3. In acute triangle \(ABC\), the altitudes meet the opposite sides at \(D,E,F\). Show that \[ \angle BDE+\angle CEF=\angle BAC. \] S

Number Theory

N1. Let \(p\) be a prime. Show that for any integers \(a_1,a_2,\ldots,a_p\), \[ a_1^p+a_2^p+\cdots+a_p^p-a_1-a_2-\cdots-a_p \] is divisible by \(p\). S

N2. If \(n\) is a positive integer not divisible by 3, show that there is a multiple of \(n\) with digit sum \(1996\). S

N3. Show that there are infinitely many primes \(p\) such that the order of \(10\) modulo \(p\) is divisible by 3. S

N4. Let \(a_n\) be defined by \(a_0=0\), \(a_1=1\), and \[ a_{n+2} = 1996a_{n+1}-a_n. \] Find \(a_{1996}\) modulo 1996. S