Found problems: 124
We call a table of size $n \times n$ self-describing if each cell of the table contains the total number of even numbers in its row and column other than itself. How many self-describing tables of size
a) $3 \times 3$ exist?
b) $4 \times 4$ exist?
c) $5 \times 5$ exist?
Two tables are different if they differ in at least one cell.
Numbers from $1$ to $49$ are randomly placed in a $35 \times 35$ table such that number $i$ is used exactly $i$ times. Some random cells of the table are removed so that table falls apart into several connected (by sides) polygons. Among them, the one with the largest area is chosen (if there are several of the same largest areas, a random one of them is chosen). What is the largest number of cells that can be removed that guarantees that in the chosen polygon there is a number which occurs at least $15$ times?
$n$ is a natural number. Given $3n \cdot 3n$ table, the unit cells are colored white and black such that starting from the left up corner diagonals are colored in pure white or black in ratio of 2:1 respectively. ( See the picture below). In one step any chosen $2 \cdot 2$ square's white cells are colored orange, orange are colored black and black are colored white. Find all $n$ such that with finite steps, all the white cells in the table turns to black, and all black cells in the table turns to white. ( From starting point)
Two intelligent people playing a game on the $1403 \times 1403$ table with $1403^2$ cells. The first one in each turn chooses a cell that didn't select before and draws a vertical line segment from the top to the bottom of the cell. The second person in each turn chooses a cell that didn't select before and draws a horizontal line segment from the left to the right of the cell. After $1403^2$ steps the game will be over. The first person gets points equal to the longest verticals line segment and analogously the second person gets point equal to the longest horizonal line segment. At the end the person who gets the more point will win the game. What will be the result of the game?
King Arthur is placing $a + b + c$ knights around a table.
$a$ knights are dressed in red, $b$ knights are dressed in brown, and $c$ knights are dressed in orange.
Arthur wishes to arrange the knights so that no knight is seated next to someone dressed in the same colour as himself. Show that this is possible if, and only if, there exists a triangle whose sides have lengths $a +\frac12, b +\frac12$, and $c +\frac12$
Given is a table 4x4 and in every square there is 0 or 1. In a move we choose row or column and we change the numbers there. Call the square "zero" if we cannot decrease the number of zeroes in it. Call "degree of the square" the number zeroes in a "zero" square. Find all possible values of the degree.
For each natural $n \ge 4$, find the smallest natural number $k$ that satisfies following condition:
For an arbitrary arrangement of $k$ chips of two colors on $n\times n$ board, there exists a non-empty set such that all columns and rows contain even number ($0$ is also possible) of chips each color.
One needs to ffll the cells of an $n\times n$ table ($n > 1$) with distinct integers from $1$ to $n^2$ so that every two consecutive integers are placed in cells that share a side, while every two integers with the same remainder if divided by $n$ are placed in distinct rows and distinct columns. For which $n$ is this possible?
(Alexandr Gribalko)
A rectangular array has $m$ rows and $n$ columns, where $m < n$. Some cells of the array contain stars, in such a way that there is at least one star in each column. Prove that there is at least one such star such that the row containing it has more stars than the column containing it.
(A. Razborov, Moscow)
Rectangles $1\times20$, $1\times 19$, ..., $1\times 1$ were cut out of $20\times20$ table. Prove that from the remaining part of the table $36$ $1\times2$ dominos can be cut
[I]Proposed by S. Berlov[/i]
Is it possible to fill a rectangular table with black and white squares (only) so, that the number of black squares will equal to the number of white squares, and each row and each column will have more than $75\%$ squares of the same colour?
Let $d\geq 1$ and $n\geq 0$ be integers. Find the number of ways to write down a nonnegative integer in each square of a $d\times d$ grid such that the numbers in any set of $d$ squares, no two in the same row or column, sum to $n$.
Let $n > 4$ be an integer. A square is divided into $n^2$ smaller identical squares, in some of which were [b]1’s[/b] and in the other – [b]0's[/b]. It is not allowed in one row or column to have the following arrangements of adjacent digits in this order: $101$, $111$ or $1001$. What is the biggest number of [b]1’s[/b] in the table? (The answer depends on $n$.)
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)
Given a natural number $k>1$. Find the smallest number $\alpha$ satisfying the following condition. Suppose that the table $(2k + 1) \times (2k + 1)$ is filled with real numbers not exceeding $1$ in absolute value, and the sums of the numbers in all lines are equal to zero. Then you can rearrange the numbers so that each number remains in its row and all the sums over the columns will be at most $\alpha$.
The entries of a $7 \times 5$ table are fi lled with numbers so that in each $2 \times 3$ rectangle (vertical or horizontal) the sum of numbers is $0$. For $100$ dollars Peter may choose any single entry and learn the number in it. What is the least amount of dollars he should spend in order to learn the total sum of numbers in the table for sure?
a) We are playing the following game on this table:
In each move we select a row or a column of the table, reduce two neighboring numbers in that row or column by $1$ and increase the third one by $1$. After some of these moves can we get to a table with all the same entries?
b) This time we have the choice to arrange the integers from $1$ to $9$ in the$ 3 \times3$ table. Still using the same moves now our aim is to create a table with all the same entries, maximising the value of the entries. What is the highest possible number we can achieve?
On an infinite sheet of graph paper a table is drawn so that in each square of the table stands a number equal to the arithmetic mean of the four adjacent numbers. Out of the table a piece is cut along the lines of the graph paper. Prove that the largest number on the piece always occurs at an edge, where $x = \frac14 (a + b + c + d)$.
The cells of a $8 \times 8$ table are colored either black or white so that each row has a different number of black squares, and each column has a different number of black squares. What is the maximum number of pairs of adjacent cells of different colors?
Cells of a $2000\times2000$ board are colored according to the following rules:
1)At any moment a cell can be colored, if none of its neighbors are colored
2)At any moment a $1\times2$ rectangle can be colored, if exactly two of its neighbors are colored.
3)At any moment a $2\times2$ squared can be colored, if 8 of its neighbors are colored
(Two cells are considered to be neighboring, if they share a common side). Can the entire $2000\times2000$ board be colored?
[I]Proposed by K. Kohas[/i]
Let $n$ be a positive integer and let $t$ be an integer. $n$ distinct integers are written on a table. Bob, sitting in a room nearby, wants to know whether there exist some of these numbers such that their sum is equal to $t$. Alice is standing in front of the table and she wants to help him. At the beginning, she tells him only the initial sum of all numbers on the table. After that, in every move he says one of the $4$ sentences:
$i.$ Is there a number on the table equal to $k$?
$ii.$ If a number $k$ exists on the table, erase him.
$iii.$ If a number $k$ does not exist on the table, add him.
$iv.$ Do the numbers written on the table can be arranged in two sets with equal sum of elements?
On these questions Alice answers yes or no, and the operations he says to her she does (if it is possible) and does not tell him did she do it. Prove that in less than $3n$ moves, Bob can find out whether there exist numbers initially written on the board such that their sum is equal to $t$
a) Given a big square consisting of $7\times 7$ squares. You should mark the centres of $k$ points in such a way, that no quadruple of the marked points will be the vertices of a rectangle with the sides parallel to the sides of the given squares. What is the greatest $k$ such that the problem has solution?
b) The same problem for $13\times 13$ square.
A plane is cut into unit squares, each of which is colored in black or white. It is known that each rectangle 3 x 4 or 4 x 3 contains exactly 8 white squares. In how many ways can this plane be colored?
In every cell of a table with $n$ rows and $m$ columns is written one of the letters $a$, $b$, $c$. Every two rows of the table have the same letter in at most $k\geq 0$ positions and every two columns coincide at most $k$ positions. Find $m$, $n$, $k$ if
\[\frac{2mn+6k}{3(m+n)}\geq k+1\]
A plane is cut into unit squares, which are then colored in $n$ colors. A polygon $P$ is created from $n$ unit squares that are connected by their sides. It is known that any cell polygon created by $P$ with translation, covers $n$ unit squares in different colors. Prove that the plane can be covered with copies of $P$ so that each cell is covered exactly once.