Problem 1.1: Yousif has a $13 \times 9$ board, such that $7$ random cells are colored black and the rest of the squares ($110$) are colored white. In each move Yousif chooses a $2 \times 2$ square inside the board and switches each of its $4$ cells (from black to white or from white to black). Can the board be completely colored white after a finite number of moves?

Problem 1.2 Hamoody and Abdulkareem play a game. Hamoody writes $37$ distinct positive integers on the board such that their sum is less than $1000$. Then Abdulkareem walks in. Hamoody wins if Abdulkareem can’t find two numbers written on the board that add up to $37$, otherwise Abdulkareem wins. Which player has a winning strategy and why?

Problem 1.3 How many ways are there to form a word containing $k$ letters only using letters ‘a’ and ‘b’, such that after each letter ‘a’ there is at least one letter ‘b’ directly after it? Solve the problem for:

• (a) $k = 4$
• (b) $k = 5$
• (c) $k \ge 6$

Problem 2.1 A convex polygon $P$ lies strictly inside another convex polygon $Q$. Prove that the perimeter of $Q$ is greater than the perimeter of $P$.

Problem 2.2 Miseed and Moath play a game. The numbers from $1$ to $100$ are written on the board. Moath then erases $k$ numbers from the board. Then Miseed walks in. Miseed wins if he can find $k$ numbers on the board that add up to $100$, otherwise Moath wins. Who has a winning strategy for:

• (a) $k = 9$
• (b) $k = 8$ and why?

Problem 2.3 Ahmed and Amer play a game on a $6 \times 6$ board. Initially all the cells are colored white, then Amer picks $k$ cells and colors them black. Then Ahmed walks in. Ahmed wins if he can find $4$ black squares that form the corners of a rectangle or a square (as shown in the figure below), otherwise Amer wins. Who has a winning strategy for:

• (a) $k = 16$
• (b) $k = 17$ and why?

Problem 3.1 Tournament of Towns Junior A-Level Fall 2005. Omar starts with an $8 \times 8$ board and places a rook on each cell. Step by step, Omar removes a rook if it attacks an odd number of other rooks. What is the maximal number of rooks that can be removed by Omar?

Problem 3.2 Several checkers are placed on a board. Each turn, a checker may jump diagonally over an adjacent piece if the opposite square is empty. If a checker is jumped over in this way, it is removed from the board. Is it possible to make a sequence of such jumps to remove all but one checker from the board shown below?

Problem 3.3 MOSP 2007. In an $n \times n$ square, each of the numbers $1, 2, \dots, n$ appear exactly $n$ times. Show that there is a row or column that contains at least $\sqrt{n}$ distinct numbers.

Problem 4.1 Can the vertices of a regular $30$-gon be labeled with numbers $1, 2, \dots, 30$ in such a way that the sum of labels of every pair of neighboring vertices is a perfect square?

Problem 4.2 Denote $A_n$ as the number of strings of length $n$ only using letters ‘a’ and ‘b’, such that neither ‘aabb’ nor ‘bbaa’ appears. Denote $B_n$ as the number of strings of length $n$ only using letters ‘a’ and ‘b’, such that ‘aba’ doesn’t appear. Prove that $A_n = 2B_n - 1$.

Problem 4.3 A rectangle $R$ is tiled with rectangles such that each of these rectangle has an integer side. Prove that $R$ also has an integer side.

Problem 5.1 Elyas and Lukasz play a game on a $2n \times 2n$ board. Elyas covers the board by dominos. Then Lukasz walks in. Lukasz wins if he can cut the board into two parts by a straight line that doesn’t cut any domino, otherwise Elyas wins. Who has a winning strategy for:

• (a) $n = 2$
• (b) $n \ge 4$
• (c) $n = 3$ and why?

Problem 5.2 Find the number of sets $(a_1, a_2, \dots, a_n)$ such that $a_i \in \mathbb{Z}$ and $0 \le a_1 \le a_2 \le \dots \le a_n \le m$.

