MathDB

1989 IMO Longlists

Part of IMO Longlists

Subcontests

(72)
8
1
7
1
3
1
2
1
99
1
98
1
97
1

Prove that f1 and f2 are independent

An arithmetic function is a real-valued function whose domain is the set of positive integers. Define the convolution product of two arithmetic functions f f and g g to be the arithmetic function f∗g f * g, where (f * g)(n) \equal{} \sum_{ij\equal{}n} f(i) \cdot g(j), and f^{*k} \equal{} f * f * \ldots * f (k k times) We say that two arithmetic functions f f and g g are dependent if there exists a nontrivial polynomial of two variables P(x, y) \equal{} \sum_{i,j} a_{ij} x^i y^j with real coefficients such that P(f,g) \equal{} \sum_{i,j} a_{ij} f^{*i} * g^{*j} \equal{} 0, and say that they are independent if they are not dependent. Let p p and q q be two distinct primes and set f_1(n) \equal{} \begin{cases} 1 & \text{ if } n \equal{} p, \\ 0 & \text{ otherwise}. \end{cases} f_2(n) \equal{} \begin{cases} 1 & \text{ if } n \equal{} q, \\ 0 & \text{ otherwise}. \end{cases} Prove that f1 f_1 and f2 f_2 are independent.
96
1
95
1
92
1
91
1
90
1
88
1
85
1
82
1
81
1
80
1

A pointer that moves along a graduated ruler

A balance has a left pan, a right pan, and a pointer that moves along a graduated ruler. Like many other grocer balances, this one works as follows: An object of weight L L is placed in the left pan and another of weight R R in the right pan, the pointer stops at the number R \minus{} L on the graduated ruler. There are n,(n≥2) n, (n \geq 2) bags of coins, each containing \frac{n(n\minus{}1)}{2} \plus{} 1 coins. All coins look the same (shape, color, and so on). n\minus{}1 bags contain real coins, all with the same weight. The other bag (we don’t know which one it is) contains false coins. All false coins have the same weight, and this weight is different from the weight of the real coins. A legal weighing consists of placing a certain number of coins in one of the pans, putting a certain number of coins in the other pan, and reading the number given by the pointer in the graduated ruler. With just two legal weighings it is possible to identify the bag containing false coins. Find a way to do this and explain it.
79
1

Power tower s.t. T_n(3) > T_{1989}(2)

Given two natural numbers w w and n, n, the tower of n n w′s w's is the natural number Tn(w) T_n(w) defined by Tn(w)=ww⋯w, T_n(w) = w^{w^{\cdots^{w}}}, with n n w′s w's on the right side. More precisely, T1(w)=w T_1(w) = w and Tn+1(w)=wTn(w). T_{n+1}(w) = w^{T_n(w)}. For example, T3(2)=222=16, T_3(2) = 2^{2^2} = 16, T4(2)=216=65536, T_4(2) = 2^{16} = 65536, and T2(3)=33=27. T_2(3) = 3^3 = 27. Find the smallest tower of 3′s 3's that exceeds the tower of 1989 1989 2′s. 2's. In other words, find the smallest value of n n such that Tn(3)>T1989(2). T_n(3) > T_{1989}(2). Justify your answer.
78
1
77
1
76
1
75
1
73
1
72
1

Prove that exactly one of the following situations occurs

To each pair (x,y) (x, y) of distinct elements of a finite set X X a number f(x,y) f(x, y) equal to 0 or 1 is assigned in such a way that f(x,y)≠f(y,x) f(x, y) \neq f(y, x) ∀x,y \forall x,y and x≠y. x \neq y. Prove that exactly one of the following situations occurs: (i) X X is the union of two disjoint nonempty subsets U,V U, V such that f(u, v) \equal{} 1 ∀u∈U,v∈V. \forall u \in U, v \in V. (ii) The elements of X X can be labeled x1,…,xn x_1, \ldots , x_n so that f(x_1, x_2) \equal{} f(x_2, x_3) \equal{} \cdots \equal{} f(x_{n\minus{}1}, x_n) \equal{} f(x_n, x_1) \equal{} 1. Alternative formulation: In a tournament of n participants, each pair plays one game (no ties). Prove that exactly one of the following situations occurs: (i) The league can be partitioned into two nonempty groups such that each player in one of these groups has won against each player of the other. (ii) All participants can be ranked 1 through n n so that i\minus{}th player wins the game against the (i \plus{} 1)st and the n\minus{}th player wins against the first.
70
1
69
1

There exists a permutation

