Found problems: 59
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.
In an $8 \times 8$ grid, $n$ disks, numbered $1$ to $n$ are stacked, with random order, in a pile in the bottom left comer. The disks can be moved one at a time to a neighbouring cell either to the right or top. The aim to move all the disks to the cell at the top right comer and stack them in the order $1,2,...,n$ from the bottom. Each cell, except the bottom left and top right cell, can have at most one disk at any given time. Find the largest value of $n$ so that the aim can be achieved.
Given a $n\times n$ table, where $n$ is odd. There is either $1$ or $-1$ in its every field. A product of the numbers in the column is written under every column. A product of the numbers in the row is written to the right of every row. Prove that the sum of $2n$ products doesn't equal to $0$.
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$.
A sequence $(a_1, a_2,...,a_k)$ consisting of pairwise different cells of an $n\times n$ board is called a cycle if $k \ge 4$ and cell ai shares a side with cell $a_{i+1}$ for every $i = 1,2,..., k$, where $a_{k+1} = a_1$. We will say that a subset $X$ of the set of cells of a board is [i]malicious [/i] if every cycle on the board contains at least one cell belonging to $X$. Determine all real numbers $C$ with the following property: for every integer $n \ge 2$ on an $n\times n$ board there exists a malicious set containing at most $Cn^2$ cells.
Each entry in an $n\times n$ table is either $+$ or $-$. At each step, one can choose a row or a column and reverse all signs in it. From the initial position, it is possible to obtain the table in which all signs are $+$. Prove that this can be accomplished in at most $n$ steps.
a) A square table with $49$ small squares is filled with numbers $1$ to $7$ so that in each row and in each column all numbers from $1$ to $7$ are present. Let the table be symmetric through the main diagonal. Prove that on this diagonal all the numbers $1, 2, 3, . . . , 7$ are present.
b) A square table with $n^2$ small squares is filled with numbers $1$ to $n$ so that in each row and in each column all numbers from $1$ to $n$ are present. Let $n$ be odd and the table be symmetric through the main diagonal. Prove that on this diagonal all the numbers $1, 2, 3, . . . , n$ are present.
Find the greatest number of depicted pieces composed of $4$ unit squares that can be placed without overlapping on an $n \times n$ grid (where n is a positive integer) in such a way that it is possible to move from some corner to the opposite corner via uncovered squares (moving between squares requires a common edge). The shapes can be rotated and reflected.
[img]https://cdn.artofproblemsolving.com/attachments/b/d/f2978a24fdd737edfafa5927a8d2129eb586ee.png[/img]
A $17 \times 17$ square is cut out of a sheet of graph paper. Each cell of this square has one of thenumbers from $1$ to $70$. Prove that there are $4$ distinct squares whose centers $A, B, C, D$ are the vertices of a parallelogramsuch that $AB // CD$, moreover, the sum of the numbers in the squares with centers $A$ and $C$ is equal to that in the squares with centers $B$ and $D$.
Prove that it is impossible to fill the cells of an $8 \times 8$ table with the numbers from $ 1$ to $64$ (each number must be used once) so that for each $2\times 2$ square, the difference between products of the numbers on it’s diagonals will be equal to $ 1$.
Every cell of a $20 \times 20$ table has to be coloured black or white (there are $2^{400}$ such colourings in total). Given any colouring $P$, we consider division of the table into rectangles with sides in the grid lines where no rectangle contains more than two black cells and where the number of rectangles containing at most one black cell is the least possible. We denote this smallest possible number of rectangles containing at most one black cell by $f(P)$. Determine the maximum value of $f(P)$ as $P$ ranges over all colourings.
In a $N \times N$ array of numbers, all rows are different (two rows are said to be different even if they differ only in one entry). Prove that there is a column which can be deleted in such a way that the resulting rows will still be different.
(A Andjans, Riga)
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
Let $n$ be a positive integer. In how many ways can an $n \times n$ table be filled with integers from $0$ to $5$ such that
a) the sum of each row is divisible by $2$ and the sum of each column is divisible by $3$
b) the sum of each row is divisible by $2$, the sum of each column is divisible by $3$ and the sum of each of the two diagonals is divisible by $6$?
In every unit square of a$ n \times n$ table ($n \ge 11$) a real number is written, such that the sum of the numbers in any $10 \times 10$ square is positive and the sum of the numbers in any $11\times 11$ square is negative. Determine all possible values for $n$
The figure shows a figure of $5$ unit squares, a Greek cross. What is the largest number of Greek crosses that can be placed on a grid of dimensions $8 \times 8$ without any overlaps, with each unit square covering just one square in a grid?
Every unit square of a $n \times n$ board is colored either red or blue so that among all 2 $\times 2$ squares on this board all possible colorings of $2 \times 2$ squares with these two colors are represented (colorings obtained from each other by rotation and reflection are considered different).
a) Find the least possible value of $n$.
b) For the least possible value of $n$ find the least possible number of red unit squares
There is a $19\times19$ board. Is it possible to mark some $1\times 1$ squares so that each of $10\times 10$ squares contain different number of marked squares?
Find the smallest positive integer $n$ with the following property:
After painting black exactly $n$ cells of a $7\times 7$ board there always exists a $2\times 2$ square with at least three black cells.
From a squared sheet of paper of size $29 \times 29, 99$ pieces, each a $2\times 2$ square, are cut off (all cutting is along the lines bounding the squares). Prove that at least one more piece of size $2\times 2$ may be cut from the remaining part of the sheet.
(S Fomin, Leningrad)
(a) On each square of a squared sheet of paper of size $20 \times 20$ there is a soldier. Vanya chooses a number $d$ and Petya moves the soldiers to new squares in such a way that each soldier is moved through a distance of at least $d$ (the distance being measured between the centres of the initial and the new squares) and each square is occupied by exactly one soldier. For which $d$ is this possible?
(Give the maximum possible $d$, prove that it is possible to move the soldiers through distances not less than $d$ and prove that there is no greater $d$ for which this procedure may be carried out.)
(b) Answer the same question as (a), but with a sheet of size $21 \times 21$.
(SS Krotov, Moscow)
Each field of the $1987\times 1987$ board is filled with numbers, which absolute value is not greater than one. The sum of all the numbers in every $2\times 2$ square equals $0$. Prove that the sum of all the numbers is not greater than $1987$.
Given a square $100\times 100$ on the sheet of cross-lined paper. There are several broken lines drawn inside the square. Their links consist of the small squares sides. They are neither pairwise- nor self-intersecting (have no common points). Their ends are on the big square boarder, and all the other vertices are in the big square interior. Prove that there exists (in addition to four big square angles) a node (corresponding to the cross-lining family, inside the big square or on its side) that does not belong to any broken line.
Nine numbers are arranged in a square table:
$a_1 \,\,\, a_2 \,\,\,a_3$
$b_1 \,\,\,b_2 \,\,\,b_3$
$c_1\,\,\, c_2 \,\,\,c_3$ .
It is known that the six numbers obtained by summing the rows and columns of the table are equal:
$a_1 + a_2 + a_3 = b_1 + b_2 + b_3 = c_1 + c_2 + c_3 = a_1 + b_1 + c_1 = a_2 + b_2 + c_2 = a_3 + b_3 + c_3$ .
Prove that the sum of products of numbers in the rows is equal to the sum of products of numbers in the columns:
$a_1 b_1 c_1 + a_2 b_2c_2 + a_3b_3c_3 = a_1a_2a_3 + b_1 b_2 b_3 + c_1 c_2c_3$ .
(V Proizvolov)
Find the greatest number of depicted pieces composed of $4$ unit squares that can be placed without overlapping on an $n \times n$ grid (where n is a positive integer) in such a way that it is possible to move from some corner to the opposite corner via uncovered squares (moving between squares requires a common edge). The shapes can be rotated and reflected.
[img]https://cdn.artofproblemsolving.com/attachments/b/d/f2978a24fdd737edfafa5927a8d2129eb586ee.png[/img]