Problem 5.3 Cono Sur 2011. Let $Q$ be a $(2n+1) \times (2n+1)$ board. Some of its cells are colored black in such a way that every $2 \times 2$ board of $Q$ contains at most $2$ black cells. Find the maximum amount of black cells that the board may have.

Problem 6.1 Safwat places a knight onto an $8 \times 8$ board. Then Smbat moves the knight. Then Safwat makes a move, but he may not place it on a square visited before, and so on. The loser is the one who cannot move. Who has a winning strategy and why?

Problem 6.2 Tournament of Towns 1988. An infinite chessboard has the shape of the first quadrant. Is it possible to write a positive integer into each square, such that each row and each column contains each positive integer exactly once?

Problem 6.3 Czech-Polish-Slovak Match 2018. In a $2 \times 3$ rectangle there is a poly-line of length $36$, which can have self-intersections. Show that there exists a line parallel to two sides of the rectangle, which intersects the other two sides and intersects the poly-line in fewer than $10$ points.

Problem 7.1 Tournament of Towns Junior A-Level Spring 2002. Dominik and Nikola play a game on a $99 \times 99$ board. Dominik controls two white chips in the bottom left and top right corners. Nikola controls two black chips in the bottom right and top left corners. The players move alternately (Dominik starts). In each move, a player moves one of his chips to an adjacent square (by side). Dominik wins if he can make his two white chips adjacent (by side). Can Nikola prevent Dominik from winning?

Problem 7.2 Tournament of Towns Junior A-Level Fall 2001. Let $n \ge 3$ be an integer. Each row in an $(n-2) \times n$ array consists of the numbers $1, 2, \dots, n$ in some order, and the numbers in each column are all different. Prove that this array can be expanded into an $n \times n$ array such that each row and each column consists of the numbers $1, 2, \dots, n$.

Problem 7.3 Romania JBMO TST 2011. We consider an $n \times n$ ($n \ge 2$) grid. Determine all the values of $k \in \mathbb{N}$ for which we can write a real number in each square such that the sum of the $n^2$ numbers is positive, while the sum of the numbers from any $k \times k$ square is negative.

Problem 8.1 Consider an $n \times n$ staircase, which consists of the squares on or below the main diagonal of an $n \times n$ grid. A path is a sequence of distinct squares, every two consecutive of which share an edge. What is the minimum number of paths that an $n \times n$ staircase can be partitioned into?

Problem 8.2 Over half of the squares of a $7 \times 7$ board are occupied by rooks. Prove that there is a rook that is ‘encircled’ (there is a rook attacking it from each of the four directions).

Problem 8.3 Can three faces of an $8 \times 8 \times 8$ cube having a common vertex be covered with $64$ $1 \times 3$ strips (The strips can be folded along the edges of the cube)?

Problem 9.1 Tournament of Towns Junior A-Level Spring 2001. Several non-intersecting diagonals divide a convex polygon into triangles. At each vertex the number of triangles adjacent to it is written. Can you always reconstruct all the diagonals using these numbers if the diagonals are erased?

Problem 9.2 Tournament of Towns Junior A-Level Fall 2001. Dusan places a rook on any square of an empty $8 \times 8$ chessboard. Then he places additional rooks one rook at a time, each attacking an odd number of rooks which are already on the board. What is the maximum number of rooks Dusan can place on the chessboard?

Problem 9.3 In an $n \times n$ grid, at least $2n$ squares are marked. Prove that there is a sequence $P_1, P_2, \dots, P_k$ of centers of marked squares such that the segments $P_i P_{i+1}$ alternate between horizontal and vertical for all $1 \le i \le k$ where $P_{k+1} = P_1$.

Problem 10.1 In the three dimensional lattice plane nine points are marked. Prove that the midpoint of the segment connecting some two of the marked points also lies on the lattice grid.

Problem 10.2 Tournament of Towns Junior A-Level Fall 2013. On a table, there are $11$ piles of $10$ stones each. Marwan and Hamza play the following game. In turns they take $1, 2$ or $3$ stones at a time: Marwan takes stones from any single pile while Hamza takes stones from different piles but no more than one from each. Marwan moves first. The player who cannot move, loses. Which of the players, Marwan or Hamza, has a winning strategy?

