Olympiad problems

2023 Indonesia MO, 3

A natural number $n$ is written on a board. On every step, Neneng and Asep changes the number on the board with the following rule: Suppose the number on the board is $X$. Initially, Neneng chooses the sign up or down. Then, Asep will pick a positive divisor $d$ of $X$, and replace $X$ with $X+d$ if Neneng chose the sign "up" or $X-d$ if Neneng chose "down". This procedure is then repeated. Asep wins if the number on the board is a nonzero perfect square, and loses if at any point he writes zero. Prove that if $n \geq 14$, Asep can win in at most $(n-5)/4$ steps.

2019 Olympic Revenge, 4

Tags: 3D geometry , icosahedron , combinatorics , game , Game Theory , game strategy

A regular icosahedron is a regular solid of $20$ faces, each in the form of an equilateral triangle, with $12$ vertices, so that each vertex is in $5$ edges. Twelve indistinguishable candies are glued to the vertices of a regular icosahedron (one at each vertex), and four of these twelve candies are special. André and Lucas want to together create a strategy for the following game: • First, André is told which are the four special sweets and he must remove exactly four sweets that are not special from the icosahedron and leave the solid on a table, leaving afterwards without communicating with Lucas. • Later, Sponchi, who wants to prevent Lucas from discovering the special sweets, can pick up the icosahedron from the table and rotate it however he wants. • After Sponchi makes his move, he leaves the room, Lucas enters and he must determine the four special candies out of the eight that remain in the icosahedron. Determine if there is a strategy for which Lucas can always properly discover the four special sweets.

2010 Rioplatense Mathematical Olympiad, Level 3, 3

Tags: combinatorics , game , game strategy , Game Theory

Alice and Bob play the following game. To start, Alice arranges the numbers $1,2,\ldots,n$ in some order in a row and then Bob chooses one of the numbers and places a pebble on it. A player's [i]turn[/i] consists of picking up and placing the pebble on an adjacent number under the restriction that the pebble can be placed on the number $k$ at most $k$ times. The two players alternate taking turns beginning with Alice. The first player who cannot make a move loses. For each positive integer $n$, determine who has a winning strategy.

2019 Romania Team Selection Test, 3

Tags: combinatorics , game , game strategy , Game Theory

Alice and Bob play the following game. To start, Alice arranges the numbers $1,2,\ldots,n$ in some order in a row and then Bob chooses one of the numbers and places a pebble on it. A player's [i]turn[/i] consists of picking up and placing the pebble on an adjacent number under the restriction that the pebble can be placed on the number $k$ at most $k$ times. The two players alternate taking turns beginning with Alice. The first player who cannot make a move loses. For each positive integer $n$, determine who has a winning strategy.

2024 Auckland Mathematical Olympiad, 7

Tags: Game Theory

There are $20$ points marked on a circle. Two players take turns drawing chords with ends at marked points that do not intersect the already drawn chords. The one who cannot make the next move loses. Who can secure their win?

2009 Bosnia Herzegovina Team Selection Test, 1

Tags: induction , combinatorics unsolved , combinatorics , Game Theory , Bosnia , 2009

Given an $1$ x $n$ table ($n\geq 2$), two players alternate the moves in which they write the signs + and - in the cells of the table. The first player always writes +, while the second always writes -. It is not allowed for two equal signs to appear in the adjacent cells. The player who can’t make a move loses the game. Which of the players has a winning strategy?

2019 Kosovo Team Selection Test, 1

Tags: combinatorics , Game Theory , Combinatorial games

There are 2019 cards in a box. Each card has a number written on one of its sides and a letter on the other side. Amy and Ben play the following game: in the beginning Amy takes all the cards, places them on a line and then she flips as many cards as she wishes. Each time Ben touches a card he has to flip it and its neighboring cards. Ben is allowed to have as many as 2019 touches. Ben wins if all the cards are on the numbers' side, otherwise Amy wins. Determine who has a winning strategy.

2024 Indonesia MO, 4

Tags: Game Theory , Integers , combinatorics , number theory , Inamo

Kobar and Borah are playing on a whiteboard with the following rules: They start with two distinct positive integers on the board. On each step, beginning with Kobar, each player takes turns changing the numbers on the board, either from $P$ and $Q$ to $2P-Q$ and $2Q-P$, or from $P$ and $Q$ to $5P-4Q$ and $5Q-4P$. The game ends if a player writes an integer that is not positive. That player is declared to lose, and the opponent is declared the winner. At the beginning of the game, the two numbers on the board are $2024$ and $A$. If it is known that Kobar does not lose on his first move, determine the largest possible value of $A$ so that Borah can win this game.

2016 Bundeswettbewerb Mathematik, 2

Tags: geometry , geometry unsolved , area of a triangle , area , Game Theory

