1st All Russian Mathematical Olympiad Problems 1961

1.  Given 12 vertices and 16 edges arranged as follows:

Draw any curve which does not pass through any vertex. Prove that the curve cannot intersect each edge just once. Intersection means that the curve crosses the edge from one side to the other. For example, a circle which had one of the edges as tangent would not intersect that edge.

2.  Given a rectangle ABCD with AC length e and four circles centers A, B, C, D and radii a, b, c, d respectively, satisfying a+c=b+d<e. Prove you can inscribe a circle inside the quadrilateral whose sides are the two outer common tangents to the circles center A and C, and the two outer common tangents to the circles center B and D.

3.  Prove that any 39 successive natural numbers include at least one whose digit sum is divisible by 11.

4. (a)  Arrange 7 stars in the 16 places of a 4 x 4 array, so that no 2 rows and 2 columns contain all the stars.

(b)  Prove this is not possible for <7 stars.

5. (a)  Given a quadruple (a, b, c, d) of positive reals, transform to the new quadruple (ab, bc, cd, da). Repeat arbitarily many times. Prove that you can never return to the original quadruple unless a=b=c=d=1.

(b)  Given n a power of 2, and an n-tuple (a₁, a₂, ... , a_n) transform to a new n-tuple (a₁a₂, a₂a₃, ... , a_n-1a_n, a_na₁). If all the members of the original n-tuple are 1 or -1, prove that with sufficiently many repetitions you obtain all 1s.

6. (a)  A and B move clockwise with equal angular speed along circles center P and Q respectively. C moves continuously so that AB=BC=CA. Establish C's locus and speed.

*(b)  ABC is an equilateral triangle and P satisfies AP=2, BP=3. Establish the maximum possible value of CP.

7.  Given an m x n array of real numbers. You may change the sign of all numbers in a row or of all numbers in a column. Prove that by repeated changes you can obtain an array with all row and column sums non-negative.

8.  Given n<1 points, some pairs joined by an edge (an edge never joins a point to itself). Given any two distinct points you can reach one from the other in just one way by moving along edges. Prove that there are n-1 edges.

9.  Given any natural numbers m, n and k. Prove that we can always find relatively prime natural numbers r and s such that rm+sn is a multiple of k.

10.  A and B play the following game with N counters. A divides the counters into 2 piles, each with at least 2 counters. Then B divides each pile into 2 piles, each with at least one counter. B then takes 2 piles according to a rule which both of them know, and A takes the remaining 2 piles. Both A and B make their choices in order to end up with as many counters as possible. There are 3 possibilities for the rule:

  R1  B takes the biggest heap (or one of them if there is more than one) and the smallest heap (or one of them if there is more than one).

  R2  B takes the two middling heaps (the two heaps that A would take under R1).

  R3  B has the choice of taking either the biggest and smallest, or the two middling heaps.

For each rule, how many counters will A get if both players play optimally?

11.  Given three arbitary infinite sequences of natural numbers, prove that we can find unequal natural numbers m, n such that for each sequence the mth member is not less than the nth member.

*12.  120 unit squares are arbitarily arranged in a 20 x 25 rectangle (both position and orientation is arbitary). Prove that it is always possible to place a circle of unit diameter inside the rectangle without intersecting any of the squares.

Solutions

Problem 1

Given 12 vertices and 16 edges arranged as follows:

Draw any curve which does not pass through any vertex. Prove that the curve cannot intersect each edge just once. Intersection means that the curve crosses the edge from one side to the other. For example, a circle which had one of the edges as tangent would not intersect that edge. 

Solution

A-----B-----C
|     |     |
D--E--F--G--H
|  |     |  |
I--J-----K--L

If a curve intersects the boundary of a region R (such as ABFED), then it moves from inside R to outside or vice versa. Hence if R has an odd number of edges (like ABFED) then a curve intersecting all of them just once must have one endpoint inside R. But there are four such regions (ABFED, BCHGF, EFGKJ and the outside of ABCHLKJID) and only two endpoints.

Note that we can easily intersect all edges but one. For example, start above AB, then cross successively AB, AD, DI, DE, EF, EJ, IJ, JK, GK, KL, HL, GH, CH, BC, FG.

Problem 2

Given a rectangle ABCD with AC length e and four circles centers A, B, C, D and radii a, b, c, d respectively, satisfying a+c=b+d<e. Prove you can inscribe a circle inside the quadrilateral whose sides are the two outer common tangents to the circles center A and C, and the two outer common tangents to the circles center B and D.

