5th All Soviet Union Mathematical Olympiad 1971 Problems & Solutions



1.  Prove that we can find a number divisible by 2n whose decimal representation uses only the digits 1 and 2.
2.  (1) A1A2A3 is a triangle. Points B1, B2, B3 are chosen on A1A2, A2A3, A3A1 respectively and points D1, D2 D3 on A3A1, A1A2, A2A3 respectively, so that if parallelograms AiBiCiDi are formed, then the lines AiCi concur. Show that A1B1·A2B2·A3B3 = A1D1·A2D2·A3D3. (2) A1A2 ... An is a convex polygon. Points Bi are chosen on AiAi+1 (where we take An+1 to mean A1), and points Di on Ai-1Ai (where we take A0 to mean An) such that if parallelograms AiBiCiDi are formed, then the n lines AiCi concur. Show that ∏ AiBi = ∏ AiDi.
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 R2.
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)2 < (A - a)(Ba - Ab). Show that the quadratics x2 + ax + b = 0 and x2 + 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) = x2 + xy + y2. 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) = x2 + axy + y2 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 2n 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 2n. True for n = 1: take N = 2. Suppose it is true for n. If 2n+1 divides N, then since 2n+1 divides 2 x 10n it also divides N' obtained from N by placing a 2 in front of it. If 2n+1 does not divide N, then N = 2n x odd and 10n = 2n x odd, so N + 10n (in other words the n+1 digit number obtained by placing a 1 in front of N) is divisible by 2n+1

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.



Fun Math Games for Kids

 
Return to top of page Copyright © 2010 Copyright 2010 (C) CoolMath4Kids - Cool Math 4 Kids - Cool Math Games 4 Kids - Coolmath4kids Bloxorz - Coolmath-4kids - Math games, Fun Math Lessons, Puzzles and Brain Benders, Flash Cards for Addition, Subtration, Multiplication, Fraction, Division - Cool Math 4 Kids - Math Games, Math Puzzles, Math Lessons - Cool Math 4 Kids Math Lessones - 4KidsMathGames - CoolMath Games4Kids coolmath4kids.info. All right reseved.