Olympiad problems

1986 Tournament Of Towns, (130) 6

Squares of an $8 \times 8$ chessboard are each allocated a number between $1$ and $32$ , with each number being used twice. Prove that it is possible to choose $32$ such squares, each allocated a different number, so that there is at least one such square on each row or column . (A . Andjans, Riga

1987 All Soviet Union Mathematical Olympiad, 444

Tags: square table , game , game strategy , combinatorics

The "Sea battle" game. a) You are trying to find the $4$-field ship -- a rectangle $1x4$, situated on the $7x7$ playing board. You are allowed to ask a question, whether it occupies the particular field or not. How many questions is it necessary to ask to find that ship surely? b) The same question, but the ship is a connected (i.e. its fields have common sides) set of $4$ fields.

2007 Estonia Team Selection Test, 6

Tags: coloring , grid , square table , combinatorics

Consider a $10 \times 10$ grid. On every move, we colour $4$ unit squares that lie in the intersection of some two rows and two columns. A move is allowed if at least one of the $4$ squares is previously uncoloured. What is the largest possible number of moves that can be taken to colour the whole grid?

1985 Tournament Of Towns, (089) 5

Tags: digit , square table , combinatorics

The digits $0, 1 , 2, ..., 9$ are written in a $10 x 10$ table , each number appearing $10$ times . (a) Is it possible to write them in such a way that in any row or column there would be not more than $4$ different digits? (b) Prove that there must be a row or column containing more than $3$ different digits . { L . D . Kurlyandchik , Leningrad)

1991 All Soviet Union Mathematical Olympiad, 549

Tags: combinatorics , square table , table

An $h \times k$ minor of an $n \times n$ table is the $hk$ cells which lie in $h$ rows and $k$ columns. The semiperimeter of the minor is $h + k$. A number of minors each with semiperimeter at least $n$ together include all the cells on the main diagonal. Show that they include at least half the cells in the table.

1984 Tournament Of Towns, (055) O3

Tags: square table , consecutive , combinatorics

Consider the $4(N-1)$ squares on the boundary of an $N$ by $N$ array of squares. We wish to insert in these squares $4 (N-1)$ consecutive integers (not necessarily positive) so that the sum of the numbers at the four vertices of any rectangle with sides parallel to the diagonals of the array (in the case of a “degenerate” rectangle, i.e. a diagonal, we refer to the sum of the two numbers in its corner squares) are one and the same number. Is this possible? Consider the cases (a) $N = 3$ (b) $N = 4$ (c) $N = 5$ (VG Boltyanskiy, Moscow)

1991 All Soviet Union Mathematical Olympiad, 542

Tags: square table , combinatorics

A minus sign is placed on one square of a $5 \times 5$ board and plus signs are placed on the remaining squares. A move is to select a $2 \times 2, 3 \times 3, 4 \times 4$ or $5 \times 5$ square and change all the signs in it. Which initial positions allow a series of moves to change all the signs to plus?

2001 Estonia National Olympiad, 5

Tags: magic square , combinatorics , difference , sum , square table

A $3\times 3$ table is filled with real numbers in such a way that each number in the table is equal to the absolute value of the difference of the sum of numbers in its row and the sum of numbers in its column. (a) Show that any number in this table can be expressed as a sum or a difference of some two numbers in the table. (b) Show that there is such a table not all of whose entries are $0$.

1982 All Soviet Union Mathematical Olympiad, 340

Tags: combinatorics , table , square table

The square table $n\times n$ is filled by integers. If the fields have common side, the difference of numbers in them doesn't exceed $1$. Prove that some number is encountered not less than a) not less than $[n/2]$ times ($[ ...]$ mean the whole part), b) not less than $n$ times.