Olympiad problems

2013 Dutch IMO TST, 4

Let $n \ge 3$ be an integer, and consider a $n \times n$-board, divided into $n^2$ unit squares. For all $m \ge 1$, arbitrarily many $1\times m$-rectangles (type I) and arbitrarily many $m\times 1$-rectangles (type II) are available. We cover the board with $N$ such rectangles, without overlaps, and such that every rectangle lies entirely inside the board. We require that the number of type I rectangles used is equal to the number of type II rectangles used.(Note that a $1 \times 1$-rectangle has both types.) What is the minimal value of $N$ for which this is possible?

2024 Rioplatense Mathematical Olympiad, 1

Tags: combinatorics , board , rioplatense , grid

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.

2022 May Olympiad, 1

Tags: coloring , combinatorics , board

In a $7\times7$ board, some squares are painted red. Let $a$ be the number of rows that have an odd number of red squares and let $b$ be the number of columns that have an odd number of red squares. Find all possible values of $a+b$. For each value found, give a example of how the board can be painted.

Kvant 2020, M2595

Tags: game , board , combinatorics

Kolya and Dima play a game on an $8\times 8$ board, making moves in turn. During his turn, Kolya must put one cross in any empty cell (i.e., in a cell in which a cross has not yet been drawn and which has not yet been covered with a domino). Dima must cover two adjacent cells with a domino (which are not yet covered with other dominoes), in which there are an even number of crosses in total (0 or 2). The one who can't make a move loses. Which of does the player have a winning strategy, if [list=a] [*]Dima makes the first move? [*]Kolya makes the first move? [/list] [i]Proposed by M. Didin[/i]

2020 Lusophon Mathematical Olympiad, 5

Tags: board , combinatorics

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$?

2015 Rioplatense Mathematical Olympiad, Level 3, 4

Tags: combinatorics , board , coloring

You have a $9 \times 9$ board with white squares. A tile can be moved from one square to another neighbor (tiles that share one side). If we paint some squares of black, we say that such coloration is [i]good [/i] if there is a white square where we can place a chip that moving through white squares can return to the initial square having passed through at least $3$ boxes, without passing the same square twice. Find the highest possible value of $k$ such that any form of painting $k$ squares of black are a [i]good [/i] coloring.

2024 May Olympiad, 5

Tags: combinatorics , board

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]

2019 Belarusian National Olympiad, 11.8

Tags: board , combinatorics

At each node of the checkboard $n\times n$ board, a beetle sat. At midnight, each beetle crawled into the center of a cell. It turned out that the distance between any two beetles sitting in the adjacent (along the side) nodes didn't increase. Prove that at least one beetle crawled into the center of a cell at the vertex of which it sat initially. [i](A. Voidelevich)[/i]

2022 JBMO Shortlist, C6

Tags: combinatorics , board , shortlist

Let $n \ge 2$ be an integer. In each cell of a $4n \times 4n$ table we write the sum of the cell row index and the cell column index. Initially, no cell is colored. A move consists of choosing two cells which are not colored and coloring one of them in red and one of them in blue. Show that, however Alex perfors $n^2$ moves, Jane can afterwards perform a number of moves (eventually none) after which the sum of the numbers written in the red cells is the same as the sum of the numbers written in the blue ones.

2017 Bosnia and Herzegovina Junior BMO TST, 4

Tags: combinatorics , board , positioned , maximum

In each cell of $5 \times 5$ table there is one number from $1$ to $5$ such that every number occurs exactly once in every row and in every column. Number in one column is [i]good positioned[/i] if following holds: - In every row, every number which is left from [i]good positoned[/i] number is smaller than him, and every number which is right to him is greater than him, or vice versa. - In every column, every number which is above from [i]good positoned[/i] number is smaller than him, and every number which is below to him is greater than him, or vice versa. What is maximal number of good positioned numbers that can occur in this table?

2024 Brazil Undergrad MO, 3

Tags: combinatorics , board , coloring

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?

2022 Azerbaijan JBMO TST, C5?

Tags: shortlist , combinatorics , coloring , board

Alice and Bob play a game together as a team on a $100 \times 100$ board with all unit squares initially white. Alice sets up the game by coloring exactly $k$ of the unit squares red at the beginning. After that, a legal move for Bob is to choose a row or column with at least $10$ red squares and color all of the remaining squares in it red. What is the smallest $k$ such that Alice can set up a game in such a way that Bob can color the entire board red after finitely many moves? Proposed by [i]Nikola Velov, Macedonia[/i]

2021 Brazil National Olympiad, 2

Tags: combinatorics , board

Let $n$ be a positive integer. On a $2 \times 3 n$ board, we mark some squares, so that any square (marked or not) is adjacent to at most two other distinct marked squares (two squares are adjacent when they are distinct and have at least one vertex in common, i.e. they are horizontal, vertical or diagonal neighbors; a square is not adjacent to itself). (a) What is the greatest possible number of marked square? (b) For this maximum number, in how many ways can we mark the squares? configurations that can be achieved through rotation or reflection are considered distinct.

Kvant 2020, M2614

Tags: combinatorics , board

In an $n\times n$ table, it is allowed to rearrange rows, as well as rearrange columns. Asterisks are placed in some $k{}$ cells of the table. What maximum $k{}$ for which it is always possible to ensure that all the asterisks are on the same side of the main diagonal (and that there are no asterisks on the main diagonal itself)? [i]Proposed by P. Kozhevnikov[/i]