A triangle $ABC$ with area $1$ is given. Anja and Bernd are playing the following game: Anja chooses a point $X$ on side $BC$. Then Bernd chooses a point $Y$ on side $CA$ und at last Anja chooses a point $Z$ on side $AB$. Also, $X,Y$ and $Z$ cannot be a vertex of triangle $ABC$. Anja wants to maximize the area of triangle $XYZ$ and Bernd wants to minimize that area. What is the area of triangle $XYZ$ at the end of the game, if both play optimally?

2016 Germany Team Selection Test, 3

Tags: Game Theory , game , Integer , number theory , combinatorics

In the beginning there are $100$ integers in a row on the blackboard. Kain and Abel then play the following game: A [i]move[/i] consists in Kain choosing a chain of consecutive numbers; the length of the chain can be any of the numbers $1,2,\dots,100$ and in particular it is allowed that Kain only chooses a single number. After Kain has chosen his chain of numbers, Abel has to decide whether he wants to add $1$ to each of the chosen numbers or instead subtract $1$ from of the numbers. After that the next move begins, and so on. If there are at least $98$ numbers on the blackboard that are divisible by $4$ after a move, then Kain has won. Prove that Kain can force a win in a finite number of moves.

2018 Iran Team Selection Test, 2

Tags: combinatorics , Iran , Iranian TST , game strategy , game , Game Theory

Mojtaba and Hooman are playing a game. Initially Mojtaba draws $2018$ vectors with zero sum. Then in each turn, starting with Mojtaba, the player takes a vector and puts it on the plane. After the first move, the players must put their vector next to the previous vector (the beginning of the vector must lie on the end of the previous vector). At last, there will be a closed polygon. If this polygon is not self-intersecting, Mojtaba wins. Otherwise Hooman. Who has the winning strategy? [i]Proposed by Mahyar Sefidgaran, Jafar Namdar [/i]

2018 Belarusian National Olympiad, 11.8

Tags: combinatorics , Game Theory

The vertices of the regular $n$-gon are marked. Two players play the following game: they, in turn, select a vertex and connect it by a segment to either the adjacent vertex or the center of the $n$-gon. The winner is a player if after his move it is possible to get any vertex from any other vertex moving along segments. For each integer $n\geqslant 3$ determine who has a winning strategy.

2024 Mexico National Olympiad, 6

Tags: combinatorics , Game Theory

Ana and Beto play on a blackboard where all integers from 1 to 2024 (inclusive) are written. On each turn, Ana chooses three numbers $a,b,c$ written on the board and then Beto erases them and writes one of the following numbers: $$a+b-c, a-b+c, ~\text{or}~ -a+b+c.$$ The game ends when only two numbers are left on the board and Ana cannot play. If the sum of the final numbers is a multiple of 3, Beto wins. Otherwise, Ana wins. ¿Who has a winning strategy?

2024 Iran MO (3rd Round), 2

Tags: table , combinatorics , cells , game strategy , Game Theory

Two intelligent people playing a game on the $1403 \times 1403$ table with $1403^2$ cells. The first one in each turn chooses a cell that didn't select before and draws a vertical line segment from the top to the bottom of the cell. The second person in each turn chooses a cell that didn't select before and draws a horizontal line segment from the left to the right of the cell. After $1403^2$ steps the game will be over. The first person gets points equal to the longest verticals line segment and analogously the second person gets point equal to the longest horizonal line segment. At the end the person who gets the more point will win the game. What will be the result of the game?

Russian TST 2018, P2

Tags: combinatorics , Iran , Iranian TST , game strategy , game , Game Theory

Mojtaba and Hooman are playing a game. Initially Mojtaba draws $2018$ vectors with zero sum. Then in each turn, starting with Mojtaba, the player takes a vector and puts it on the plane. After the first move, the players must put their vector next to the previous vector (the beginning of the vector must lie on the end of the previous vector). At last, there will be a closed polygon. If this polygon is not self-intersecting, Mojtaba wins. Otherwise Hooman. Who has the winning strategy? [i]Proposed by Mahyar Sefidgaran, Jafar Namdar [/i]

2001 Saint Petersburg Mathematical Olympiad, 9.1

Tags: combinatorics , Combinatorial games , game , Game Theory , board , domino , Coloring

All the cells of a $10\times10$ board are colored white initially. Two players are playing a game with alternating moves. A move consists of coloring any un-colored cell black. A player is considered to loose, if after his move no white domino is left. Which of the players has a winning strategy? [I]Proposed by A. Khrabrov[/i]

2022 Cono Sur, 4

Tags: combinatorics , Game Theory

Ana and Beto play on a grid of $2022 \times 2022$. Ana colors the sides of some squares on the board red, so that no square has two red sides that share a vertex. Next, Bob must color a blue path that connects two of the four corners of the board, following the sides of the squares and not using any red segments. If Beto succeeds, he is the winner, otherwise Ana wins. Who has a winning strategy?

2016 Regional Competition For Advanced Students, 3

Tags: Austria , Game Theory