Problem 10.3 All Russian Olympiad 2021. Omar and his $99$ students play a game on an infinite cell grid. Omar starts first, then each of the $99$ students makes a move, then Omar and so on. On one move the person can color one unit segment on the grid. A segment cannot be colored twice. Omar wins if, at some moment, there is a $1 \times 2$ or $2 \times 1$ rectangle such that each segment from its border is colored, but the segment between the two adjacent squares isn’t colored. Can Omar guarantee a win?

Problem 11.1 The ‘Minesweeper’ game is played on a $10 \times 10$ board. Some cells have a ‘mine’ placed on them, while in the other cells, there is written a number indicating how many of the neighboring cells (that share a vertex) contain a mine. Prove that if we ‘reverse’ the board (put mines on the cells, where there was no mines initially, and fill the numbers similarly in the cells where were mines) then the sum of numbers in the board will remain the same.

Problem 11.2 On an $8 \times 8$ screen with unit pixels. Initially, there are at least $50$ pixels which are ‘on’. In any $2 \times 2$ square, as soon as there are $3$ pixels which are ‘off’, the fourth pixel turns off automatically. Prove that the whole screen can never be totally ‘off’.

Problem 11.3 AIME 1989. Let $S$ be a subset of $\{1, 2, 3, \dots, 2022\}$ such that no two members of $S$ differ by $4$ or $7$. What is the largest number of elements $S$ can have?

Problem 12.1 The following figure shows a road map connecting $14$ cities. Is there a path passing through each city exactly once?

Problem 12.2 Baltic Way 1998. Can we tile a $13 \times 13$ table from which we remove the central $1 \times 4$ or $4 \times 1$ rectangles?

Problem 12.3 IMO shortlist 1998, Romanian TST 1997. Let $p, q, r$ be distinct prime numbers. Let $A = \{ p^a q^b r^c \mid 0 \le a, b, c \le 7 \}$. Find the least $n \in \mathbb{N}$ such that for any $B \subset A$ where $|B| = n$, has elements $x$ and $y$ such that $x$ divides $y$.

Problem 13.1 A $6 \times 6$ rectangle is tiled by $2 \times 1$ dominoes. Prove that it always has at least one ‘fault-line’, i.e. a line cutting the rectangle without cutting any domino, as shown in the figure below; the red line is the fault-line.

Problem 13.2 Consider an $n \times n$ board with the four corners removed. For which values of $n$ can you cover the board with L-tetrominoes as in the example below?

Problem 13.3 All Russian Olympiad 2010. On an $n \times n$ grid where $n \ge 4$ the main diagonal is colored black, while the rest of the board is colored white. In each move you can reverse the colors of a row or column. Prove that there will always be at least $n$ black cells.

Problem 14.1 Tournament of Towns Senior P-Level Fall 2007. Two players take turns coloring the squares of a $4 \times 4$ grid, one square at the time. A player loses if after his move a $2 \times 2$ square is colored completely. Which of the players has a winning strategy?

Problem 14.2 USAMO 2007. A square grid on the Euclidean plane consists of all points $(m,n)$, where $m$ and $n$ are integers. Is it possible to cover all grid points by an infinite family of discs with non-overlapping interiors if each disc in the family has radius at least $5$?

Problem 14.3 Taiwan TST 2016. There is a grid of equilateral triangles with a distance $1$ between any two neighboring grid points. An equilateral triangle with side length $n$ lies on the grid so that all of its vertices are grid points, and all of its sides match the grid. Now, let us decompose this equilateral triangle into $n^2$ smaller triangles (not necessarily equilateral triangles) so that the vertices of all these smaller triangles are all grid points, and all these small triangles have equal areas. Prove that there are at least $n$ equilateral triangles among these smaller triangles.

Problem 15.1 Vietnam TST 2021. Find the maximum number of cells that can be colored in a $10 \times 10$ board such that each colored cell is adjacent (by vertex) to at most $1$ other colored cell.

