## My problems from Tournament of Towns

As Tournament of Towns does not want to find "absolute winner" it gives problems which are kind of unpredictable. They can be easy or hard, but they are always interesting. That's why I prefer to present my problems here.

Spring 1994, O Level, Seniors, problem 2.
The sequence of positive integers a1, a2, ... is such that for each n = 1, 2, ... the quadratic equation an+2x2 + an+1x + an has a real root. Can the sequence consist of
(a) 10 terms,
(b) an infinite number of terms?
[Points: (a) 2, (b) 3.]

Autumn 1994, O Level, Juniors, problem 4.
There are 20 pupils in the Backwords school. Any two of them have a common grandfather. Prove that there exist 14 pupils all of whom have a common grandfather.
[5 points]

Spring 1995, A Level, Juniors, problem 5.
Four equal right-angled triangles are given. We are allowed to cut any triangle into two new ones along the altitude dropped on to the hypotenuse. This operation may be repeated with any of the triangles from the new set. Prove that after any number of such operations there will be congruent triangles among those obtained.
[8 points]

Spring 1995, A Level, Seniors, problem 2.
For what values of n is it possible to paint the edges of a prism whose base is n-gon so that there are edges of all three colours at each vertex and all the faces (including the upper and lower bases) have edges of all three colours?
[4 points]

Autumn 1995, A Level, Juniors, problem 4.
Some points with integer coordinates in the plane are marked. It is known that no four of them lie on a circle. Show that there exist a circle of radius 1995 without any marked point inside.
[6 points]

Spring 1995, A Level, Seniors, problem 6.
A game is played on a 1×1000 board. There are n chips, all of which are initially in a box near the board. Two players move in turn. The first may choose 17 chips or less, from either on or off the board. She then puts them into unoccupied cells on the board so that there is no more than one chip in each of the cells. The second player may take off the board any number of chips occupying consecutive cells and put them back in the box. The first player wins if she can put all n chips on the board so that they occupy consecutive cells.
(a) Show that she can win if n=98.
(b) For what maximal value of n can she win?
[Points: (a) 4, (b) 5.]

Autumn 1995, O Level, Seniors, problem 3.
A rectangle with sides of lengths a and b (a>b) is cut into rightangled triangles so that any two of these triangles either have a common side, a common vertex or no common points. Morover, any common side of two triangles is a leg of one of them and the hypotenuse of the other. Prove that a ≥ 2b.
[5 points]

Autumn 1995, A Level, Seniors, problem 6.
Does ther exist an increasing arithmetic progression of
(a) 11
(b) 10000
(b) infinitely many
positive integers such that the sums of their digits in base 10 also form an increasing arithmetic progression? [Points: (a) 3, (b) 4, (c) 2.]

Autumn 1996, O Level, Juniors, problem 4.
(a) A square is cut into right triangles with legs of lengths 3 and 4. Prove that the total number of the triangles is even.
(b) A rectangle is cut into right triangles with legs of lengths 1 and 2. Prove that the total number of the triangles is even.
[Points: (a) 2, (b) 4.]

Autumn 1997, A Level, Juniors, problem 3.
Initially there is a checker on every square of a 1×n board. The first move consists of moving a checker to an adjacent square thus creating a stack of two checkers. Then each time when making a move, one can choose a stack and move it in either direction as many squares on the board as there are checkers in the stack. If after the move the stack lands on a non-empty square, it is placed on top of the stack which is already there. Prove that it is possible to stack all the checkers on one square in n–1 moves.
[5 points]

Autumn 1997, A Level, Juniors, problem 5.
Each face of a cube is of the same size as each square of a chessboard. The cube is coloured black and white, placed on one of the squares of the chessboard and rolled so that each square of the chessboard is visited exactly once. Can this be done in such a way that the colour of the visited square and the colour of the bottom face of the cube are always the same?
[5 points]

Autumn 1997, A Level, Juniors, problem 7.
You are given a balance and one copy of each ten weights of 1, 2, 4, 16, 32, 64, 128, 256 and 512 grams. An object weighing M grams, where M is a positive integer, is put on one of the pans and may be balanced in different ways by placing various combinations of the given weights on either pan of the balance. (b) prove that no object can be balanced in more then 89 ways.
(b) Find a value of M such that an object weighing M grams can be balanced in 89 ways.
(with A.Kulakov)
[Points: (a) 5, (b) 4.]

Spring 1998, O Level, Juniors, problem 1.
Anya, Borya, and Vasya listed words that could be formed from a given set of letters. They each listed a different number of words: Anya listed the most, Vasya the least. They were awarded points as follows. Each word listed by only one of them scored 2 points for the child. Each word listed by two of them scored 1 point for each of these two children. Words listed by all three of them scored 0 points. Is it possible that Vasya got the highest score, and Anya the lowest?
[3 points]