Solution

Let O be the center of the rectangle. Let r = (a+c)/2 = (b+d)/2. The required circle has center O, radius r. Let an outer common tangent touch the circle center A at W, and the circle center C at X. Let P be the midpoint of WX, then OP is parallel to AW and CX and has length r, hence the circle center O touches AW at P. Similarly for the other common tangents. Problem 3

Prove that any 39 successive natural numbers include at least one whose digit sum is divisible by 11.

Solution

Let n be the smallest number in the sequence and m the smallest with last digit 0. m and m+10 have different digit sums unless (possibly) the penultimate digit of m is 9, but in that case m+10 and m+20 have different digit sums. So two of m, m+10, m+20 are sure to have different digit sums. Hence at least one has a digit sum not congruent to 1 mod 11. Adding the appropriate final digit gives a number whose digit sum is divisible by 11. This number lies in the range m to m+29 and m<=n+9. Hence the result. n=999981 shows it is best possible.

Problem 4

(a)  Arrange 7 stars in the 16 places of a 4 x 4 array, so that no 2 rows and 2 columns contain all the stars.

(b)  Prove this is not possible for <7 stars.

Solution

(a)

**..
*.*.
.**.
...*

Pick any two rows. The unpicked stars lie in different columns.

(b)  If there is a row with at least 3 stars, pick it. That leaves at most 3 stars, pick the row for one and the columns for the others. Now assume no row has more than 2 stars. 6 stars in <6 rows, so we can pick a row with 2 stars. That leaves 4 stars in 3 rows, so we can pick another row with 2 stars. That leaves 2 stars. Pick their columns. [This glosses over the case of <6 stars. In this case we can add extra stars to make the number up to 6. Now the procedure above deals with the original stars and the extra stars, and in particular with the original stars.] 

Problem 5

(a)  Given a quadruple (a, b, c, d) of positive reals, transform to the new quadruple (ab, bc, cd, da). Repeat arbitarily many times. Prove that you can never return to the original quadruple unless a=b=c=d=1.

(b)  Given n a power of 2, and an n-tuple (a₁, a₂, ... , a_n) transform to a new n-tuple (a₁a₂, a₂a₃, ... , a_n-1a_n, a_na₁). If all the members of the original n-tuple are 1 or -1, prove that with sufficiently many repetitions you obtain all 1s.

Solution

(a)  Let Q₀ be the original quadruple (a, b, c, d) and Q_n the quadruple after n transformations. If abcd>1, then the products form a strictly increasing sequence, so return is impossible. Similarly if abcd<1. So we must have abcd=1.

Let the largest of the four values of a quadruple Q be M(Q). If a member of Q₁ is not 1, then M(Q₁)>1. Q₃ consists of the elements of Q₁ squared and permuted, so M(Q₃) = M(Q₁)². Hence the sequence M(Q₁), M(Q₃), M(Q₅), ... increases without limit. This means no return is possible, because a return would lead to the values cycling.

(b)  After r<n transformations, the first number of the n-tuple is the product a₁^(r|0)a₂^(r|1) ... a_r+1^(r|r), where (r|i) denotes the binomial coefficient. [This is an easy induction.] Hence after n=2^k transformations it is a₁² times the product a₂^(n|1) ... a_n^(n|n-1). So it is sufficient to prove that (n|i) is even for n a power of 2 and 0<i<n. But observe that (n|i) = (n-1|i) n/(n-i) and n is divisible by a higher power of 2 than n-i.

Problem 6

(a)  A and B move clockwise with equal angular speed along circles center P and Q respectively. C moves continuously so that AB=BC=CA. Establish C's locus and speed.

*(b)  ABC is an equilateral triangle and P satisfies AP=2, BP=3. Establish the maximum possible value of CP.

Solution

(a)  Represent A, B as complex numbers z₁ + w₁e^it, z₂ + w₂e^it. Then C is (z₁ + w₁e^it) + (z₂ + w₂e^it - z₁ - w₁e^it) e^{i π/3}, which is also of the form z + w e^it.

However, there is one subtlety. There are actually two circles possible for C depending on which side of AB we place it. The continuity requirement means that C is normally confined to one of the circles. However, if A and B ever coincide then C may be able to switch to the other circle.

If we regard "moves continuously" as allowing a discontinuous velocity, then a switch is always possible (provided A and B coincide).

