2000/2001 - 1st series of the winter part
Deadline: October 2, 2000

Mathematical Medley

1. The kindergarten group is standing in the column of pairs. The number of boys equals the number of girls in each of the two columns. The number of mixed (boy and girl) pairs equals to the number of the rest pairs. Prove that the total number of children in the group is dividable by eight.

2a. 2b. Two are playing the game "cats and rats" on the chess-board 8x8. The first has one piece -- a rat, the second -- several pieces -- cats. All the pieces have four available moves -- up, down, left, right -- to the neighbour field, but the rat can also escape from the board if it is on the boarder of the chess-board. If they appear on the same field -- the rat is eaten. The players move in turn, but the second can move all the cats in independent directions.
a) Let there be two cats. The rat is on the interior field. Is it possible to put the cats on such a fields on the border that they will be able to catch the rat?
b) Let there be three cats, but the rat moves twice during the first turn. Prove that the rat can escape.

3a. Some pawns are placed on a chessboard. We can move in each turn a pawn to neighbouring square (squares are neighbouring if they have common side). After some turns each pawn visited each square exactly once and returned to beginning position. Prove that in some moment no pawn was on beginning position.

3b. The world and the European champion are determined in the same tournament carried in one round. There are 20 teams and k of them are European. The European champion is determined according to the results of the games only between those k teams. What is the greatest k such that the situation, when the single European champion is the single world outsider, is possible if it is hockey (draws allowed)?

4a. A computer screen shows a 98x98 chessboard, colored in the usual way. One can select with a mouse any rectangle with sides on the lines of the chessboard and click the mouse button as a result, the colors in the selected rectangle switch (black becomes white, white becomes black). Find, with proof, the minimum number of mouse clicks needed to make the chessboard all one color.

4b. Let n>1 be a positive integer. Arbitrary 2n squares of a table n x n are chosen and a pawn is put on each chosen square. Prove that four squares with pawns can be chosen such that their centres are the vertices of a parallelogram.

5a. Suppose that necklace A has 14 beads and necklace B has 19. Prove that for any odd integer n >= 1, there is a way to number each of the 33 beads with an integer from the sequence (n, n+1, ..., n+32) so that each integer is used once, and adjacent beads correspond to relatively prime integers.

5b. The Y2K Game is played on a 1x2000 grid as follows. Two players in turn write either an S or an O in an empty square. The first player who produces three consecutive boxes that spell SOS wins. If all boxes are filled without preducing SOS then the game is a draw. Prove that the second player has a winning strategy.