Spring 1998, O Level, Juniors, problem 5.
Pinoccio claims that he has isoceles triangle which he can divide into three triangles, any two of which can be put together to form a new isoceles triangle. Can Pinoccio's words be truthful?
[5 points]

Spring 1998, O Level, Seniors, problem 3.
What is the maximum number of colours that can be used to paint an 8×8 chessboard so that every square is painted in a single colour, and is adjacent, horizontally, vertically but not diagonally, to at least two other squares of its own colour?
[3 points]

Spring 1998, A Level, Juniors, problem 6.
10 people are sitting at a round table. There are some nuts in front of each of them, 100 nuts altogether. After a certain signal each person passes some of his nuts to the person sitting to his right. If he has an even number of nuts, he passes half of them; otherwise he passes one nut plus half of the remaining nuts. This procedure is repeated over and over again. Prove that eventually everyone will have exactly 10 nuts.
[8 points]

Spring 1998, A Level, Seniors, problem 3.
(a) The numbers 1, 2, 4, 8, 16, 32, 64, 128 are written on a blackboard. We are allowed to erase any two numbers and write their difference instead (this is always a non-negative number). After this procedure has been repeated seven times, only a single number will remain. Could this number be 97?
(b) The numbers 1, 2, 22, 23, ..., 210. are written on a blackboard. We are allowed to erase any two numbers and write their difference instead (this is always a non-negative number). After this procedure has been repeated seven times, only a single number will remain. What values could this number have?
[Points: (a) 2, (b) 3.]

Spring 1998, A Level, Seniors, problem 5.
A “labyrinth” is an 8×8 chessboard with walls between some neighboring squares. If a rook can traverse the entire board without jumping over the walls, the labyrinth is "good"; otherwise, it is "bad". Are there more good labyrinths or bad labyrinths?
[6 points]

Autumn 1998, O Level, Juniors, problem 4.
Twelve candidates for mayor participate in a TV talk show. At some point a candidate said: “One lie has been told.” Another said: "Now two lies has been told”. “Now three lies,” said a third. This continued until the twelfth said "Now twelve lies has been told”. At this point the moderator ended the discussion. It turned out that at least one of the candidates correctly stated the number of lies told before he made the claim. How many lies were actually told by the candidates?
[4 points]

Autumn 1998, A Level, Juniors, problem 1.
Prove that for any two positive integers a and b the equation LCM(a, a+5) = LCM(b, b+5) implyes a = b.
[4 points]

Autumn 1998, A Level, Juniors, problem 2.
John and Mary each have a white 8×8 square divided into 1×1 cells. They have painted an equal number of cells on their respective squares in blue. Prove that one can cut up each of the two squares into 2×1 dominoes so that it is possible to reassemble John's dominos, as well as Mary's, into two new squares with the same pattern of blue cells.
[4 points]

Autumn 1998, A Level, Juniors, problem 4.
All the diagonals of a regular 25-gon are drawn. Prove that no 9 of the diagonals pass through one interior point of the 25-gone.
[6 points]

Autumn 1998, A Level, Juniors, problem 4.
A gang of robbers took away a bag of coins from a merchant. Each coin is worth an integer number of pennies. It is known that if any single coin is removed from the bag, then the remaining coins can be divided fairly among the robbers (that is, they all get coins with the same total value in pennies). Prove that after one coin is removed, the number of the remaining coins is divisible by the number of robbers.
[6 points]

Autumn 1998, A Level, Seniors, problem 1.
(a) Prove that for any two positive integers a and b the equation LCM(a, a+5) = LCM(b, b+5) implyes a = b.
(a) Is it possible that LCM(a, b) = LCM(a+c, b+c) for positive integers a, b and c?
[Points: (a) 2, (b) 3.]

Autumn 1998, A Level, Seniors, problem 4.
Twelve places had been arranged at a round table for members of the Jury, with a name tag at each place. Professor K. being absent-minded instead of occupying his place, sits down at the next place (clockwise). Each of the other Juru members in turn either occupies the place assigned to this member or, if it has been already occupied, sits down at the first free place in the clockwise order. The resulting seating arrangement depends on the order in which the Jury members come to the table. How many differnet seating arrangements of this kind are possible?
[6 points]

Spring 1999, A Level, Seniors, problem 1.
A convex polyhedron body drifts in a sea. Can it happen that 90% of its volume is below the water level, while more than half of its surface area is above the water level?
[4 points]