(b)  Answer: 5.

P must be the opposite side of AB to C (or we could increase CP, whilst keeping AP and BP the same, by reflecting in AB). Similarly it must be on the same side of AC as B, and on the same side of BC as A. For any P in this region the quadrilateral APBC is convex and hence satisfies Ptolemy's inequality CP·AB ≤ AP·BC + BP·AC, with equality iff APBC is cyclic. But AB = BC = CA, so we have CP ≤ AP + BP = 5 with equality iff P lies on the arc AB of the circle ABC. Note that there is just one such point, because the locus of P such that BP=1.5 AP is a circle which cuts the arc just once.

Ptolemy's inequality for 4 points A, B, C, D: AB·CD + BC·AD ≥ AC·BD with equality iff ABCD is a cyclic quadrilateral (meaning A, B, C, D lie on a circle in that order).

Proof

Take E inside ABCD such that ∠DAE = ∠CAB and ∠ADE = ∠ACB. Then ADE and ACB are similar, so DE/CB = AD/AC and hence BC·AD = AC·DE. It also follows that AE/AB = AD/AC. But we also have ∠EAB = ∠DAC and hence AEB and ADC are also similar. So EB/AB = DC/AC, and hence AB·CD = AC·EB. Adding, we have: AB·CD + BC·AD = AC(BE + ED) ≥ AC·BD with equality iff E lies on BD, or equivalently ABCD is cyclic.

This glosses over one point. It only follows that ∠EAB = ∠DAC if ABCD is convex. For the convex case, we have that ∠EAB = ∠CAB + ∠EAC and ∠DAC = ∠DAE + ∠EAC, or ∠EAB = ∠CAB - ∠EAC and ∠DAC = ∠DAE - ∠EAC. Either way ∠EAB = ∠DAC. But in the non-convex case, we can have ∠EAB = ∠CAB + ∠EAC and ∠DAC = ∠DAE - ∠EAC (or - ... +) and hence the angles ∠EAB and ∠DAC are not necessarily equal.

Problem 7

Given an m x n array of real numbers. You may change the sign of all numbers in a row or of all numbers in a column. Prove that by repeated changes you can obtain an array with all row and column sums non-negative. 

Solution

The array has mn entries. Call an array that can be obtained by repeated changes a reachable array. A reachable array differs from the original only in that some or all of the signs of its mn entries may be different. There are at most 2 possibilities for each sign and hence at most 2^mn different reachable arrays. For each reachable array calculate the sum of all its entries. Take the reachable array with the largest such sum. It must have non-negative row and column sums, because if any such sum was negative, changing the sign of that row or column would give another reachable array with strictly greater total sum.

 Problem 8

Given n<1 points, some pairs joined by an edge (an edge never joins a point to itself). Given any two distinct points you can reach one from the other in just one way by moving along edges. Prove that there are n-1 edges.

Solution

Every point must have at least one edge. We show that there is a point with just one edge. Suppose the contrary, that every point has at least two edges. We now construct a path in which the same edge or point never appears twice. Starting from any point b, move along an edge to c. c is not already on the path, because otherwise the edge would join b to itself. Now suppose we have reached a point x not previously on the path. x has at least two edges, so it must have another one besides the one we used to reach it. Suppose this joins x to y. If y is already on the path, then we have two distinct ways of moving along edges from x to y: directly, or by backtracking along the path from x to y. But this is impossible, so y is not already on the path and we may extend the path to it. But this procedure allows us to construct a path containing more than the n distinct points available. Contradiction.

The result is now easy. Induction on n. Take a point with just one edge. Remove it and the edge. Then the remaining n-1 points satisfy the premise and hence have just n-2 edges.

Problem 9

Given any natural numbers m, n and k. Prove that we can always find relatively prime natural numbers r and s such that rm+sn is a multiple of k.

Solution

Care is needed. Although easy, this is more awkward than it looks.

Let d=(m,n), the greatest common divisor of m and n. Let r=n/d, s=nhk - m/d, where h is any integer sufficiently large to ensure that s>0. Now rm+sn = mn/d + nnhk - mn/d = nnhk, which is a multiple of k. If e divides r, then it also divides rdhk = nhk. So if e divides r and s, then it also divides s - nhk = -m/d. But n/d and m/d are relatively prime, so e must be 1. Hence r and s are relatively prime. 

Problem 10

