Found problems: 136
What is the greatest amount of rooks that can be placed on an $n\times n$ board, such that each rooks beats an even number of rooks? A rook is considered to beat another rook, if they lie on one vertical or one horizontal line and no rooks are between them.
[I]Proposed by D. Karpov[/i]
On grid paper, mark three nodes so that in the triangle they formed, the sum of the two smallest medians equals to half-perimeter.
I have an $n \times n$ sheet of stamps, from which I've been asked to tear out blocks of three adjacent stamps in a single row or column. (I can only tear along the perforations separating adjacent stamps, and each block must come out of the sheet in one piece.) Let $b(n)$ be the smallest number of blocks I can tear out and make it impossible to tear out any more blocks. Prove that there are real constants $c$ and $d$ such that \[ \dfrac{1}{7} n^2 - cn \leq b(n) \leq \dfrac{1}{5} n^2 + dn \] for all $n > 0$.
Petya and Vasya live in neighboring houses (see the plan in the figure). Vasya lives in the fourth entrance. It is known that Petya runs to Vasya by the shortest route (it is not necessary walking along the sides of the cells) and it does not matter from which side he runs around his house. Determine in which entrance he lives Petya .
[img]https://cdn.artofproblemsolving.com/attachments/b/1/741120341a54527b179e95680aaf1c4b98ff84.png[/img]
You have a $2m$ by $2n$ grid of squares coloured in the same way as a standard checkerboard. Find the total number of ways to place $mn$ counters on white squares so that each square contains at most one counter and no two counters are in diagonally adjacent white squares.
Consider a $8\times 8$ chessboard where all $64$ unit squares are at the start white. Prove that, if any $12$ of the $64$ unit square get painted black, then we can find $4$ lines and $4$ rows that have all these $12$ unit squares.
Let $n$ be a fixed positive integer and consider an $n\times n$ grid of real numbers. Determine the greatest possible number of cells $c$ in the grid such that the entry in $c$ is both strictly greater than the average of $c$'s column and strictly less than the average of $c$'s row.
[i]Proposed by Holden Mui[/i]
The square $ABCD$ is divided into $n^2$ equal small (elementary) squares by parallel lines to its sides, (see the figure for the case $n = 4$). A spider starts from point$ A$ and moving only to the right and up tries to arrive at point $C$. Every ” movement” of the spider consists of: ”$k$ steps to the right and $m$ steps up” or ”$m$ steps to the right and $k$ steps up” (which can be performed in any way). The spider first makes $l$ ”movements” and in then, moves to the right or up without any restriction. If $n = m \cdot l$, find all possible ways the spider can approach the point $C$, where $n, m, k, l$ are positive integers with $k < m$.
[img]https://cdn.artofproblemsolving.com/attachments/2/d/4fb71086beb844ca7c492a30c7d333fa08d381.png[/img]
The bottom line of a $2\times 13$ rectangle is filled with $13$ tokens marked with the numbers $1, 2, ..., 13$ and located in that order. An operation is a move of a token from its cell into a free adjacent cell (two cells are called adjacent if they have a common side). What is the minimum number of operations needed to rearrange the chips in reverse order in the bottom line of the rectangle?
Sheldon and Bella play a game on an infinite grid of cells. On each of his turns, Sheldon puts one of the following tetrominoes (reflections and rotations aren't permitted)
[asy]
size(200);
draw((0, 0)--(1, 0)--(1, 2)--(0, 2)--cycle);
draw((1, 1)--(2, 1)--(2, 3)--(1, 3)--cycle);
draw((0,1)--(1,1));
draw((1,2)--(2,2));
draw((5, 0.5)--(6, 0.5)--(6, 1.5)--(5, 1.5)--cycle);
draw((6, 0.5)--(7, 0.5)--(7, 1.5)--(6, 1.5)--cycle);
draw((6, 1.5)--(7, 1.5)--(7, 2.5)--(6, 2.5)--cycle);
draw((7, 1.5)--(8, 1.5)--(8, 2.5)--(7, 2.5)--cycle);
[/asy]
somewhere on the grid without overlap. Then, Bella colors that tetromino such that it has a different color from any other tetromino that shares a side with it. After $2631$ such moves by each player, the game ends, and Sheldon's score is the number of colors used by Bella.
What's the maximum $N$ such that Sheldon can guarantee that his score will be at least $N$?
Ana draws a checkered board that has at least 20 rows and at least 24 columns. Then, Beto must completely cover that board, without holes or overlaps, using only pieces of the following two types:
Each piece must cover exactly 4 or 3 squares of the board, as shown in the figure, without leaving the board.
It is permitted to rotate the pieces and it is not necessary to use all types of pieces.
Explain why, regardless of how many rows and how many columns Ana's board has, Beto can always complete his task.
Given an integer $n\geq 2,$ colour red exactly $n$ cells of an infinite sheet of grid paper. A rectangular grid array is called special if it contains at least two red opposite corner cells; single red cells and 1-row or 1-column grid arrays whose end-cells are both red are special. Given a configuration of exactly $n$ red cells, let $N$ be the largest number of red cells a special rectangular grid array may contain. Determine the least value $N$ may take over all possible configurations of exactly $n$ red cells
A man disposes of sufficiently many metal bars of length $2$ and wants to construct a grill of the shape of an $n \times n$ unit net. He is allowed to fold up two bars at an endpoint or to cut a bar into two equal pieces, but two bars may not overlap or intersect. What is the minimum number of pieces he must use?
Let $a$ and $b$ be positive integers. The cells of an $(a+b+1)\times (a+b+1)$ grid are colored amber and bronze such that there are at least $a^2+ab-b$ amber cells and at least $b^2+ab-a$ bronze cells. Prove that it is possible to choose $a$ amber cells and $b$ bronze cells such that no two of the $a+b$ chosen cells lie in the same row or column.
In a 2025 by 2025 grid, every cell initially contains a `1'. Every minute, we simultaneously replace the number in each cell with the sum of numbers in the cells that share an edge with it. (For example, after the first minute, the number 2 is written in each of the four
corner cells.)
After 2025 minutes, we colour the board in checkerboard fashion, such that the top left corner is black. Find the difference between the sum of numbers in black cells and the sum of numbers in white cells.
[i]Proposed by chorn[/i]
Petya and Vasya live in neighboring houses (see the plan in the figure). Vasya lives in the fourth entrance. It is known that Petya runs to Vasya by the shortest route (it is not necessary walking along the sides of the cells) and it does not matter from which side he runs around his house. Determine in which entrance he lives Petya .
[img]https://cdn.artofproblemsolving.com/attachments/b/1/741120341a54527b179e95680aaf1c4b98ff84.png[/img]
In an $N \times N$ table consisting of small unit squares, some squares are coloured black and the other squares are coloured white. For each pair of columns and each pair of rows, the four squares on the intersections of these rows and columns must not all be of the same colour. What is the largest possible value of $N$?
Let $n$ be an integer greater than $1$. In how many ways can we fill all the numbers $1, 2,..., 2n$ in the boxes of a grid of $2\times n$, one in each box, so that any two consecutive numbers are they in squares that share one side of the grid?
Positive integers $m, n$ are such that $mn$ is divisible by $9$ but not divisible by $27$. Rectangle $m \times n$ is cut into corners, each consisting of three cells. There are four types of such corners, depending on their orientation; you can see them on the figure below. Could it happen that the number of corners of each type was the exact square of some positive integer?
[i]Proposed by Oleksiy Masalitin[/i]
[img]https://i.ibb.co/Y8QSHyf/Kyiv-MO-2023-10-4.png[/img]
Consider all pairs of distinct points on the Cartesian plane $(A, B)$ with integer coordinates. Among these pairs of points, find all for which there exist two distinct points $(X, Y)$ with integer coordinates, such that the quadrilateral $AXBY$ is convex and inscribed.
[i]Proposed by Anton Trygub[/i]
Let $n$ be an odd positive integer and consider an $n \times n$ chessboard of $n^2$ unit squares. In some of the cells of the chessboard, we place a knight. A knight in a cell $c$ is said to [i]attack [/i] a cell $c'$ if the distance between the centers of $c$ and $c'$ is exactly $\sqrt{5}$ (in particular, a knight does not attack the cell which it occupies).
Suppose each cell of the board is attacked by an even number of knights (possibly zero). Show that the configuration of knights is symmetric with respect to all four axes of symmetry of the board (i.e. the configuration of knights is both horizontally and vertically symmetric, and also unchanged by reflection along either diagonal of the chessboard).
[i]NIkolai Beluhov[/i]
Suppose a grid with $2m$ rows and $2n$ columns is given, where $m$ and $n$ are positive integers. You may place one pawn on any square of this grid, except the bottom left one or the top right one. After placing the pawn, a snail wants to undertake a journey on the grid. Starting from the bottom left square, it wants to visit every square exactly once, except the one with the pawn on it, which the snail wants to avoid. Moreover, it wants to fi nish in the top right square. It can only move horizontally or vertically on the grid.
On which squares can you put the pawn for the snail to be able to finish its journey?
In an $n$ by $n$ grid, each cell is filled with an integer between $1$ and $6$. The outmost cells all contain the number $1$, and any two cells that share a vertex has difference not equal to $3$. For any vertex $P$ inside the grid (not including the boundary), there are $4$ cells that have $P$ has a vertex. If these four cells have exactly three distinct numbers $i$, $j$, $k$ (two cells have the same number), and the two cells with the same number have a common side, we call $P$ an $ijk$-type vertex. Let there be $A_{ijk}$ vertices that are $ijk$-type. Prove that $A_{123}\equiv A_{246} \pmod 2$.
Let $n{}$ be a natural number. The playing field for a "Master Sudoku" is composed of the $n(n+1)/2$ cells located on or below the main diagonal of an $n\times n$ square. A teacher secretly selects $n{}$ cells of the playing field and tells his student
[list]
[*]the number of selected cells on each row, and
[*]that there is one selected cell on each column.
[/list]The teacher's selected cells form a Master Sudoku if his student can determine them with the given information. How many Master Sudokus are there?
[i]Proposed by T. Amdeberkhan, M. Ruby and F. Petrov[/i]
Let $n \ge 2$ be a positive integer. An $n\times n$ grid of squares has been colored as a chessboard. Let a [i]move[/i] consist of picking a square from the board and then changing the colors to the opposite for all squares that lie in the same row as the chosen square, as well as for all squares that lie in the same column (the chosen square itself is also changed to the opposite color). Find all values of $n$ for which it is possible to make all squares of the grid be the same color in a finite sequence of moves.