2024 Junior Balkan Team Selection Tests - Romania, P5

Tags: combinatorics , board

An [i]$n$-type triangle[/i] where $n\geqslant 2$ is formed by the cells of a $(2n+1)\times(2n+1)$ board, situated under both main diagonals. For instance, a $3$-type triangle looks like this:[img]https://i.ibb.co/k4fmwWY/Screenshot-2024-07-31-153932.png[/img]Determine the maximal length of a sequence with pairwise distinct cells in an $n$-type triangle, such that, beggining with the second one, any cell of the sequence has a common side with the previous one. [i]Cristi Săvescu[/i]

2022/2023 Tournament of Towns, P4

Tags: combinatorics , board

Let $n>1$ be an integer. A rook stands in one of the cells of an infinite chessboard that is initially all white. Each move of the rook is exactly $n{}$ cells in a single direction, either vertically or horizontally, and causes the $n{}$ cells passed over by the rook to be painted black. After several such moves, without visiting any cell twice, the rook returns to its starting cell, with the resulting black cells forming a closed path. Prove that the number of white cells inside the black path gives a remainder of $1{}$ when divided by $n{}$.

1995 Mexico National Olympiad, 6

Tags: board , combinatorics

A $1$ or $0$ is placed on each square of a $4 \times 4$ board. One is allowed to change each symbol in a row, or change each symbol in a column, or change each symbol in a diagonal (there are $14$ diagonals of lengths $1$ to $4$). For which arrangements can one make changes which end up with all $0$s?

2012 Lusophon Mathematical Olympiad, 2

Tags: board , combinatorics

Maria has a board of size $n \times n$, initially with all the houses painted white. Maria decides to paint black some houses on the board, forming a mosaic, as shown in the figure below, as follows: she paints black all the houses from the edge of the board, and then leaves white the houses that have not yet been painted. Then she paints the houses on the edge of the next remaining board again black, and so on. a) Determine a value of $n$ so that the number of black houses equals $200$. b) Determine the smallest value of $n$ so that the number of black houses is greater than $2012$.

2018 Bosnia and Herzegovina Team Selection Test, 4

Tags: combinatorics , board , maximum , absolute value

Every square of $1000 \times 1000$ board is colored black or white. It is known that exists one square $10 \times 10$ such that all squares inside it are black and one square $10 \times 10$ such that all squares inside are white. For every square $K$ $10 \times 10$ we define its power $m(K)$ as an absolute value of difference between number of white and black squares $1 \times 1$ in square $K$. Let $T$ be a square $10 \times 10$ which has minimum power among all squares $10 \times 10$ in this board. Determine maximal possible value of $m(T)$

2017 Lusophon Mathematical Olympiad, 5

Tags: board , combinatorics

The unit cells of a 5 x 5 board are painted with 5 colors in a way that every cell is painted by exactly one color and each color is used in 5 cells. Show that exists at least one line or one column of the board in which at least 3 colors were used.

2007 Peru Iberoamerican Team Selection Test, P4

Tags: combinatorics , board , table

Each of the squares on a $15$×$15$ board has a zero. At every step you choose a row or a column, we delete all the numbers from it and then we write the numbers from $1$ to $15$ in the empty cells, in an arbitrary order. find the sum possible maximum of the numbers on the board that can be achieved after a number finite number of steps.

2017 OMMock - Mexico National Olympiad Mock Exam, 2

Tags: combinatorics , board , game , triangle

Alice and Bob play on an infinite board formed by equilateral triangles. In each turn, Alice first places a white token on an unoccupied cell, and then Bob places a black token on an unoccupied cell. Alice's goal is to eventually have $k$ white tokens on a line. Determine the maximum value of $k$ for which Alice can achieve this no matter how Bob plays. [i]Proposed by Oriol Solé[/i]

2021/2022 Tournament of Towns, P3

Tags: combinatorics , board

In a checkered square of size $2021\times 2021$ all cells are initially white. Ivan selects two cells and paints them black. At each step, all the cells that have at least one black neighbor by side are painted black simultaneously. Ivan selects the starting two cells so that the entire square is painted black as fast as possible. How many steps will this take? [i]Ivan Yashchenko[/i]

2024 Dutch BxMO/EGMO TST, IMO TSTST, 4

Tags: rotation , board , combinatorics

Let $n$ be a positive with $n\geq 3$. Consider a board of $n \times n$ boxes. In each step taken the colors of the $5$ boxes that make up the figure bellow change color (black boxes change to white and white boxes change to black) The figure can be rotated $90°, 180°$ or $270°$. Firstly, all the boxes are white.Determine for what values of $n$ it can be achieved, through a series of steps, that all the squares on the board are black.

1996 Estonia National Olympiad, 5

Tags: table , combinatorics , board

Three children wanted to make a table-game. For that purpose they wished to enumerate the $mn$ squares of an $m \times n$ game-board by the numbers $1, ... ,mn$ in such way that the numbers $1$ and $mn$ lie in the corners of the board and the squares with successive numbers have a common edge. The children agreed to place the initial square (with number $1$) in one of the corners but each child wanted to have the final square (with number $mn$ ) in different corner. For which numbers $m$ and $n$ is it possible to satisfy the wish of any of the children?