Let k k and s s be positive integers. For sets of real numbers {α1,α2,…,αs} \{\alpha_1, \alpha_2, \ldots , \alpha_s\} and {β1,β2,…,βs} \{\beta_1, \beta_2, \ldots, \beta_s\} that satisfy \sum^s_{i\equal{}1} \alpha^j_i \equal{} \sum^s_{i\equal{}1} \beta^j_i   \forall j \equal{} \{1,2 \ldots, k\} we write \{\alpha_1, \alpha_2, \ldots , \alpha_s\} \overset{k}{\equal{}} \{\beta_1, \beta_2, \ldots , \beta_s\}. Prove that if \{\alpha_1, \alpha_2, \ldots , \alpha_s\} \overset{k}{\equal{}} \{\beta_1, \beta_2, \ldots , \beta_s\} and s≤k, s \leq k, then there exists a permutation π \pi of {1,2,…,s} \{1, 2, \ldots , s\} such that \beta_i \equal{} \alpha_{\pi(i)}   \forall i \equal{} 1,2, \ldots, s.
65
1
63
1
61
1
60
1
58
1
57
1
56
1
54
1

Prove that n = 23

Let n \equal{} 2k \minus{} 1 where k≥6 k \geq 6 is an integer. Let T T be the set of all n\minus{}tuples (x1,x2,…,xn) (x_1, x_2, \ldots, x_n) where xi∈{0,1} x_i \in \{0,1\} \forall i \equal{} \{1,2, \ldots, n\} For x \equal{} (x_1, x_2, \ldots, x_n) \in T and y \equal{} (y_1, y_2, \ldots, y_n) \in T let d(x,y) d(x,y) denote the number of integers j j with 1≤j≤n 1 \leq j \leq n such that xi≠xj x_i \neq x_j, in particular d(x,x) \equal{} 0. Suppose that there exists a subset S S of T T with 2k 2^k elements that has the following property: Given any element x∈T, x \in T, there is a unique element y∈S y \in S with d(x,y)≤3. d(x, y) \leq 3. Prove that n \equal{} 23.
53
1
52
1
51
1
49
1
47
1

Determine the set of admissible X

Let A,B A,B denote two distinct fixed points in space. Let X,P X, P denote variable points (in space), while K,N,n K,N, n denote positive integers. Call (X,K,N,P) (X,K,N,P) admissible if (N \minus{} K) \cdot PA \plus{} K \cdot PB \geq N \cdot PX. Call (X,K,N) (X,K,N) admissible if (X,K,N,P) (X,K,N,P) is admissible for all choices of P. P. Call (X,N) (X,N) admissible if (X,K,N) (X,K,N) is admissible for some choice of K K in the interval 0<K<N. 0 < K < N. Finally, call X X admissible if (X,N) (X,N) is admissible for some choice of N,(N>1). N, (N > 1). Determine: (a) the set of admissible X; X; (b) the set of X X for which (X,1989) (X, 1989) is admissible but not (X,n),n<1989. (X, n), n < 1989.
46
1
45
1
44
1

Ways that the product of n distinct letters be formed?

Given two distinct numbers b1 b_1 and b2 b_2, their product can be formed in two ways: b1×b2 b_1 \times b_2 and b2×b1. b_2 \times b_1. Given three distinct numbers, b1,b2,b3, b_1, b_2, b_3, their product can be formed in twelve ways: b1×(b2×b3); b_1\times(b_2 \times b_3); (b1×b2)×b3; (b_1 \times b_2) \times b_3; b1×(b3×b2); b_1 \times (b_3 \times b_2); (b1×b3)×b2; (b_1 \times b_3) \times b_2; b2×(b1×b3); b_2 \times (b_1 \times b_3); (b2×b1)×b3; (b_2 \times b_1) \times b_3; b2×(b3×b1); b_2 \times(b_3 \times b_1); (b2×b3)×b1; (b_2 \times b_3)\times b_1; b3×(b1×b2); b_3 \times(b_1 \times b_2); (b3×b1)×b2; (b_3 \times b_1)\times b_2; b3×(b2×b1); b_3 \times(b_2 \times b_1); (b3×b2)×b1. (b_3 \times b_2) \times b_1. In how many ways can the product of n n distinct letters be formed?
43
1
42
1
41
1
39
1
38
1
36
1
34
1
33
1
32
1
31
1
30
1
28
1
27
1
26
1
25
1
24
1
23
1
21
1

Coloured blue, white and red

