Found problems: 109
On the screen of a computer there is an $2^n\times 2^n$ board. On each cell of the main diagonal there is a file. At each step, we may select some files and move them to the left, on their respective rows, by the same distance. What is the minimum number of necessary moves in order to put all files on the first column?
[i]Proposed by Vlad Spătaru[/i]
A board $n \times n$ is divided into $n^2$ unit squares and a number is written in each unit square.
Such a board is called [i] interesting[/i] if the following conditions hold:
$\circ$ In all unit squares below the main diagonal, the number $0$ is written;
$\circ$ Positive integers are written in all other unit squares.
$\circ$ When we look at the sums in all $n$ rows, and the sums in all $n$ columns, those $2n$ numbers
are actually the numbers $1,2,...,2n$ (not necessarily in that order).
$a)$ Determine the largest number that can appear in a $6 \times 6$ [i]interesting[/i] board.
$b)$ Prove that there is no [i]interesting[/i] board of dimensions $7\times 7$.
A [i]squidward[/i] is a piece that moves on a board in the following way: it advances three squares in one direction and then two squares in a perpendicular direction. For example, in the figure below, by making one move, the squidward can move to any of the $8$ squares indicated with arrows. Initially, there is one squidward on each of the $35$ squares of a $5 \times 7$ board. At the same time, each squidward makes exactly one move. What is the smallest possible number of empty squares after these moves?
[center][img]https://i.imgur.com/rqgG95C.png[/img][/center]
Two types of pieces, bishops and rooks, are to be placed on a $10\times 10$ chessboard (without necessarily filling it) such that each piece occupies exactly one square of the board. A bishop $B$ is said to [i]attack[/i] a piece $P$ if $B$ and $P$ are on the same diagonal and there are no pieces between $B$ and $P$ on that diagonal; a rook $R$ is said to attack a piece $P$ if $R$ and $P$ are on the same row or column and there are no pieces between $R$ and $P$ on that row or column.
A piece $P$ is [i]chocolate[/i] if no other piece $Q$ attacks $P$.
What is the maximum number of chocolate pieces there may be, after placing some pieces on the chessboard?
[i]Proposed by José Alejandro Reyes González[/i]
Let $n$ be a positive integer. We are given a $3n \times 3n$ board whose unit squares are colored in black and white in such way that starting with the top left square, every third diagonal is colored in black and the rest of the board is in white. In one move, one can take a $2 \times 2$ square and change the color of all its squares in such way that white squares become orange, orange ones become black and black ones become white. Find all $n$ for which, using a finite number of moves, we can make all the squares which were initially black white, and all squares which were initially white black.
Proposed by [i]Boris Stanković and Marko Dimitrić, Bosnia and Herzegovina[/i]
A one player game is played on the triangular board shown on the picture. A token is placed on each circle. Each token is white on one side and black on the other. Initially, the token at one vertex of the triangle has the black side up, while the others have the white sides up. A move consists of removing a token with the black side up and turning over the adjacent tokens (two tokens are adjacent if they are joined by a segment). Is it possible to remove all the tokens by a sequence of moves?
[img]https://cdn.artofproblemsolving.com/attachments/d/2/aabf82a0ddd6907482f27e6e0f1e1b56cd931d.png[/img]
An $7\times 7$ array is divided in $49$ unit squares. Find all integers $n \in N^*$ for which $n$ checkers can be placed on the unit squares so that each row and each line have an even number of checkers.
($0$ is an even number, so there may exist empty rows or columns. A square may be occupied by at most $1$ checker).
If $46$ squares are colored red in a $9\times 9$ board, show that there is a $2\times 2$ block on the board in which at least $3$ of the squares are colored red.
All cells of an $n\times n$ table are painted in several colors so that there is no monochromatic $2\times2$ square. A sequence of different cells $a_1,a_2,\ldots,a_k$ is called a [i]colorful[/i] if any two consecutive cells are adjacent and are painted in different colors. What is the largest $k{}$ for which there is a colorful sequence of length $k{}$ regardless of the coloring of the cells of the table?
[i]Proposed by N. Belukhov[/i]
There are several dominoes on a board such that each domino occupies two adjacent cells and none of the dominoes are adjacent by side or vertex. The bottom left and top right cells of the board are free. A token starts at the bottom left cell and can move to a cell adjacent by side: one step to the right or upwards at each turn. Is it always possible to move from the bottom left to the top right cell without passing through dominoes if the size of the board is a) $100 \times 101$ cells and b) $100 \times 100$ cells?
[i]Nikolay Chernyatiev[/i]
An equilateral triangle of side $n$ has been divided into little equilateral triangles of side $1$ in the usual way. We draw a path over the segments of this triangulation, in such a way that it visits exactly once each one of the $\frac{(n+1)(n+2)}{2}$ vertices. What is the minimum number of times the path can change its direction?
The figure below shows a valid path on a triangular board of side $4$, with exactly $9$ changes of direction.
[asy]
unitsize(30);
pair h = (1, 0);
pair v = dir(60);
pair d = dir(120);
for(int i = 0; i < 4; ++i)
{
draw(i*v -- i*v + (4 - i)*h);
draw(i*h -- i*h + (4 - i)*v);
draw((i + 1)*h -- (i + 1)*h + (i + 1)*d);
}
draw(h + v -- v -- (0, 0) -- 2*h -- 2*h + v -- h + 2*v -- 2*v -- 4*v -- 3*h + v -- 3*h -- 4*h, linewidth(2));
draw(3*h -- 4*h, EndArrow);
fill(circle(h + v, 0.1));
[/asy]
[i]Proposed by Oriol Solé[/i]
There is a bacterium in one of the cells of a $10 \times 10{}$ checkered board. At the first move, the bacterium shifts to a cell adjacent by side to the original one, and divides into two bacteria (both stay in the same cell). Then again, one of the bacteria on the board shifts to a cell adjacent by side and divides into two bacteria, and so on. Is it possible that after some number of such moves the number of bacteria in each cell of the board is the same?
[i]Alexandr Gribalko[/i]
Two types of tiles, depicted on the figure below, are given.
[img]https://wiki-images.artofproblemsolving.com//2/23/Izrezak.PNG[/img]
Find all positive integers $n$ such that an $n\times n$ board consisting of $n^2$ unit squares can be covered without gaps with these two types of tiles (rotations and reflections are allowed) so that no two tiles overlap and no part of any tile covers an area outside the $n\times n$ board. \\
[i]Proposed by Art Waeterschoot[/i]
We are given an $(n^2-1)\times(n^2-1)$ checkered board. A set of $n{}$ cells is called [i]progressive[/i] if the centers of the cells lie on a straight line and form $n-1$ equal intervals. Find the number of progressive sets.
[i]Proposed by P. Kozhevnikov[/i]
Consider an integer \(n \ge 2\) and write the numbers \(1, 2, \ldots, n\) down on a board. A move consists in erasing any two numbers \(a\) and \(b\), then writing down the numbers \(a+b\) and \(\vert a-b \vert\) on the board, and then removing repetitions (e.g., if the board contained the numbers \(2, 5, 7, 8\), then one could choose the numbers \(a = 5\) and \(b = 7\), obtaining the board with numbers \(2, 8, 12\)). For all integers \(n \ge 2\), determine whether it is possible to be left with exactly two numbers on the board after a finite number of moves.
[i]Proposed by China[/i]
Consider a game on an \( n \times n \) board, where each square starts with exactly one stone. A move consists of choosing $5$ consecutive squares in the same row or column of the board and toggling the state of each of those squares (removing the stone from squares with a stone and placing a stone in squares without a stone). For which positive integers \( n \geq 5 \) is it possible to end up with exactly one stone on the board after a finite number of moves?
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]
Consider a checkered $3m\times 3m$ square, where $m$ is an integer greater than $1.$ A frog sits on the lower left corner cell $S$ and wants to get to the upper right corner cell $F.$ The frog can hop from any cell to either the next cell to the right or the next cell upwards.
Some cells can be [i]sticky[/i], and the frog gets trapped once it hops on such a cell. A set $X$ of cells is called [i]blocking[/i] if the frog cannot reach $F$ from $S$ when all the cells of $X$ are sticky. A blocking set is [i] minimal[/i] if it does not contain a smaller blocking set.[list=a][*]Prove that there exists a minimal blocking set containing at least $3m^2-3m$ cells.
[*]Prove that every minimal blocking set containing at most $3m^2$ cells.
$\bullet$ Determine a natural $n$ such that the constant sum $S$ of a magic square of $ n \times n$ (that is, the sum of its elements in any column, or the diagonal) differs as little as possible from $1992$.
$\bullet$ Construct or describe the construction of this magic square.
In how many ways can we fill the cells of a $4\times4$ grid such that each cell contains exactly one positive integer and the product of the numbers in each row and each column is $2020$?
All the cells of a $10\times10$ board are colored white initially. Two players are playing a game with alternating moves. A move consists of coloring any un-colored cell black. A player is considered to loose, if after his move no white domino is left. Which of the players has a winning strategy?
[I]Proposed by A. Khrabrov[/i]
There was a rook at some square of a $10 \times 10{}$ chessboard. At each turn it moved to a square adjacent by side. It visited each square exactly once. Prove that for each main diagonal (the diagonal between the corners of the board) the following statement is true: in the rook’s path there were two consecutive steps at which the rook first stepped away from the diagonal and then returned back to the diagonal.
[i]Alexandr Gribalko[/i]
There are $n$ positive integers on the board. We can add only positive integers $c=\frac{a+b}{a-b}$, where $a$ and $b$ are numbers already writted on the board.
$a)$ Find minimal value of $n$, such that with adding numbers with described method, we can get any positive integer number written on the board
$b)$ For such $n$, find numbers written on the board at the beginning
On a $100 \times 100$ chessboard, the plan is to place several $1 \times 3$ boards and $3 \times 1$ board, so that
[list]
[*] Each tile of the initial chessboard is covered by at most one small board.
[*] The boards cover the entire chessboard tile, except for one tile.
[*] The sides of the board are placed parallel to the chessboard.
[/list]
Suppose that to carry out the instructions above, it takes $H$ number of $1 \times 3$ boards and $V$ number of $3 \times 1$ boards. Determine all possible pairs of $(H,V)$.
[i]Proposed by Muhammad Afifurrahman, Indonesia[/i]
The numbers $1$ through $16$ are to be written in the cells of a $4\times 4$ board.
(a) Prove that this can be done in such a way that any two numbers in cells that share a side differ by at most $4$.
(b) Prove that this cannot be done in such a way that any two numbers in cells that share a side differ by at most $3$.