MathDB

2005 IMO Shortlist

Part of IMO Shortlist

Subcontests

(8)
8
1
5
3

Invariance

There are n n markers, each with one side white and the other side black. In the beginning, these n n markers are aligned in a row so that their white sides are all up. In each step, if possible, we choose a marker whose white side is up (but not one of the outermost markers), remove it, and reverse the closest marker to the left of it and also reverse the closest marker to the right of it. Prove that, by a finite sequence of such steps, one can achieve a state with only two markers remaining if and only if n \minus{} 1 is not divisible by 3 3.
Proposed by Dusan Dukic, Serbia

Hard to approach it !

Let △ABC\triangle ABC be an acute-angled triangle with AB≠ACAB \not= AC. Let HH be the orthocenter of triangle ABCABC, and let MM be the midpoint of the side BCBC. Let DD be a point on the side ABAB and EE a point on the side ACAC such that AE=ADAE=AD and the points DD, HH, EE are on the same line. Prove that the line HMHM is perpendicular to the common chord of the circumscribed circles of triangle △ABC\triangle ABC and triangle △ADE\triangle ADE.

Highly divisible positive integers

Denote by d(n)d(n) the number of divisors of the positive integer nn. A positive integer nn is called highly divisible if d(n)>d(m)d(n) > d(m) for all positive integers m<nm < n. Two highly divisible integers mm and nn with m<nm < n are called consecutive if there exists no highly divisible integer ss satisfying m<s<nm < s < n. (a) Show that there are only finitely many pairs of consecutive highly divisible integers of the form (a,b)(a, b) with a∣ba\mid b. (b) Show that for every prime number pp there exist infinitely many positive highly divisible integers rr such that prpr is also highly divisible.
3
4
7
3

Two permutations

Suppose that a1 a_1, a2 a_2, … \ldots, an a_n are integers such that n\mid a_1 \plus{} a_2 \plus{} \ldots \plus{} a_n. Prove that there exist two permutations (b1,b2,…,bn) \left(b_1,b_2,\ldots,b_n\right) and (c1,c2,…,cn) \left(c_1,c_2,\ldots,c_n\right) of (1,2,…,n) \left(1,2,\ldots,n\right) such that for each integer i i with 1≤i≤n 1\leq i\leq n, we have n\mid a_i \minus{} b_i \minus{} c_i
Proposed by Ricky Liu & Zuming Feng, USA

perimeter Inequality [p(ABC) p(PQR) &gt;= (p(DEF))^2]

In an acute triangle ABCABC, let DD, EE, FF be the feet of the perpendiculars from the points AA, BB, CC to the lines BCBC, CACA, ABAB, respectively, and let PP, QQ, RR be the feet of the perpendiculars from the points AA, BB, CC to the lines EFEF, FDFD, DEDE, respectively.
Prove that p(ABC)p(PQR)≥(p(DEF))2p\left(ABC\right)p\left(PQR\right) \ge \left(p\left(DEF\right)\right)^{2}, where p(T)p\left(T\right) denotes the perimeter of triangle TT .
Proposed by Hojoo Lee, Korea

P(m!) is composite

Let P(x)=anxn+an−1xn−1+…+a0P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots+a_{0}, where a0,…,ana_{0},\ldots,a_{n} are integers, an>0a_{n}>0, n≥2n\geq 2. Prove that there exists a positive integer mm such that P(m!)P(m!) is a composite number.
2
2

Functional equation

We denote by \mathbb{R}^\plus{} the set of all positive real numbers.
Find all functions f: \mathbb R^ \plus{} \rightarrow\mathbb R^ \plus{} which have the property: f(x)f(y)\equal{}2f(x\plus{}yf(x)) for all positive real numbers xx and yy.
Proposed by Nikolai Nikolov, Bulgaria

The sombrero problem