Let ABC ABC be an equilateral triangle with side length equal to N∈N. N \in \mathbb{N}. Consider the set S S of all points M M inside the triangle ABC ABC satisfying \overrightarrow{AM} \equal{} \frac{1}{N} \cdot \left(n \cdot \overrightarrow{AB} \plus{} m \cdot \overrightarrow{AC} \right) with m,n m, n integers, 0≤n≤N, 0 \leq n \leq N, 0≤m≤N 0 \leq m \leq N and n \plus{} m \leq N. Every point of S is colored in one of the three colors blue, white, red such that (i) no point of S∩[AB] S \cap [AB] is coloured blue (ii) no point of S∩[AC] S \cap [AC] is coloured white (iii) no point of S∩[BC] S \cap [BC] is coloured red Prove that there exists an equilateral triangle the following properties: (1) the three vertices of the triangle are points of S S and coloured blue, white and red, respectively. (2) the length of the sides of the triangle is equal to 1. Variant: Same problem but with a regular tetrahedron and four different colors used.
19
1
18
1
17
1
15
1
13
1
12
1
11
1
10
2
9
2
6
2

Concyclic if segments are diameters

The circles c1 c_1 and c2 c_2 are tangent at the point A. A. A straight line l l through A A intersects c1 c_1 and c2 c_2 at points C1 C_1 and C2 C_2 respectively. A circle c, c, which contains C1 C_1 and C2, C_2, meets c1 c_1 and c2 c_2 at points B1 B_1 and B2 B_2 respectively. Let ω \omega be the circle circumscribed around triangle AB1B2. AB_1B_2. The circle k k tangent to ω \omega at the point A A meets c1 c_1 and c2 c_2 at the points D1 D_1 and D2 D_2 respectively. Prove that (a) the points C1,C2,D1,D2 C_1,C_2,D_1,D_2 are concyclic or collinear, (b) the points B1,B2,D1,D2 B_1,B_2,D_1,D_2 are concyclic if and only if AC1 AC_1 and AC2 AC_2 are diameters of c1 c_1 and c2. c_2.

Function of area of a triangle

Let E E be the set of all triangles whose only points with integer coordinates (in the Cartesian coordinate system in space), in its interior or on its sides, are its three vertices, and let f f be the function of area of a triangle. Determine the set of values f(E) f(E) of f. f.
5
2

Bounded by Pi

The sequences a0,a1,… a_0, a_1, \ldots and b0,b1,… b_0, b_1, \ldots are defined for n \equal{} 0, 1, 2, \ldots by the equalities a_0 \equal{} \frac {\sqrt {2}}{2},   a_{n \plus{} 1} \equal{} \frac {\sqrt {2}}{2} \cdot \sqrt {1 \minus{} \sqrt {1 \minus{} a^2_n}} and b_0 \equal{} 1,   b_{n \plus{} 1} \equal{} \frac {\sqrt {1 \plus{} b^2_n} \minus{} 1}{b_n} Prove the inequalities for every n \equal{} 0, 1, 2, \ldots 2^{n \plus{} 2} a_n < \pi < 2^{n \plus{} 2} b_n.

Prove two properties for functions

Let n>1 n > 1 be a fixed integer. Define functions f_0(x) \equal{} 0, f_1(x) \equal{} 1 \minus{} \cos(x), and for k>0, k > 0, f_{k\plus{}1}(x) \equal{} f_k(x) \cdot \cos(x) \minus{} f_{k\minus{}1}(x). If F(x) \equal{} \sum^n_{r\equal{}1} f_r(x), prove that (a) 0<F(x)<1 0 < F(x) < 1 for 0 < x < \frac{\pi}{n\plus{}1}, and (b) F(x)>1 F(x) > 1 for \frac{\pi}{n\plus{}1} < x < \frac{\pi}{n}.
1
2

Multiplication table for the new product for n=11 and n=12

In the set S_n \equal{} \{1, 2,\ldots ,n\} a new multiplication a∗b a*b is defined with the following properties: (i) c \equal{} a * b is in Sn S_n for any a∈Sn,b∈Sn. a \in S_n, b \in S_n. (ii) If the ordinary product a⋅b a \cdot b is less than or equal to n, n, then a*b \equal{} a \cdot b. (iii) The ordinary rules of multiplication hold for ∗, *, i.e.: (1) a * b \equal{} b * a (commutativity) (2) (a * b) * c \equal{} a * (b * c) (associativity) (3) If a * b \equal{} a * c then b \equal{} c (cancellation law). Find a suitable multiplication table for the new product for n \equal{} 11 and n \equal{} 12.

Equal to the area of the quadrangle

If in a convex quadrilateral ABCD,E ABCD, E and F F are the midpoints of the sides BC BC and DA DA respectively. Show that the sum of the areas of the triangles EDA EDA and FBC FBC is equal to the area of the quadrangle.