Spring 1999, A Level, Seniors, problem 6.
A rook is allowed to move one cell either horizontally or vertiacally. After 64 moves the rook visited all the cells of the 8×8 chessboard and returned back to the initiall cell. Prove that the number of moves in the vertical direction and the number of moves in the horizontal direction cannot be equal.
[9 points]

Autumn 1999, O Level, Juniors, problem 1.
A right-angled triangle made of paper is folded along a straight line so that the vertex at the right angle coincides with one of the other vertices of the triangle and a quadrilateral is obtained.
(a) What is the ratio into which the diagonals of this quadrilateral divide each other?
(b) This quadrilateral is cut along its longest diagonal. Find the area of the smallest piece of paper thus obtained if the area of the original triangle is 1.
[Points: (a) 2, (b) 2.]

Autumn 1999, O Level, Juniors, problem 5.
Is it possible to divide a 6×6 chessboard into 18 rectangles, each either 1×2 or 2×1, and to draw exactly one diagonal on each rectangle such that no two of these diagonals have a common endpoint?
[4 points]

Autumn 1999, O Level, Seniors, problem 5.
Is it possible to divide a 8×8 chessboard into 32 rectangles, each either 1×2 or 2×1, and to draw exactly one diagonal on each rectangle such that no two of these diagonals have a common endpoint?
[4 points]

Autumn 1999, O Level, Seniors, problem 1.
The incenter of the triangle is joined by three segments to the three vertices of the triangle, thereby dividing it into three smaller triangles. If one of these three triangles is similar to the original triangle, find its angles.
[4 points]

Autumn 1999, A Level, Juniors, problem 1.
n consequtive positive integers are put down in a row (not necessarily in order) so that the sum of any three successive integers in the row is divisible by the leftmost number in the triple. What is the largest possible value of n if the last number in the row is odd?
[3 points]

Autumn 1999, A Level, Juniors, problem 4.
(a) On each of the 1×1 squares of the top row of an 8×8 chessboard there is a black pawn, and on each of the 1×1 squares of the bottom row of this chessboard there is a white pawn. On each move one can shift any pawn vertically or horizontally to any adjacent empty 1×1 square. What is the smallest number of moves that are needed to move all white pawns to the top row and all black pawns to the bottom row?
(b) The same question for a 7×7 board.
[Points: (a) 3, (b) 4]

Autumn 1999, A Level, Juniors, problem 5.
Tireless Thomas and Jeremy construct a sequence. At the beginning there is one positive integer in the sequence. Then they successively write new numbers in the following way: Thomas obtains the next number by adding to the previous number one of its (decimal) digits, while Jeremy obtains the next number by subtracting from the previous number one of its digits. Prove that there is a number in this sequence which will be repeated at least 100 times.
(with S.Genkin)
[8 points]

Autumn 1999, A Level, Juniors, problem 6.
Inside a rectangular piece of paper n rectangular holes with sides parallel to the sides of the paper have been cut out. Into what minimal number of rectangular pieces (without holes) is it always possible to cut this piece of paper?
[9 points]

Autumn 1999, A Level, Seniors, problem 1.
For what values of n is it possible to place the integers from 1 to n inclusive on a circle (not necessarily in order) so that the sum of any two successive integers in the circle is divisible by the next one in clockwise order?
[3 points]

Autumn 1999, A Level, Seniors, problem 2.
On a rectangular piece of paper there are
(a) several marked points all on the straight line;
(b) three marked points (not necessarily on a straight line).
We are allowed to fold the paper several times along a straight line not containing marked points and then puncture the folded paper with a needle. Show that this can be done so that after the paper has been unfolded all the marked points are punctured and there are no extra holes.
[Points: (a) 2, (b) 3]

Autumn 1999, A Level, Seniors, problem 5.
(a) The numbers 1, 2, ... , 100 are divided into two groups so that the sum of all numbers in one group is equal to that in the other. Prove that one can remove two numbers from each group so that the sums of all numbers in each group are still the same.
(b) The numbers 1, 2, ... , n are divided into two groups so that the sum of all numbers in one group is equal to that in the other. Is it true that for any such n > 4 one can remove two numbers from each group so that the sums of all numbers in each group are still the same?
[Points: (a) 4, (b) 4]

Autumn 1999, A Level, Seniors, problem 6.
On a large chessboard, 2n of its squares have been marked so that the rook (which moves only horizontally or vertically) can visit all the marked squares without jumping over any unmarked ones. Prove that the figure consisting of all the marked squares can be cut into n rectangles.
(with Maxim Shapovalov)
[8 points]

Spring 2000, O Level, Juniors, problem 3.
The bases of a prism is an n-gon. We wish to colour its 2n vertices in three colours in such a way that every vertex is connected by edges to vertices of all three colours. (a) Prove that if n is divisible by 3, then the task is possible.
(b) Prove that if the task is possible, then n is divisible by 3.
[Points: (a) 2, (b) 3]

