Found problems: 19
2022 Korea Winter Program Practice Test, 3
Let $n\ge 3$ be a positive integer. Amy wrote all the integers from $1$ to $n^2$ on the $n\times n$ grid, so that each cell contains exactly one number. For $i=1,2,\cdots ,n^2-1$, the cell containing $i$ shares a common side with the cell containing $i+1$. Each turn, Bred can choose one cell, and check what number is written. Bred wants to know where $1$ is written by less than $3n$ turns. Determine whether $n$ such that Bred can always achieve his goal is infinite.
2000 Saint Petersburg Mathematical Olympiad, 11.6
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]
2013 USAJMO, 2
Each cell of an $m\times n$ board is filled with some nonnegative integer. Two numbers in the filling are said to be [i]adjacent[/i] if their cells share a common side. (Note that two numbers in cells that share only a corner are not adjacent). The filling is called a [i]garden[/i] if it satisfies the following two conditions:
(i) The difference between any two adjacent numbers is either $0$ or $1$.
(ii) If a number is less than or equal to all of its adjacent numbers, then it is equal to $0$.
Determine the number of distinct gardens in terms of $m$ and $n$.
2000 Saint Petersburg Mathematical Olympiad, 10.5
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]
2024 Rioplatense Mathematical Olympiad, 1
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.
the 14th XMO, P4
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$.
2004 Canada National Olympiad, 2
How many ways can $ 8$ mutually non-attacking rooks be placed on the $ 9\times9$ chessboard (shown here) so that all $ 8$ rooks are on squares of the same color?
(Two rooks are said to be attacking each other if they are placed in the same row or column of the board.)
[asy]unitsize(3mm);
defaultpen(white);
fill(scale(9)*unitsquare,black);
fill(shift(1,0)*unitsquare);
fill(shift(3,0)*unitsquare);
fill(shift(5,0)*unitsquare);
fill(shift(7,0)*unitsquare);
fill(shift(0,1)*unitsquare);
fill(shift(2,1)*unitsquare);
fill(shift(4,1)*unitsquare);
fill(shift(6,1)*unitsquare);
fill(shift(8,1)*unitsquare);
fill(shift(1,2)*unitsquare);
fill(shift(3,2)*unitsquare);
fill(shift(5,2)*unitsquare);
fill(shift(7,2)*unitsquare);
fill(shift(0,3)*unitsquare);
fill(shift(2,3)*unitsquare);
fill(shift(4,3)*unitsquare);
fill(shift(6,3)*unitsquare);
fill(shift(8,3)*unitsquare);
fill(shift(1,4)*unitsquare);
fill(shift(3,4)*unitsquare);
fill(shift(5,4)*unitsquare);
fill(shift(7,4)*unitsquare);
fill(shift(0,5)*unitsquare);
fill(shift(2,5)*unitsquare);
fill(shift(4,5)*unitsquare);
fill(shift(6,5)*unitsquare);
fill(shift(8,5)*unitsquare);
fill(shift(1,6)*unitsquare);
fill(shift(3,6)*unitsquare);
fill(shift(5,6)*unitsquare);
fill(shift(7,6)*unitsquare);
fill(shift(0,7)*unitsquare);
fill(shift(2,7)*unitsquare);
fill(shift(4,7)*unitsquare);
fill(shift(6,7)*unitsquare);
fill(shift(8,7)*unitsquare);
fill(shift(1,8)*unitsquare);
fill(shift(3,8)*unitsquare);
fill(shift(5,8)*unitsquare);
fill(shift(7,8)*unitsquare);
draw(scale(9)*unitsquare,black);[/asy]
2019 Canada National Olympiad, 3
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.
2022 Pan-American Girls' Math Olympiad, 1
Leticia has a $9\times 9$ board. She says that two squares are [i]friends[/i] is they share a side, if they are at opposite ends of the same row or if they are at opposite ends of the same column. Every square has $4$ friends on the board. Leticia will paint every square one of three colors: green, blue or red. In each square a number will be written based on the following rules:
- If the square is green, write the number of red friends plus twice the number of blue friends.
- If the square is red, write the number of blue friends plus twice the number of green friends.
- If the square is blue, write the number of green friends plus twice the number of red friends.
Considering that Leticia can choose the coloring of the squares on the board, find the maximum possible value she can obtain when she sums the numbers in all the squares.
2023 ISI Entrance UGB, 5
There is a rectangular plot of size $1 \times n$. This has to be covered by three types of tiles - red, blue and black. The red tiles are of size $1 \times 1$, the blue tiles are of size $1 \times 1$ and the black tiles are of size $1 \times 2$. Let $t_n$ denote the number of ways this can be done. For example, clearly $t_1 = 2$ because we can have either a red or a blue tile. Also $t_2 = 5$ since we could have tiled the plot as: two red tiles, two blue tiles, a red tile on the left and a blue tile on the right, a blue tile on the left and a red tile on the right, or a single black tile.
[list=a]
[*]Prove that $t_{2n+1} = t_n(t_{n-1} + t_{n+1})$ for all $n > 1$.
[*]Prove that $t_n = \sum_{d \ge 0} \binom{n-d}{d}2^{n-2d}$ for all $n >0$.
[/list]
Here,
\[ \binom{m}{r} = \begin{cases}
\dfrac{m!}{r!(m-r)!}, &\text{ if $0 \le r \le m$,} \\
0, &\text{ otherwise}
\end{cases}\]
for integers $m,r$.
2021 Olympic Revenge, 4
On a chessboard, Po controls a white queen and plays, in alternate turns, against an invisible black king (there are only those two pieces on the board). The king cannot move to a square where he would be in check, neither capture the queen. Every time the king makes a move, Po receives a message from beyond that tells which direction the king has moved (up, right, up-right, etc). His goal is to make the king unable to make a movement.
Can Po reach his goal with at most $150$ moves, regardless the starting position of the pieces?
2022 IMO, 6
Let $n$ be a positive integer. A [i]Nordic[/i] square is an $n \times n$ board containing all the integers from $1$ to $n^2$ so that each cell contains exactly one number. Two different cells are considered adjacent if they share a common side. Every cell that is adjacent only to cells containing larger numbers is called a [i]valley[/i]. An [i]uphill path[/i] is a sequence of one or more cells such that:
(i) the first cell in the sequence is a valley,
(ii) each subsequent cell in the sequence is adjacent to the previous cell, and
(iii) the numbers written in the cells in the sequence are in increasing order.
Find, as a function of $n$, the smallest possible total number of uphill paths in a Nordic square.
Author: Nikola Petrović
2017 AIME Problems, 11
Consider arrangements of the $9$ numbers $1, 2, 3, \dots, 9$ in a $3 \times 3$ array. For each such arrangement, let $a_1$, $a_2$, and $a_3$ be the medians of the numbers in rows $1$, $2$, and $3$ respectively, and let $m$ be the median of $\{a_1, a_2, a_3\}$. Let $Q$ be the number of arrangements for which $m = 5$. Find the remainder when $Q$ is divided by $1000$.
2017 Junior Balkan Team Selection Tests - Moldova, Problem 8
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?
2024 USEMO, 6
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]
2022 USAJMO, 2
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.
2024 Olympic Revenge, 2
Davi and George are taking a city tour through Fortaleza, with Davi initially leading. Fortaleza is organized like an $n \times n$ grid. They start in one of the grid's squares and can move from one square to another adjacent square via a street (for each pair of neighboring squares on the grid, there is a street connecting them). Some streets are dangerous. If Davi or George pass through a dangerous street, they get scared and swap who is leading the city tour. Their goal is to pass through every block of Fortaleza exactly once. However, if the city tour ends with George in command, the entire world becomes unemployed and everyone starves to death. Given that there is at least one street that is not dangerous, prove that Davi and George can achieve their goal without everyone dying of hunger.
2022 IMO Shortlist, C8
Let $n$ be a positive integer. A [i]Nordic[/i] square is an $n \times n$ board containing all the integers from $1$ to $n^2$ so that each cell contains exactly one number. Two different cells are considered adjacent if they share a common side. Every cell that is adjacent only to cells containing larger numbers is called a [i]valley[/i]. An [i]uphill path[/i] is a sequence of one or more cells such that:
(i) the first cell in the sequence is a valley,
(ii) each subsequent cell in the sequence is adjacent to the previous cell, and
(iii) the numbers written in the cells in the sequence are in increasing order.
Find, as a function of $n$, the smallest possible total number of uphill paths in a Nordic square.
Author: Nikola Petrović
2022 USAMO, 1
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.