Problem 15.2 In a graph $G$, no vertex has degree greater than $n$. Show that one can color the vertices using at most $n+1$ colors, such that no two neighboring vertices are the same color.

Problem 15.3 Czech-Polish-Slovak Match 2018. There are $2018$ players sitting around a round table. At the beginning of the game we arbitrarily deal all the cards from a deck of $K$ cards to the players (some players may receive no cards). In each turn we choose a player who draws one card from each of the two neighbors. It is only allowed to choose a player whose each neighbor holds a nonzero number of cards. The game terminates when there is no such player. Determine the largest possible value of $K$ such that, no matter how we deal the cards and how we choose the players, the game always terminates after a finite number of turns.

Problem 16.1 There are $n$ cars placed around a circular track with enough fuel between them to make a complete loop around the track. Show that there is a car which can make it around the track by collecting the fuel from each car that it passes as it moves.

Problem 16.2 The cells of a $10 \times 10$ board is colored in a standard chessboard coloring. Is it possible to place $10$ rooks on five white and five black cells such that no two rooks attack each other?

Problem 16.3 Given is a $1 \times n$ board with some cells colored black. We call a rectangle consisting of whole cells ‘odd’ if it contains an odd number of black cells. Determine the largest possible number of ‘odd’ rectangles.

Problem 17.1 A $100 \times 100$ board is divided into unit squares. In every square there is an arrow that points up, down, left or right. The board is surrounded by a wall, except for the right side of the top right corner square. An insect is placed in one of the squares. Each second, the insect moves one unit in the direction of the arrow in its square. When the insect moves, the arrow of the square it was in moves $90^\circ$ degrees clockwise. If the indicated movement cannot be done, the insect does not move that second, but the arrow in its squares does move. Is it possible that the insect never leaves the board?

Problem 17.2 All Russian Olympiad 2005. In a $2 \times n$ array we have positive reals such that the sum of the numbers in each of the $n$ columns is $1$. Show that we can select a number in each column such that the sum of the selected numbers in each row is at most $\frac{n+1}{4}$.

Problem 17.3 Prove that the number of domino tilings of an $n \times (n+1)$ rectangle is odd.

Problem 18.1 What is the largest possible size of a subset of $\{1, 2, 3, \dots, 2n\}$ which does not contain two elements with one dividing the other?

Problem 18.2 Eötvös-Kurschák 1967. A convex $n$-gon is divided into triangles by diagonals which do not intersect except at vertices of the $n$-gon. Each vertex belongs to an odd number of triangles. Show that $n$ must be a multiple of $3$.

Problem 18.3 Given are vertices of a regular $2n$-gon. Consider all triangles with vertices in these points. Prove that the total area of all acute triangles is equal to the total area of all obtuse triangles.

Problem 19.1 Prove that a graph is bipartite if and only if all of its cycles have even length.

Problem 19.2 Each edge of an $m \times n$ rectangular grid is oriented with an arrow such that:

• (a) the border is oriented clockwise
• (b) each interior vertex has two arrows coming out of it, and two arrows going into it.

Prove that there is at least one square whose edges are oriented clockwise.

Problem 19.3 EGMO 2016. Let $m$ be a positive integer. Consider a $4m \times 4m$ array of square unit cells. Two different cells are related to each other if they are in either the same row or in the same column. No cell is related to itself. Some cells are coloured blue, such that every cell is related to at least two blue cells. Determine the minimum number of blue cells.

Problem 20.1 Given $7$ lines on the plane, prove that two of them form an angle less than $26^\circ$.

Problem 20.2 Belarus 2005. Prove that it is not possible color the squares of an $11 \times 11$ grid using three colours, such that no four squares whose centres form the vertices of a rectangle with sides parallel to the sides of the grid, have the same colour.

Problem 20.3 USAMO 1999. The Y2K Game is played on a $1 \times 2000$ grid as follows. Two players in turn write either an ‘S’ or an ‘U’ in an empty square. The first player who produces three consecutive boxes that spell ‘SUS’ wins. If all boxes are filled without producing ‘SUS’ then the game is a draw. Prove that the second player has a winning strategy.