olymmath

ISL 2007

IMO Shortlist 2007.

Other problems

A1

Given a sequence a1,a2,…,ana_{1}, a_{2}, \ldots, a_{n} of real numbers. For each i(1≤i≤n)i(1 \leq i \leq n) define di=max⁡{aj:1≤j≤i}−min⁡{aj:i≤j≤n}d_{i}=\max \left\{a_{j}: 1 \leq j \leq i\right\}-\min \left\{a_{j}: i \leq j \leq n\right\} and let d=max⁡{di:1≤i≤n}d=\max \left\{d_{i}: 1 \leq i \leq n\right\} (a) Prove that for arbitrary real numbers x1≤x2≤…≤xnx_{1} \leq x_{2} \leq \ldots \leq x_{n}, max⁡{∣xi−ai∣:1≤i≤n}≥d2\max \left\{\left|x_{i}-a_{i}\right|: 1 \leq i \leq n\right\} \geq \frac{d}{2} (b) Show that there exists a sequence x1≤x2≤…≤xnx_{1} \leq x_{2} \leq \ldots \leq x_{n} of real numbers such that we have equality in (1). (New Zealand)

A2

Consider those functions f:N→Nf: \mathbb{N} \rightarrow \mathbb{N} which satisfy the condition f(m+n)≥f(m)+f(f(n))−1f(m+n) \geq f(m)+f(f(n))-1 for all m,n∈Nm, n \in \mathbb{N}. Find all possible values of f(2007)f(2007). (N(\mathbb{N} denotes the set of all positive integers.) (Bulgaria)

A3

Let nn be a positive integer, and let xx and yy be positive real numbers such that xn+yn=1x^{n}+y^{n}=1. Prove that (∑k=1n1+x2k1+x4k)(∑k=1n1+y2k1+y4k)<1(1−x)(1−y)\left(\sum_{k=1}^{n} \frac{1+x^{2 k}}{1+x^{4 k}}\right)\left(\sum_{k=1}^{n} \frac{1+y^{2 k}}{1+y^{4 k}}\right)<\frac{1}{(1-x)(1-y)} (Estonia)

A4

Find all functions f:R+→R+f: \mathbb{R}^{+} \rightarrow \mathbb{R}^{+}such that f(x+f(y))=f(x+y)+f(y)f(x+f(y))=f(x+y)+f(y) for all x,y∈R+x, y \in \mathbb{R}^{+}. (Symbol R+\mathbb{R}^{+}denotes the set of all positive real numbers.) (Thaliand)

A5

Let c>2c>2, and let a(1),a(2),…a(1), a(2), \ldots be a sequence of nonnegative real numbers such that a(m+n)≤2a(m)+2a(n) for all m,n≥1, a(m+n) \leq 2 a(m)+2 a(n) \text { for all } m, n \geq 1 \text {, } and a(2k)≤1(k+1)c for all k≥0a\left(2^{k}\right) \leq \frac{1}{(k+1)^{c}} \text { for all } k \geq 0 Prove that the sequence a(n)a(n) is bounded. (Croatia)

A6

Let a1,a2,…,a100a_{1}, a_{2}, \ldots, a_{100} be nonnegative real numbers such that a12+a22+…+a1002=1a_{1}^{2}+a_{2}^{2}+\ldots+a_{100}^{2}=1. Prove that a12a2+a22a3+…+a1002a1<1225a_{1}^{2} a_{2}+a_{2}^{2} a_{3}+\ldots+a_{100}^{2} a_{1}<\frac{12}{25} (Poland)

A7 · Also IMO 2007 Problem 6

Let nn be a positive integer. Consider S={(x,y,z)∣x,y,z∈{0,1,…,n},x+y+z>0}S = \left\{ (x,y,z) \mid x,y,z \in \{ 0, 1, \ldots, n\}, x + y + z > 0 \right \} as a set of (n+1)3−1(n + 1)^{3} - 1 points in the three-dimensional space. Determine the smallest possible number of planes, the union of which contains SS but does not include (0,0,0)(0,0,0) .

Author: Gerhard Wöginger, Netherlands

C1

Let n>1n>1 be an integer. Find all sequences a1,a2,…,an2+na_{1}, a_{2}, \ldots, a_{n^{2}+n} satisfying the following conditions: (a) ai∈{0,1}a_{i} \in\{0,1\} for all 1≤i≤n2+n1 \leq i \leq n^{2}+n; (b) ai+1+ai+2+…+ai+n<ai+n+1+ai+n+2+…+ai+2na_{i+1}+a_{i+2}+\ldots+a_{i+n}<a_{i+n+1}+a_{i+n+2}+\ldots+a_{i+2 n} for all 0≤i≤n2−n0 \leq i \leq n^{2}-n. (Serbia)

C2

A unit square is dissected into n>1n>1 rectangles such that their sides are parallel to the sides of the square. Any line, parallel to a side of the square and intersecting its interior, also intersects the interior of some rectangle. Prove that in this dissection, there exists a rectangle having no point on the boundary of the square. (Japan)

C3

Find all positive integers nn, for which the numbers in the set S={1,2,…,n}S=\{1,2, \ldots, n\} can be colored red and blue, with the following condition being satisfied: the set S×S×SS \times S \times S contains exactly 2007 ordered triples (x,y,z)(x, y, z) such that (i) x,y,zx, y, z are of the same color and (ii) x+y+zx+y+z is divisible by nn. (Netherlands)

C4

Let A0=(a1,…,an)A_{0}=\left(a_{1}, \ldots, a_{n}\right) be a finite sequence of real numbers. For each k≥0k \geq 0, from the sequence Ak=(x1,…,xn)A_{k}=\left(x_{1}, \ldots, x_{n}\right) we construct a new sequence Ak+1A_{k+1} in the following way. 1. We choose a partition {1,…,n}=I∪J\{1, \ldots, n\}=I \cup J, where II and JJ are two disjoint sets, such that the expression ∣∑i∈Ixi−∑j∈Jxj∣\left|\sum_{i \in I} x_{i}-\sum_{j \in J} x_{j}\right| attains the smallest possible value. (We allow the sets II or JJ to be empty; in this case the corresponding sum is 0 .) If there are several such partitions, one is chosen arbitrarily. 2. We set Ak+1=(y1,…,yn)A_{k+1}=\left(y_{1}, \ldots, y_{n}\right), where yi=xi+1y_{i}=x_{i}+1 if i∈Ii \in I, and yi=xi−1y_{i}=x_{i}-1 if i∈Ji \in J. Prove that for some kk, the sequence AkA_{k} contains an element xx such that ∣x∣≥n/2|x| \geq n / 2. (Iran)

C5

In the Cartesian coordinate plane define the strip Sn={(x,y)∣n≤x<n+1}S_{n}=\{(x, y) \mid n \leq x<n+1\} for every integer nn. Assume that each strip SnS_{n} is colored either red or blue, and let aa and bb be two distinct positive integers. Prove that there exists a rectangle with side lengths aa and bb such that its vertices have the same color. (Romania)

C6 · Also IMO 2007 Problem 3

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a clique if each two of them are friends. (In particular, any group of fewer than two competitiors is a clique.) The number of members of a clique is called its size.

Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.

Author: Vasily Astakhov, Russia

C7

Let α<3−52\alpha<\frac{3-\sqrt{5}}{2} be a positive real number. Prove that there exist positive integers nn and p>α⋅2np>\alpha \cdot 2^{n} for which one can select 2p2 p pairwise distinct subsets S1,…,Sp,T1,…,TpS_{1}, \ldots, S_{p}, T_{1}, \ldots, T_{p} of the set {1,2,…,n}\{1,2, \ldots, n\} such that Si∩Tj≠∅S_{i} \cap T_{j} \neq \varnothing for all 1≤i,j≤p1 \leq i, j \leq p. (Austria)

C8

Given a convex nn-gon PP in the plane. For every three vertices of PP, consider the triangle determined by them. Call such a triangle good if all its sides are of unit length. Prove that there are not more than 23n\frac{2}{3} n good triangles. (Ukraine)

G1

In triangle ABCA B C, the angle bisector at vertex CC intersects the circumcircle and the perpendicular bisectors of sides BCB C and CAC A at points R,PR, P, and QQ, respectively. The midpoints of BCB C and CAC A are SS and TT, respectively. Prove that triangles RQTR Q T and RPSR P S have the same area. (Czech Republic)

G2

Given an isosceles triangle ABCA B C with AB=ACA B=A C. The midpoint of side BCB C is denoted by MM. Let XX be a variable point on the shorter arc MAM A of the circumcircle of triangle ABMA B M. Let TT be the point in the angle domain BMAB M A, for which ∠TMX=90∘\angle T M X=90^{\circ} and TX=BXT X=B X. Prove that ∠MTB−∠CTM\angle M T B-\angle C T M does not depend on XX. (Canada)

G3

The diagonals of a trapezoid ABCDA B C D intersect at point PP. Point QQ lies between the parallel lines BCB C and ADA D such that ∠AQD=∠CQB\angle A Q D=\angle C Q B, and line CDC D separates points PP and QQ. Prove that ∠BQP=∠DAQ\angle B Q P=\angle D A Q. (Ukraine)

G4 · Also IMO 2007 Problem 2

Consider five points AA , BB , CC , DD and EE such that ABCDABCD is a parallelogram and BCEDBCED is a cyclic quadrilateral. Let ℓ\ell be a line passing through AA . Suppose that ℓ\ell intersects the interior of the segment DCDC at FF and intersects line BCBC at GG . Suppose also that EF=EG=ECEF = EG = EC . Prove that ℓ\ell is the bisector of angle DABDAB .

Author: Charles Leytem, Luxembourg

G5

Let ABCA B C be a fixed triangle, and let A1,B1,C1A_{1}, B_{1}, C_{1} be the midpoints of sides BC,CA,ABB C, C A, A B, respectively. Let PP be a variable point on the circumcircle. Let lines PA1,PB1,PC1P A_{1}, P B_{1}, P C_{1} meet the circumcircle again at A′,B′,C′A^{\prime}, B^{\prime}, C^{\prime} respectively. Assume that the points A,B,C,A′,B′,C′A, B, C, A^{\prime}, B^{\prime}, C^{\prime} are distinct, and lines AA′,BB′,CC′A A^{\prime}, B B^{\prime}, C C^{\prime} form a triangle. Prove that the area of this triangle does not depend on PP. (United Kingdom)

G6

Determine the smallest positive real number kk with the following property. Let ABCDA B C D be a convex quadrilateral, and let points A1,B1,C1A_{1}, B_{1}, C_{1} and D1D_{1} lie on sides AB,BCA B, B C, CDC D and DAD A, respectively. Consider the areas of triangles AA1D1,BB1A1,CC1B1A A_{1} D_{1}, B B_{1} A_{1}, C C_{1} B_{1}, and DD1C1D D_{1} C_{1}; let SS be the sum of the two smallest ones, and let S1S_{1} be the area of quadrilateral A1B1C1D1A_{1} B_{1} C_{1} D_{1}. Then we always have kS1≥Sk S_{1} \geq S. (U.S.A.)

G7

Given an acute triangle ABCA B C with angles α,β\alpha, \beta and γ\gamma at vertices A,BA, B and CC, respectively, such that β>γ\beta>\gamma. Point II is the incenter, and RR is the circumradius. Point DD is the foot of the altitude from vertex AA. Point KK lies on line ADA D such that AK=2RA K=2 R, and DD separates AA and KK. Finally, lines DID I and KIK I meet sides ACA C and BCB C at EE and FF, respectively. Prove that if IE=IFI E=I F then β≤3γ\beta \leq 3 \gamma. (Iran)

G8

Point PP lies on side ABA B of a convex quadrilateral ABCDA B C D. Let ω\omega be the incircle of triangle CPDC P D, and let II be its incenter. Suppose that ω\omega is tangent to the incircles of triangles APDA P D and BPCB P C at points KK and LL, respectively. Let lines ACA C and BDB D meet at EE, and let lines AKA K and BLB L meet at FF. Prove that points E,IE, I, and FF are collinear. (Poland)

N1

Find all pairs (k,n)(k, n) of positive integers for which 7k−3n7^{k}-3^{n} divides k4+n2k^{4}+n^{2}. (Austria)

N2

Let b,n>1b, n>1 be integers. Suppose that for each k>1k>1 there exists an integer aka_{k} such that b−aknb-a_{k}^{n} is divisible by kk. Prove that b=Anb=A^{n} for some integer AA. (Canada)

N3

Let XX be a set of 10000 integers, none of them is divisible by 47 . Prove that there exists a 2007-element subset YY of XX such that a−b+c−d+ea-b+c-d+e is not divisible by 47 for any a,b,c,d,e∈Ya, b, c, d, e \in Y. (Netherlands)

N4

For every integer k≥2k \geq 2, prove that 23k2^{3 k} divides the number (2k+12k)−(2k2k−1)\left(\begin{array}{c} 2^{k+1} \\ 2^{k} \end{array}\right)-\left(\begin{array}{c} 2^{k} \\ 2^{k-1} \end{array}\right) but 23k+12^{3 k+1} does not. (Poland)

N5

Find all surjective functions f:N→Nf: \mathbb{N} \rightarrow \mathbb{N} such that for every m,n∈Nm, n \in \mathbb{N} and every prime pp, the number f(m+n)f(m+n) is divisible by pp if and only if f(m)+f(n)f(m)+f(n) is divisible by pp. ( N\mathbb{N} is the set of all positive integers.) (Iran)

N6

Let kk be a positive integer. Prove that the number (4k2−1)2\left(4 k^{2}-1\right)^{2} has a positive divisor of the form 8kn−18 k n-1 if and only if kk is even. (United Kingdom)

N7

For a prime pp and a positive integer nn, denote by νp(n)\nu_{p}(n) the exponent of pp in the prime factorization of nn !. Given a positive integer dd and a finite set {p1,…,pk}\left\{p_{1}, \ldots, p_{k}\right\} of primes. Show that there are infinitely many positive integers nn such that d∣νpi(n)d \mid \nu_{p_{i}}(n) for all 1≤i≤k1 \leq i \leq k. (India)