RU-ALLRUSSIAN 1971

Prove that we can find a number divisible by $2^{n}$ whose decimal representation uses only the digits 1 and 2.

(1) $\mathrm{A_1A_2A_3}$ is a triangle. Points $\mathrm{B_1}$ , $\mathrm{B_2}$ , $\mathrm{B_3}$ are chosen on $\mathrm{A_1A_2}$ , $\mathrm{A_2A_3}$ , $\mathrm{A_3A_1}$ respectively and points $\mathrm{D_1}$ , $\mathrm{D_2}$ $\mathrm{D_3}$ on $\mathrm{A_3A_1}$ , $\mathrm{A_1A_2}$ , $\mathrm{A_2A_3}$ respectively, so that if parallelograms $\mathrm{A_iB_iC_iD_i}$ are formed, then the lines $\mathrm{A_iC_i}$ concur. Show that $\mathrm{A_1B_1}$ : $\mathrm{A_2B_2}$ : $\mathrm{A_3B_3} = \mathrm{A_1D_1}$ : $\mathrm{A_2D_2}$ : $\mathrm{A_3D_3}$ .

(2) $\mathrm{A_1A_2\ldots A_n}$ is a convex polygon. Points $\mathrm{B_i}$ are chosen on $\mathrm{A_iA_{i + 1}}$ (where we take $\mathrm{A_{n + 1}}$ to mean $\mathrm{A_1}$ ), and points $\mathrm{D_i}$ on $\mathrm{A_{i - 1}A_i}$ (where we take $\mathrm{A_0}$ to mean $\mathrm{A_n}$ ) such that if parallelograms $\mathrm{A_iB_iC_iD_i}$ are formed, then the n lines $\mathrm{A_iC_i}$ concur. Show that $\prod \mathrm{A_iB_i} = \prod \mathrm{A_iD_i}$ .

(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?

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 \mathrm{R}^2$ .

You are given three positive integers. A move consists of replacing $\mathrm{m}\leq \mathrm{n}$ by $2\mathrm{m}$ , 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. ]

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

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

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 $(\mathrm{a} - \mathrm{d})(\mathrm{b} - \mathrm{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:

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.

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.

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 $\mathrm{n} = 6$ you cannot get B marked - and the other vertices marked +. Show that the same is true if all moves have $\mathrm{n} = 3$ or if all moves have $\mathrm{n} = 4$ .

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.

n is a positive integer. S is the set of all triples (a, b, c) such that $1 \leq a, b, c, \leq 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) \} .$ ]

Let $\operatorname {f}(\mathbf{x}, \mathbf{y}) = \mathbf{x}^{2} + \mathbf{x}\mathbf{y} + \mathbf{y}^{2}$ . Show that given any real $\mathbf{x}$ , $\mathbf{y}$ one can always find integers $\mathbf{m}, \mathbf{n}$ such that $\operatorname {f}(\mathbf{x} - \mathbf{m}, \mathbf{y} - \mathbf{n}) \leq = 1 / 3$ . What is the corresponding result if $\operatorname {f}(\mathbf{x}, \mathbf{y}) = \mathbf{x}^{2} + \mathbf{a}\mathbf{x}\mathbf{y} + \mathbf{y}^{2}$ with 0 $\leq \mathbf{a} \leq 2$ ?

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?