On the occasion of the 47th Mathematical Olympiad 2016 the numbers 47 and 2016 are written on the blackboard. Alice and Bob play the following game: Alice begins and in turns they choose two numbers $a$ and $b$ with $a > b$ written on the blackboard, whose difference $a-b$ is not yet written on the blackboard and write this difference additionally on the board. The game ends when no further move is possible. The winner is the player who made the last move. Prove that Bob wins, no matter how they play. (Richard Henner)

2018 European Mathematical Cup, 4

Tags: combinatorics , Game Theory

Let $n$ be a positive integer. Ana and Banana are playing the following game: First, Ana arranges $2n$ cups in a row on a table, each facing upside-down. She then places a ball under a cup and makes a hole in the table under some other cup. Banana then gives a finite sequence of commands to Ana, where each command consists of swapping two adjacent cups in the row. Her goal is to achieve that the ball has fallen into the hole during the game. Assuming Banana has no information about the position of the hole and the position of the ball at any point, what is the smallest number of commands she has to give in order to achieve her goal?

2015 Indonesia MO Shortlist, C9

Tags: combinatorics , Game Theory

Given 2015 balls. Astri and Budi will play a game. At first, Astri will choose two different numbers $a$ and $b$ from the set $S = \{ 1, 2, 3, \dots, 30 \}$. Budi will then choose another 2 different numbers $c$ and $d$ from the remaining 28 numbers in set $S$. By taking turns, starting from Astri, they take balls with the following rules: (1) Astri could only take $a$ or $b$ balls. (2) Budi could only take $c$ or $d$ balls. until someone couldn't take any balls satisfying the condition given (and that person will lose). Prove that Budi could choose $c,d$ such that he has a strategy to ensure his victory on this game.

2008 South East Mathematical Olympiad, 3

Tags: combinatorics unsolved , combinatorics , Game Theory , Trees

Captain Jack and his pirate men plundered six chests of treasure $(A_1,A_2,A_3,A_4,A_5,A_6)$. Every chest $A_i$ contains $a_i$ coins of gold, and all $a_i$s are pairwise different $(i=1,2,\cdots ,6)$. They place all chests according to a layout (see the attachment) and start to alternately take out one chest a time between the captain and a pirate who serves as the delegate of the captain’s men. A rule must be complied with during the game: only those chests that are not adjacent to other two or more chests are allowed to be taken out. The captain will win the game if the coins of gold he obtains are not less than those of his men in the end. Let the captain be granted to take chest firstly, is there a certain strategy for him to secure his victory?

Russian TST 2018, P2

Tags: combinatorics , set theory , game , TST , Russian TST , Game Theory

Let $\mathcal{F}$ be a finite family of subsets of some set $X{}$. It is known that for any two elements $x,y\in X$ there exists a permutation $\pi$ of the set $X$ such that $\pi(x)=y$, and for any $A\in\mathcal{F}$ \[\pi(A):=\{\pi(a):a\in A\}\in\mathcal{F}.\]A bear and crocodile play a game. At a move, a player paints one or more elements of the set $X$ in his own color: brown for the bear, green for the crocodile. The first player to fully paint one of the sets in $\mathcal{F}$ in his own color loses. If this does not happen and all the elements of $X$ have been painted, it is a draw. The bear goes first. Prove that he doesn't have a winning strategy.

2000 Slovenia National Olympiad, Problem 4

Tags: Game Theory

A pile of $2000$ coins is given on a table. In each step, we choose a pile with at least three coins, remove one coin from it, and divide the rest of this pile into two piles (not necessarily of the same size). Is it possible that after several steps each pile on the table has exactly three coins?

2010 IFYM, Sozopol, 6

Tags: combinatorics , game strategy , Game Theory

There are 2 pizzerias in a town, with 2010 pizzas each. Two scientists $A$ and $B$ are taking turns ($A$ is first), where on each turn one can eat as many pizzas as he likes from one of the pizzerias or exactly one pizza from each of the two. The one that has eaten the last pizza is the winner. Which one of them is the winner, provided that they both use the best possible strategy?

2025 China Team Selection Test, 10

Tags: combinatorics , Game Theory , Coloring

Given an odd integer $n \geq 3$. Let $V$ be the set of vertices of a regular $n$-gon, and $P$ be the set of all regular polygons formed by points in $V$. For instance, when $n=15$, $P$ consists of $1$ regular $15$-gon, $3$ regular pentagons, and $5$ regular triangles. Initially, all points in $V$ are uncolored. Two players, $A$ and $B$, play a game where they take turns coloring an uncolored point, with player $A$ starting and coloring points red, and player $B$ coloring points blue. The game ends when all points are colored. A regular polygon in $P$ is called $\textit{good}$ if it has more red points than blue points. Find the largest positive integer $k$ such that no matter how player $B$ plays, player $A$ can ensure that there are at least $k$ $\textit{good}$ polygons.