These problems are intended for students studying upper level secondary mathematics. Nearly all of them are new and original, proposed by Russian teachers especially for the Olympiad. One bacterium divides into two new ones. Then every second, one of the bacteria also splits in two, and soon there are 1995 bacteria. Prove that one of them lives for at least 995 seconds without any division. A sequence of natural numbers (Xn ) is formed in the following way:``` X = 19 X = 95 X = LCM ( X , X ) + X 1 2 n+2 n+1 n n ``` Find GCD ( X1995 , X1996 ).    [LCM - least common multiple     GCD - greatest common divisor] In a country there live 'knights' and 'knaves.' The 'knaves' always lie and the 'knights' always tell the truth - unless they make a mistake. 1995 knights and knaves are sitting around a table. Each says that he is sitting between a knight and a knave, but two knights are mistaken. How many knaves are seated at the table? Divide a square into 7 polygons such that any two like polygons will have no common edge, and any two that are not the same shape will have a common edge. (For any polygon there must exist another with the same shape.) The Mad Tea-Party: The Hatter, the March Hare, and the Dormouse sit at a round table. On the table are 12 cups full of tea. Every day at six o'clock, each of the table-companions moves two places to his right or left (if the place is free) and drinks all the tea at that place if there is any in his cup. After the place-changing, Alice fills one of the cups. Prove that Alice can keep at least 6 cups full. Prove that there are infinitely many integers that are not equal to the sum of two squares of integers, but that are equal to the sum of three cubes of integers. Dazzy fishes for more than a week. He experiences three different levels of success. On a good day he catches 9 fish. On a bad day he catches only 5 fish. On other days he catches 7 fish. In all, Dazzy catches 53 fish. How many bad days does he have? Is it possible to put the numbers from 1 to 64 in the squares of a chess board in such a way that the sum of the numbers in any three squares arranged in the following pattern will be odd? ``` --- | | ------- | | | ------- ``` Tyrannosaurus Rex and Tyrannosaurus Glipp are playing a game. Each player in turn puts an X or an O in any free square of an 11x11 checkerboard. The winner of the game is the player who first puts three equal marks in a line, horizontally, vertically, or diagonally: ``` XXX or O X O or X O X ``` Tyrannosaurus Rex starts. In an errorless game, who wins? Ann, Ben, Can, and Den think of one natural number. Ann says it consists of two digits. Ben says it is a divisor of 150. Can says it is not 150. Den says it is divisible by 25. Which one of them is not telling the truth? All the digits from 1 to 9 are written on a blackboard. Pete erases some of the digits and writes the product of the numbers he has erased. In addition, he can write new digits. After some of these operations only one digit remains on the blackboard. Prove that the remaining digit is 0. Winnie-the-Pooh and Piglet are celebrating their common birthday. Every guest gives them a can of honey and a can of condensed milk. Pooh leaves some of the cans for Piglet, and others he keeps for himself. When Pooh has eaten all of his honey, the number of full cans he has left is equal to the total number of Piglet's cans. Piglet has 10 cans of milk. How many cans of honey did Pooh eat? In this game, there are 100 coins on one scale, and 200 coins on another scale. Each of two players in turn takes one or more of the coins from one of the scales. The player who makes the number of coins on the two scales equal loses. Scrooge and Glomgold play a game. Scrooge makes the first move. In an errorless game, who wins? The calculator 'ComeOn-96' has the buttons '+1', '-1', '+4', and '-4'. Whenever the result of an operation is divisable by 4, the calculator explodes! ;-) Begin with 1 on the calculator, and prove that it is impossible to arrive at an answer of 2 when using exactly 1996 operations. In a tribe of cannibals there are 20 persons. Each person likes some of his or her fellow-tribesmen and does not like others. Each day all of the people who are liked by more than half the tribe become dinner. Prove that on the 10th day after the first cannibal has been eaten, because no person is liked by more than half of the other cannibals there is no dinner. Prove that it is possible to write all 10-digit numbers that consist of only ones and twos in a circle in such a way that every two neighbouring numbers will differ by only one digit (e.g. 22211 and 22111, or 12121 and 12221). Let S be a square, Q be the perimeter of the square, and P be the perimeter of a quadrilateral T inscribed within S such that each of its vertices lies on a different edge of S. What is the smallest possible ratio of P to Q? What is the greatest number of kings that can be placed on a chess board such that every king will win only one square or no square? (A king wins all eight neighbouring squares, as shown below.) ``` - - - |*|*|*| - - - |*|K|*| - - - |*|*|*| - - - ``` All the natural numbers from 2 to 3500 are written on the blackboard. Players in turn can erase both any non-prime number and all the numbers that are not co-prime to it. A player wins if, after his turn, only prime numbers remain on the board, so that another player cannot take a turn. T-Rex and T-Glipp play a game. Who will win if T-Rex begins and neither makes a mistake? In the country of OneWay, some cities are connected by roads. Cars may drive in only one direction on roads, but pedestrians can go in both directions. From Return-City one can go to any other city by car, but in only one direction. If it is possible to leave a city and return to the same city by car, the car will go through Return-City. Two strangers leave GetOff-City from different sides. They are both pedestrians and neither can visit any city more than once. Some time later, they meet again. Prove that one of them must have visited Return-City.