5th All Soviet Union Mathematical Olympiad 1971 Problems & Solutions

1.  Prove that we can find a number divisible by 2ⁿ whose decimal representation uses only the digits 1 and 2.

2.  (1) A₁A₂A₃ is a triangle. Points B₁, B₂, B₃ are chosen on A₁A₂, A₂A₃, A₃A₁ respectively and points D₁, D₂ D₃ on A₃A₁, A₁A₂, A₂A₃ respectively, so that if parallelograms A_iB_iC_iD_i are formed, then the lines A_iC_i concur. Show that A₁B₁·A₂B₂·A₃B₃ = A₁D₁·A₂D₂·A₃D₃. (2) A₁A₂ ... A_n is a convex polygon. Points B_i are chosen on A_iA_i+1 (where we take A_n+1 to mean A₁), and points D_i on A_i-1A_i (where we take A₀ to mean A_n) such that if parallelograms A_iB_iC_iD_i are formed, then the n lines A_iC_i concur. Show that ∏ A_iB_i = ∏ A_iD_i.

3.  (1) Player A writes down two rows of 10 positive integers, one under the other. The numbers must be chosen so that if a is under b and c is under d, then a + d = b + c. Player B is allowed to ask for the identity of the number in row i, column j. How many questions must he ask to be sure of determining all the numbers? (2) An m x n array of positive integers is written on the blackboard. It has the property that for any four numbers a, b, c, d with a and b in the same row, c and d in the same row, a above c (in the same column) and b above d (in the same column) we have a + d = b + c. If some numbers are wiped off, how many must be left for the table to be accurately restored?

4.  Circles, each with radius less than R, are drawn inside a square side 1000R. There are no points on different circles a distance R apart. Show that the total area covered by the circles does not exceed 340,000 R².

5.  You are given three positive integers. A move consists of replacing m ≤ n by 2m, n-m. Show that you can always make a series of moves which results in one of the integers becoming zero. [For example, if you start with 4, 5, 10, then you could get 8, 5, 6, then 3, 10, 6, then 6, 7, 6, then 0, 7, 12.]

6.  The real numbers a, b, A, B satisfy (B - b)² < (A - a)(Ba - Ab). Show that the quadratics x² + ax + b = 0 and x² + Ax + B = 0 have real roots and between the roots of each there is a root of the other.

7.  The projections of a body on two planes are circles. Show that the circles have the same radius.

8.  An integer is written at each vertex of a regular n-gon. A move is to find four adjacent vertices with numbers a, b, c, d (in that order), so that (a - d)(b - c) < 0, and then to interchange b and c. Show that only finitely many moves are possible. For example, a possible sequence of moves is shown below:

1  7  2  3  5  4
1  2  7  3  5  4
1  2  3  7  5  4
1  2  3  5  7  4
2  1  3  5  7  4

9.  A polygon P has an inscribed circle center O. If a line divides P into two polygons with equal areas and equal perimeters, show that it must pass through O.

10.  Given any set S of 25 positive integers, show that you can always find two such that none of the other numbers equals their sum or difference.

11.  A and B are adjacent vertices of a 12-gon. Vertex A is marked - and the other vertices are marked +. You are allowed to change the sign of any n adjacent vertices. Show that by a succession of moves of this type with n = 6 you cannot get B marked - and the other vertices marked +. Show that the same is true if all moves have n = 3 or if all moves have n = 4.

12.  Equally spaced perpendicular lines divide a large piece of paper into unit squares. N squares are colored black. Show that you can always cut out a set of disjoint square pieces of paper, so that all the black squares are removed and the black area of each piece is between 1/5 and 4/5 of its total area.

13.  n is a positive integer. S is the set of all triples (a, b, c) such that 1 ≤ a, b, c, ≤ n. What is the smallest subset X of triples such that for every member of S one can find a member of X which differs in only one position. [For example, for n = 2, one could take X = { (1, 1, 1), (2, 2, 2) }.]

14.  Let f(x, y) = x² + xy + y². Show that given any real x, y one can always find integers m, n such that f(x-m, y-n) <= 1/3. What is the corresponding result if f(x, y) = x² + axy + y² with 0 ≤ a ≤ 2?

15.  A switch has two inputs 1, 2 and two outputs 1, 2. It either connects 1 to 1 and 2 to 2, or 1 to 2 and 2 to 1. If you have three inputs 1, 2, 3 and three outputs 1, 2, 3, then you can use three switches, the first across 1 and 2, then the second across 2 and 3, and finally the third across 1 and 2. It is easy to check that this allows the output to be any permutation of the inputs and that at least three switches are required to achieve this. What is the minimum number of switches required for 4 inputs, so that by suitably setting the switches the output can be any permutation of the inputs? 

Solutions

Problem 1

Prove that we can find a number divisible by 2ⁿ whose decimal representation uses only the digits 1 and 2.

Solution

Induction on n. We claim that we can find N with n digits, all 1 or 2, so that N is divisible by 2ⁿ. True for n = 1: take N = 2. Suppose it is true for n. If 2ⁿ⁺¹ divides N, then since 2ⁿ⁺¹ divides 2 x 10ⁿ it also divides N' obtained from N by placing a 2 in front of it. If 2ⁿ⁺¹ does not divide N, then N = 2ⁿ x odd and 10ⁿ = 2ⁿ x odd, so N + 10ⁿ (in other words the n+1 digit number obtained by placing a 1 in front of N) is divisible by 2ⁿ⁺¹. 

Problem 1

(1) Player A writes down two rows of 10 positive integers, one under the other. The numbers must be chosen so that if a is under b and c is under d, then a + d = b + c. Player B is allowed to ask for the identity of the number in row i, column j. How many questions must he ask to be sure of determining all the numbers?

(2) An m x n array of positive integers is written on the blackboard. It has the property that for any four numbers a, b, c, d with a and b in the same row, c and d in the same row, a above c (in the same column) and b above d (in the same column) we have a + d = b + c. If some numbers are wiped off, how many must be left for the table to be accurately restored?

Solution

(1) is trivial. We can write the condition as b - a = d - c, so the 10 numbers in the first row and 1 in the second row can all be chosen arbitrarily. Hence at least 11 questions are needed. But they are also sufficient. Having determined those numbers, the others immediately follow.

(2). The m+n-1 numbers in the first row and first column can all be chosen arbitrarily, but are sufficient to determine all the numbers. Hence at least m+n-1 numbers must survive.