7th All Soviet Union Mathematical Olympiad Problems 1973

7th All Soviet Union Mathematical Olympiad Problems 1973

1.  You are given 14 coins. It is known that genuine coins all have the same weight and that fake coins all have the same weight, but weigh less than genuine coins. You suspect that 7 particular coins are genuine and the other 7 fake. Given a balance, how can you prove this in three weighings (assuming that you turn out to be correct)?

2.  Prove that a 9 digit decimal number whose digits are all different, which does not end with 5 and or contain a 0, cannot be a square.

3.  Given n > 4 points, show that you can place an arrow between each pair of points, so that given any point you can reach any other point by travelling along either one or two arrows in the direction of the arrow.

4.  OA and OB are tangent to a circle at A and B. The line parallel to OB through A meets the circle again at C. The line OC meets the circle again at E. The ray AE meets the line OB at K. Prove that K is the midpoint of OB.

5.  p(x) = ax² + bx + c is a real quadratic such that |p(x)| ≤ 1 for all |x| ≤ 1. Prove that |cx² + bx + a| ≤ 2 for |x| ≤ 1.

6.  Players numbered 1 to 1024 play in a knock-out tournament. There ar no draws, the winner of a match goes through to the next round and the loser is knocked-out, so that there are 512 matches in the first round, 256 in the second and so on. If m plays n and m < n-2 then m always wins. What is the largest possible number for the winner?

7.  Define p(x) = ax² + bx + c. If p(x) = x has no real roots, prove that p( p(x) ) = 0 has no real roots.

8.  At time 1, n unit squares of an infinite sheet of paper ruled in squares are painted black, the rest remain white. At time k+1, the color of each square is changed to the color held at time k by a majority of the following three squares: the square itself, its northern neighbour and its eastern neighbour. Prove that all the squares are white at time n+1.

9.  ABC is an acute-angled triangle. D is the reflection of A in BC, E is the reflection of B in AC, and F is the reflection of C in AB. Show that the circumcircles of DBC, ECA, FAB meet at a point and that the lines AD, BE, CF meet at a point.

10.  n people are all strangers. Show that you can always introduce some of them to each other, so that afterwards each person has met a different number of the others. [problem: this is false as stated. Each person must have 0, 1, ... or n-1 meetings,so all these numbers must be used. But if one person has met no one, then another cannot have met everyone.]

11.  A king moves on an 8 x 8 chessboard. He can move one square at a time, diagonally or orthogonally (so away from the borders he can move to any of eight squares). He makes a complete circuit of the board, starting and finishing on the same square and visiting every other square just once. His trajectory is drawn by joining the center of the squares he moves to and from for each move. The trajectory does not intersect itself. Show that he makes at least 28 moves parallel to the sides of the board (the others being diagonal) and that a circuit is possible with exactly 28 moves parallel to the sides of the board. If the board has side length 8, what is the maximum and minimum possible length for such a trajectory.

12.  A triangle has area 1, and sides a ≥ b ≥ c. Prove that b² ≥ 2.

13.  A convex n-gon has no two sides parallel. Given a point P inside the n-gon show that there are at most n lines through P which bisect the area of the n-gon.

14.  a, b, c, d, e are positive reals. Show that (a + b + c + d + e)² ≥ 4(ab + bc + cd + de + ea).

15.  Given 4 points which do not lie in a plane, how many parallelepipeds have all 4 points as vertices? 

Solutions

Problem 1

You are given 14 coins. It is known that genuine coins all have the same weight and that fake coins all have the same weight, but weigh less than genuine coins. You suspect that 7 particular coins are genuine and the other 7 fake. Given a balance, how can you prove this in three weighings (assuming that you turn out to be correct)?

Solution

Let the coins you suspect to be genuine be G₁, G₂, ... , G₇, and the suspected fakes by F₁, F₂, ... , F₇. First weigh F₁ against G₁. Assuming F₁ weighs less, you have proved that F₁ is fake and G₁ genuine. Second, weigh F₁, G₂, G₃ against G₁, F₂, F₃. Assuming the first three weigh more you have proved that they include more genuine coins than the second three. But the second three includes one genuine coin (G₁) and the first three includes one fake (F₁), so you have proved that G₂ and G₃ are genuine and F₂ and F₃ fake. Finally, weigh F₁, F₂, F₃, G₄, G₅, G₆, G₇ against F₄, F₅, F₆, F₇, G₁, G₂, G₃. Assuming the first group weighs more it must include more genuine coins and hence just four genuine coins. Similarly, the second group must include four fakes. So you have proved the identity of the remaining coins.

Annotation:  

• The 1st All Russian Mathematical Olympiad was in 1961. In 1967 it was renamed the All Soviet Union Mathematical Olympiad and the numbering restarted, hence 1st ASU 1967. In 1992 it was renamed again as the Commonwealth of Independent States MO and the numbering restarted. But it was not held again. So 1992 was the last year. 
• The problems were intended for schoolchildren aged 14-17. Each year there were two papers of 3 or 4 questions each at three different levels (according to form, roughly ages, 14, 15, 16), but with some overlap between the levels. I can usually do the the easier questions as fast as I can write down the answer, which is almost never true for modern IMO questions. The hardest questions are comparable to the IMO.  
• The years up to 1987 are apparently published in Russian with solutions in Vasilev N B, Egorov A A, The problems of the All-Soviet-Union mathematical competitions, Moscow, Nauka 1988. ISBN 5020137308. Unfortunately, I have not yet been able to get hold of a copy. However, Vladimir Pertsel published a large text file many years ago on the internet containing an English translation of the problems only. Unfortunately, some of the problems were rather hard to understand and I have substantially changed the wording here.
  The years from 1989 to 1992 were published in English with solutions by Arkadii Slinko, USSR Mathematical Olympiads 1989-1992, Australian Mathematical Trust, 1997, ISBN 0646336185. The AMT publishes a series of olympiad problem books, which can be ordered by email.