A and B play the following game with N counters. A divides the counters into 2 piles, each with at least 2 counters. Then B divides each pile into 2 piles, each with at least one counter. B then takes 2 piles according to a rule which both of them know, and A takes the remaining 2 piles. Both A and B make their choices in order to end up with as many counters as possible. There are 3 possibilities for the rule:

  R1  B takes the biggest heap (or one of them if there is more than one) and the smallest heap (or one of them if there is more than one).

  R2  B takes the two middling heaps (the two heaps that A would take under R1).

  R3  B has the choice of taking either the biggest and smallest, or the two middling heaps.

For each rule, how many counters will A get if both players play optimally?

Solution

Answers: [N/2], [(N+1)/2], [N/2].

Suppose A leaves piles n, m with n≤m.

Under R1, B can certainly secure m by dividing the larger pile into 1 and m-1. He cannot do better, because if b is the biggest of the 4 piles, then the smallest is at most m-b. Hence A's best strategy is to leave [N/2], [(N+1)/2].

Under R2, if A leaves a=2, b=N-2, then B cannot do better than [N/2], because if he divides the larger pile into a,b with a≤b, then he takes a+1. A cannot do better, because if he leaves a,b with 3≤a≤b, then B can divide to leave 1, a-1, [b/2], [(b+1)/2]. Now if a-1≥[(b+1)/2], then B takes b≥[(N+1)/2]. If a-1<[(b+1)/2], then B takes a-1+[b/2]. But a-1≥2 and [b/2]≥[(b+1)/2]-1, so a-1+[b/2]≥1+[(b+1)/2], or B takes at least as many as A, so B takes at least [(N+1)/2].

Under R3, A's best strategy is to divide into [N/2],[(N+1)/2]. We have already shown that B can secure [(N+1)/2] and no more by following R1. He cannot do better under R2, for if he divides so that the biggest pile comes from [N/2], then the smallest does too and so he gets [(N+1)/2]. If he divides so that the biggest and smallest piles come from [(N+1)/2], then he gets only [N/2]. But one of these must apply, because if he divided so that the smaller from [N/2] was smaller than the smaller from [(N+1)/2], and the bigger from [N/2] was smaller than the bigger from [(N+1)/2], then [N/2] would be at least 2 less than [(N+1)/2] (which it is not).

Problem 11

Given three arbitary infinite sequences of natural numbers, prove that we can find unequal natural numbers m, n such that for each sequence the mth member is not less than the nth member. 

Solution

Given any infinite sequence of natural numbers we can find a non-decreasing subsequence (proof below). So suppose the three sequences are a_i, b_i, and c_i. Take a non-decreasing subsequence of a_i. Suppose it is a_i1, a_i2, a_i3, ... . Now consider the infinite sequence b_i1, b_i2, ... . It must have a non-decreasing subsequence. Suppose it is b_j1, b_j2, ... . Now consider the infinite sequence c_j1, c_j2, ... . It must have a non-decreasing subsequence c_k1, c_k2, ... . Each of the three sub-sequences a_k1, a_k2, ... , b_k1, b_k2, ... , c_k1, c_k2, ... is non-decreasing. So we may take, for example, m=k2 and n=k1.

[Proof that any infinite sequence of natural numbers has a non-decreasing subsequence: if the original sequence is unbounded, then we can take a strictly increasing subsequence. If not, then since there are only finitely many possible numbers not exceeding the bound, at least one of them must occur infinitely often.] 

Problem 12

120 unit squares are arbitarily arranged in a 20 x 25 rectangle (both position and orientation is arbitary). Prove that it is always possible to place a circle of unit diameter inside the rectangle without intersecting any of the squares. 

Solution

If a circle with unit diameter intersects a unit square, then its center must lie inside an area 3+π/4, namely an oval centered on the square and comprising: the original square, area 1; four 1 x 1/2 rectangles on the sides, total area 2; and four quarter circles at the corners, total area π/4. So if it does not intersect any of the 120 unit squares, then it must avoid ovals with a total area of 120 x (3+π/4) = 454.2. Of course, for many arrangements of the squares, these ovals might overlap substantially, but the worst case would be no overlap.

The circle is also required to lie inside the rectangle, so its center must lie outside a strip 1/2 wide around the edge, and hence inside an inner 19 x 24 rectangle, area 456. The total area of ovals is less, so they cannot cover it completely and it must be possible to place a circle as required.