Found problems: 59
Is it possible to put the numbers $0,1$ or $2$ in the unit squares of the cross-lined paper $100\times 100$ in such a way, that every rectangle $3\times 4$ (and $4\times 3$) would contain three zeros, four ones and five twos?
No matter how two copies of a convex polygon are placed inside a square, they always have a common point. Prove that no matter how three copies of the same polygon are placed inside this square, they also have a common point.
Every cell of a $4\times 4$ square grid net, has $1\times 1$ size. Is it possible to represent this net as a union of the following sets:
a) Eight broken lines of length five each?
b) Five broken lines of length eight each?
In a $3n \times 3n$ grid, each square is either black or red. Each red square not on the edge of the grid has exactly five black squares among its eight neighbor squares.. On every black square that not at the edge of the grid, there are exactly four reds in the adjacent squares box. How many black and how many red squares are in the grid?
A $5\times 5$ board is covered by eight hooks (a three unit square figure, shown in the picture) so that one unit square remains free. Determine all squares of the board that can remain free after such covering.
[img]https://cdn.artofproblemsolving.com/attachments/6/8/a8c4e47ba137b904bd28c01c1d2cb765824e6a.png[/img]
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?
Two people play a game on a $9 \times 9$ board. They move alternately. On each move, the first player draws a cross in an empty cell, and the second player draws a nought in an empty cell. When all $81$ cells are filled, the number $K$ of rows and columns in which there are more crosses and the number $H$ of rows and columns in which there are more noughts are counted. The score for the first player is the difference $B = K- H$. Find a value of $B$ such that the first player can guarantee a score of at least $B$, while the second player can hold the first player's score to at most B, regardless how the opponent plays.
(A Kanel)
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?
A number is placed in each cell of an $n \times n$ board so that the following holds:
(A) the cells on the boundary all contain 0;
(B) other cells on the main diagonal are each1 greater than the mean of the numbers to the left and right;
(C) other cells are the mean of the numbers to the left and right.
Show that (B) and (C) remain true if ''left and right'' is replaced by ''above and below''.
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)
Initially, all the squares of an $8\times 8$ grid are white. You start by choosing one of the squares and coloring it gray. After that, you may color additional squares gray one at a time, but you may only color a square gray if it has exactly $1$ or $3$ gray neighbors at that moment (where a neighbor is a square sharing an edge).
For example, the configuration below (of a smaller $3\times 4$ grid) shows a situation where six squares have been colored gray so far. The squares that can be colored at the next step are marked with a dot.
Is it possible to color all the squares gray? Justify your answer.
[img]https://cdn.artofproblemsolving.com/attachments/1/c/d50ab269f481e4e516dace06a991e6b37f2a85.png[/img]
a) The fields of the square table $4\times 4$ are filled with the "+" or "-" signs. You are allowed to change the signs simultaneously in the whole row, column, or diagonal to the opposite sign. That means, for example, that You can change the sign in the corner square, because it makes a diagonal itself. Prove that you will never manage to obtain a table containing pluses only.
b) The fields of the square table $8\times 8$ are filled with the "+" or signs except one non-corner field with "-". You are allowed to change the signs simultaneously in the whole row, column, or diagonal to the opposite sign. That means, for example, that You can change the sign in the corner field, because it makes a diagonal itself. Prove that you will never manage to obtain a table containing pluses only.
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?
Consider a table of cyclic permutations ($n\ge2$)
\[
\begin{matrix}
1, & 2, & \ldots, & n-1, & n \\
2, & 3, & \ldots, & n, & 1, \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
n, & 1, & \ldots, & n-2, & n-1.
\end{matrix}
\]
Then multiply each number of the first row by that number of the $k$-th row that is in the same column. Sum all these products and denote $s_k$ the result (e.g. $s_2=1\cdot2+2\cdot3+\cdots+(n-1)\cdot n+n\cdot1$).
a) Find a recursive relation for $s_k$ in terms of $s_{k-1}$ and determine the explicit formula for $s_k$.
b) Determine both an index $k$ and the value of $s_k$ such that the sum $s_k$ is minimal.
Given the square table $n\times n$ with $(n-1)$ marked fields. Prove that it is possible to move all the marked fields below the diagonal by moving rows and columns.
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
Each $1 \times 1$ square of an $n \times n$ table contains a different number. The smallest number in each row is marked, and these marked numbers are in different columns. Then the smallest number in each column is marked, and these marked numbers are in different rows. Prove that the two sets of marked numbers are identical.
(V Klepcyn)
A table consists of $17 \times 17$ squares. In each square one positive integer from $1$ to $17$ is written, every such number is written in exactly $17$ squares. Prove that there is a row or a column of the table that contains at least $5$ different numbers.
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$?
There is a $8\times 8$ table, drawn in a plane and painted in a chess board fashion. Peter mentally chooses a square and an interior point in it. Basil can draws any polygon (without self-intersections) in the plane and ask Peter whether the chosen point is inside or outside this polygon. What is the minimal number of questions suffcient to determine whether the chosen point is black or white?
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)
a) $r_1, r_2, ... , r_{100}, c_1, c_2, ... , c_{100}$ are distinct reals. The number $r_i + c_j$ is written in position $i, j$ of a $100 \times 100$ array. The product of the numbers in each column is $1$. Show that the product of the numbers in each row is $-1$.
b) $r_1, r_2, ... , r_{2n}, c_1, c_2, ... , c_{2n}$ are distinct reals. The number $r_i + c_j$ is written in position $i, j$ of a $2n \times 2n$ array. The product of the numbers in each column is the same. Show that the product of the numbers in each row is also the same.
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.
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.
a) The numbers $1, 2, . . . , 49$ are arranged in a square table as follows:
[img]https://cdn.artofproblemsolving.com/attachments/5/0/c2e350a6ad0ebb8c728affe0ebb70783baf913.png[/img]
Among these numbers we select an arbitrary number and delete from the table the row and the column which contain this number. We do the same with the remaining table of $36$ numbers, etc., $7$ times. Find the sum of the numbers selected.
b) The numbers $1, 2, . . . , k^2$ are arranged in a square table as follows:
[img]https://cdn.artofproblemsolving.com/attachments/2/d/28d60518952c3acddc303e427483211c42cd4a.png[/img]
Among these numbers we select an arbitrary number and delete from the table the row and the column which contain this number. We do the same with the remaining table of $(k - 1)^2$ numbers, etc., $k$ times. Find the sum of the numbers selected.