Found problems: 136
Let $n$ be a positive integer. A grid of $n\times n$ has some black-colored cells. Drini can color a cell if at least three cells that share a side with it are also colored black. Drini discovers that by repeating this process, all the cells in the grid can be colored. Prove that if there are initially $k$ colored cells, then $$k\geq \frac{n^2+2n}{3}.$$
Let $n \geq 2$ be an integer. Switzerland and Liechtenstein are performing their annual festive show. There is a field divided into $n \times n$ squares, in which the bottom-left square contains a red house with $k$ Swiss gymnasts, and the top-right square contains a blue house with $k$ Liechtensteiner gymnasts. Every other square only has enough space for a single gymnast at a time. Each second either a Swiss gymnast or a Liechtensteiner gymnast moves. The Swiss gymnasts move to either the square immediately above or to the right and the Liechtensteiner gymnasts move either to the square immediately below or to the left. The goal is to move all the Swiss gymnasts to the blue house and all the Liechtensteiner gymnasts to the red house, with the caveat that a gymnast cannot enter a house until all the gymnasts of the other nationality have left. Determine the largest $k$ in terms of $n$ for which this is possible.
In an $8 \times 8$ grid, $n$ disks, numbered $1$ to $n$ are stacked, with random order, in a pile in the bottom left comer. The disks can be moved one at a time to a neighbouring cell either to the right or top. The aim to move all the disks to the cell at the top right comer and stack them in the order $1,2,...,n$ from the bottom. Each cell, except the bottom left and top right cell, can have at most one disk at any given time. Find the largest value of $n$ so that the aim can be achieved.
A strip consists of $n$ squares which are numerated in their order by integers $1,2,3,..., n$. In the beginning, one square is empty while each remaining square contains one piece. Whenever a square contains a piece and its some neighbouring square contains another piece while the square immediately following the neighbouring square is empty, one may raise the first piece over the second one to the empty square, removing the second piece from the strip.
Find all possibilites which square can be initially empty, if it is possible to reach a state where the strip contains only one piece and
a) $n = 2008$,
b) $n = 2009$.
Given a square grid where the distance between two adjacent grid points is $1$. Can the distance between two grid points be $\sqrt5, \sqrt6, \sqrt7$ or $\sqrt{2007}$ ?
Bethan is playing a game on an $n\times n$ grid consisting of $n^2$ cells. A move consists of placing a counter in an unoccupied cell $C$ where the $2n-2$ other cells in the same row or column as $C$ contain an even number of counters. After making $M$ moves Bethan realises she cannot make any more moves. Determine the minimum value of $M$.
[i]United Kingdom, Sam Bealing[/i]
A frog is located on a unit square of an infinite grid oriented according to the cardinal directions. The frog makes moves consisting of jumping either one or two squares in the direction it is facing, and then turning according to the following rules:
i) If the frog jumps one square, it then turns $90^\circ$ to the right;
ii) If the frog jumps two squares, it then turns $90^\circ$ to the left.
Is it possible for the frog to reach the square exactly $2024$ squares north of the initial square after some finite number of moves if it is initially facing:
a) North;
b) East?
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?
Nine points form a grid of size $3\times 3$. How many triangles are there with $3$ vertices at these points?
Is it possible to write positive integers from $1$ to $2025$ in the cells of a \( 45 \times 45 \) grid such that each number is used exactly once, and at the same time, each written number is either greater than all the numbers located in its side-adjacent cells or smaller than all the numbers located in its side-adjacent cells?
[i]Proposed by Anton Trygub[/i]
Joy has a square board of size $n \times n$. At every step, he colours a cell of the board. He cannot colour any cell more than once. He also counts points while colouring the cells. At first, he has $0$ points. Every step, after colouring a cell $c$, he takes the largest possible set $S$ that creates a "$+$" sign where all cells are coloured and $c$ lies in the centre. Then, he gets the size of set $S$ as points. After colouring the whole $n \times n$ board, what is the maximum possible amount of points he can get?
Let $p$ be a prime number. Determine the largest possible $n$ such that the following holds: it is possible to fill an $n\times n$ table with integers $a_{ik}$ in the $i$th row and $k$th column, for $1\le i,k\le n$, such that for any quadruple $i,j,k,l$ with $1\le i<j\le n$ and $1\le k<l\le n$, the number $a_{ik}a_{jl}-a_{il}a_{jk}$ is not divisible by $p$.
[i]Proposed by oneplusone[/i]
Find the greatest number of depicted pieces composed of $4$ unit squares that can be placed without overlapping on an $n \times n$ grid (where n is a positive integer) in such a way that it is possible to move from some corner to the opposite corner via uncovered squares (moving between squares requires a common edge). The shapes can be rotated and reflected.
[img]https://cdn.artofproblemsolving.com/attachments/b/d/f2978a24fdd737edfafa5927a8d2129eb586ee.png[/img]
Determine the number of paths from $A$ to $B$ on the picture that go along gridlines only, do not pass through any point twice, and never go upwards?
[img]https://cdn.artofproblemsolving.com/attachments/0/2/87868e24a48a2e130fb5039daeb85af42f4b9d.png[/img]
Simon plays a game on an $n\times n$ grid of cells. Initially, each cell is filled with an integer. Every minute, Simon picks a cell satisfying the following:
[list]
[*] The magnitude of the integer in the chosen cell is less than $n^{n^n}$
[*] The sum of all the integers in the neighboring cells (sharing one side with the chosen cell) is non-zero
[/list]
Simon then adds each integer in a neighboring cell to the chosen cell.
Show that Simon will eventually not be able to make any valid moves.
There is an $n \times n$ grid which has rows and columns numbered from $1$ to $n$; the cell at row $i$ and column $j$ is denoted as the cell at $(i, j)$. A subset $A$ of the cells is called [i]good[/i] if for any two cells at $(x_1, y), (x_2, y)$ in $A$, the cells $(u, v)$ satisfying $x_1 < u \leq x_2, v<y$ or $x_1 \leq u < x_2, v>y$ are not in $A$. Determine the minimal number of good sets such that they are pairwise disjoint and every cell of the board belongs to exactly one good set.
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.
Let $a$ and $b$ be two positive integers satifying $gcd(a, b) = 1$. Consider a pawn standing on the grid point $(x, y)$.
A step of type A consists of moving the pawn to one of the following grid points: $(x+a, y+a),(x+a,y-a), (x-a, y + a)$ or $(x - a, y - a)$.
A step of type B consists of moving the pawn to $(x + b,y + b),(x + b,y - b), (x - b,y + b)$ or $(x - b,y - b)$.
Now put a pawn on $(0, 0)$. You can make a ( nite) number of steps, alternatingly of type A and type B, starting with a step of type A. You can make an even or odd number of steps, i.e., the last step could be of either type A or type B.
Determine the set of all grid points $(x,y)$ that you can reach with such a series of steps.
For some positive integer $n$, consider the board $n\times n$. On this board you can put any rectangles with sides along the sides of the grid. What is the smallest number of such rectangles that must be placed so that all the cells of the board are covered by distinct numbers of rectangles (possibly $0$)? The rectangles are allowed to have the same sizes.
[i]Proposed by Anton Trygub[/i]
Find all pairs of positive integers $(m, n)$, such that in a $m \times n$ table (with $m+1$ horizontal lines and $n+1$ vertical lines), a diagonal can be drawn in some unit squares (some unit squares may have no diagonals drawn, but two diagonals cannot be both drawn in a unit square), so that the obtained graph has an Eulerian cycle.
There are $10000$ trees in a park, arranged in a square grid with $100$ rows and $100$ columns. Find the largest number of trees that can be cut down, so that sitting on any of the tree stumps one cannot see any other tree stump.
Determine all integer $n$ such that a surface of an $n \times n \times n$ grid cube can be pasted in one layer by paper $1 \times 2$ rectangles so that each rectangle has exactly five neighbors (by a line segment).
(A.Shapovalov)
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.
Suppose $n$ is odd and each square of an $n \times n$ grid is arbitrarily filled with either by $1$ or by $-1$. Let $r_j$ and $c_k$ denote the product of all numbers in $j$-th row and $k$-th column respectively, $1 \le j, k \le n$. Prove that
$$\sum_{j=1}^{n} r_j+ \sum_{k=1}^{n} c_k\ne 0$$
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.