Spring 2000, O Level, Juniors, problem 4.
Can one place positive integers at all vertices of a cube in such a way that for every pair of numbers connected by an edge, one will be divisible by the other, and there are no other pairs of numbers with this property?
[5 points]

Spring 2000, O Level, Seniors, problem 2.
Each of pair of opposite faces of a unite cube is marked by a dot. Each of another pair of opposite faces is marked by two dots. Each of the remaining two faces is marked by three dots. Eight such cubes are used to construct a 2×2×2 cube. Count the total number of dots on each of its six faces. Can we obtain six consecutive numbers?
[4 points]

Spring 2000, A Level, Juniors, problem 2.
The parallel sides of a quadrilateral have integer lengths. Prove that this quadrilateral can be cut into congruent triangles.
[3 points]

Spring 2000, A Level, Juniors, problem 4.
Give and Take divide 100 coins between them as follows. In each step, Give chooses a handful of coins from the heap, and Take decides who gets this handful. This is repeated until all the coins have been taken, or one of them has 9 handfuls. In the latter case, the other gets all the remaining coins. What is the largest number of coins that Give can be sure of getting no matter what Take does?
[7 points]

Spring 2000, A Level, Seniors, problem 3.
Peter plays a solitaire game with a deck of cards, some of which are face-up while the others are face-down. Peter looses if all the cards are face-down. As long as at least one card is face-up, Peter must choose a stack of consecutive cards from the deck, so that the top and the bottom cards of the stack are face-up. They may be the same card. Then Peter turns the whole stack over and puts it back into the deck in exactly the same place as before. Prove that Peter always looses.
[5 points]

Autumn 2000, O Level, Juniors, problem 3.
(a) On a blackboard are written 100 different numbers. Prove that you can choose 8 of them so that their average value is not equal to that of any 9 of the numbers on the blackboard.
(b) On a blackboard are written 100 integers. For any 8 of them, you can find 9 numbers on the blackboard so that the average value of the 8 numbers is equal to that of the 9. Prove that all the numbers are equal.
[Points: (a) 2, (b) 4]

Autumn 2000, O Level, Juniors, problem 4.
Among a set of 32 coins, all identical in appearance, 30 are real and 2 are fake. Any two real coins have the same weight. The fake coins have the same weight, which is different from the weight of a real coin. How can one divide the coins into two groups of equal total weight by using a balance at most 4 times?
[5 points]

Autumn 2000, O Level, Seniors, problem 3.
In each lateral face of a pentagonal prism at least one of the four angles is equal to f. Find all possible values of f.
[4 points]

Autumn 2000, O Level, Seniors, problem 4.
Among a set of 2N coins, all identical in appearance, 2N-2 are real and 2 are fake. Any two real coins have the same weight. The fake coins have the same weight, which is different from the weight of a real coin. How can one divide the coins into two groups of equal total weight by using a balance at most 4 times, if
(a) N = 16;
(b) N = 11?
[Points: (a) 3, (b) 2]

Autumn 2000, A Level, Seniors, problem 2.
What is the largest integer n such that one can find n points on the surface of the cube, not all lying on one face and being the vertices of a regular n-gon?
[4 points]

Autumn 2000, A Level, Seniors, problem 5.
Each of the cells of an m×n table is coloured either black or white. For each cell, the total number of the cells which are in the same row on in the same column and of the same colour as this cell is strictly less then the total number of the cells which are in the same row on in the same column and of the other colour as this cell. Prove that in each row and in each column the number of the white cells is the same as the number of the black ones.
[6 points]

Spring 2001, O Level, Juniors, problem 2.
Let D, E and F be the midpoints of BC, CA and AB respectively. If one of DE, EF and FD is longer than one of AD, BE and CF, prove that ABC is an obtuse triangle.
[4 points]

Spring 2001, O Level, Juniors, problem 4.
There are five identical paper triangles on a table. Each may be slid in any direction parallel to itself without rotation.
(a) Is it true that any one of them can be covered by the other four?
(b) Prove that any one of them can be covered by the other four if the triangle is equilateral.
[Points: (a) 2, (b) 3]

Spring 2001, A Level, Juniors, problem 5.
A black pawn and a white pawn are placed on a chessboard. In each move, one of the pawns goes to an adjacent vacant square of the chessboard either vertically or horizontally. It is desired to construct a sequence of moves so that every possible postion of the two pawns on the chessboard will appear exactly once.
(a) Is this possible if the pawns must be moved alternately?
(b) Is this possible if the pawns need not be moved alternately?
[Points: (a) 3, (b) 4]