This ISL 2005 problem has not been used in any TST I know. A pity, since it is a nice problem, but in its shortlist formulation, it is absolutely incomprehensible. Here is a mathematical restatement of the problem:
Let kk be a nonnegative integer.
A forest consists of rooted (i. e. oriented) trees. Each vertex of the forest is either a leaf or has two successors. A vertex vv is called an extended successor of a vertex uu if there is a chain of vertices u0=uu_{0}=u, u1u_{1}, u2u_{2}, ..., ut−1u_{t-1}, ut=vu_{t}=v with t>0t>0 such that the vertex ui+1u_{i+1} is a successor of the vertex uiu_{i} for every integer ii with 0≤i≤t−10\leq i\leq t-1. A vertex is called dynastic if it has two successors and each of these successors has at least kk extended successors.
Prove that if the forest has nn vertices, then there are at most nk+2\frac{n}{k+2} dynastic vertices.
6
2
4
3

Functional equation

Find all functions f:R→R f: \mathbb{R}\to\mathbb{R} such that f(x+y)+f(x)f(y)=f(xy)+2xy+1 f(x+y)+f(x)f(y)=f(xy)+2xy+1 for all real numbers x x and y y.
Proposed by B.J. Venkatachala, India

Labelling edges of a complete graph - maximal # of labels?

Let n≥3n\geq 3 be a fixed integer. Each side and each diagonal of a regular nn-gon is labelled with a number from the set {1;  2;  ...;  r}\left\{1;\;2;\;...;\;r\right\} in a way such that the following two conditions are fulfilled:
1. Each number from the set {1;  2;  ...;  r}\left\{1;\;2;\;...;\;r\right\} occurs at least once as a label.
2. In each triangle formed by three vertices of the nn-gon, two of the sides are labelled with the same number, and this number is greater than the label of the third side.
(a) Find the maximal rr for which such a labelling is possible.
(b) Harder version (IMO Shortlist 2005): For this maximal value of rr, how many such labellings are there?
[hide="Easier version (5th German TST 2006) - contains answer to the harder version"] Easier version (5th German TST 2006): Show that, for this maximal value of rr, there are exactly n!(n−1)!2n−1\frac{n!\left(n-1\right)!}{2^{n-1}} possible labellings.
Proposed by Federico Ardila, Colombia

Factorial: n!|a^n+1

Find all positive integers n n such that there exists a unique integer a a such that 0≤a<n! 0\leq a < n! with the following property: n!\mid a^n \plus{} 1
Proposed by Carlos Caicedo, Colombia
1
3

Not hard but cute (points lying on a circle)

Given a triangle ABCABC satisfying AC+BC=3⋅ABAC+BC=3\cdot AB. The incircle of triangle ABCABC has center II and touches the sides BCBC and CACA at the points DD and EE, respectively. Let KK and LL be the reflections of the points DD and EE with respect to II. Prove that the points AA, BB, KK, LL lie on one circle.
Proposed by Dimitris Kontogiannis, Greece

polynomial with coefficients in {1,-1}

Find all pairs of integers a,ba,b for which there exists a polynomial P(x)∈Z[X]P(x) \in \mathbb{Z}[X] such that product (x2+ax+b)⋅P(x)(x^2+ax+b)\cdot P(x) is a polynomial of a form xn+cn−1xn−1+⋯+c1x+c0 x^n+c_{n-1}x^{n-1}+\cdots+c_1x+c_0 where each of c0,c1,…,cn−1c_0,c_1,\ldots,c_{n-1} is equal to 11 or −1-1.

shortlist2005

A house has an even number of lamps distributed among its rooms in such a way that there are at least three lamps in every room. Each lamp shares a switch with exactly one other lamp, not necessarily from the same room. Each change in the switch shared by two lamps changes their states simultaneously. Prove that for every initial state of the lamps there exists a sequence of changes in some of the switches at the end of which each room contains lamps which are on as well as lamps which are off.
Proposed by Australia