Found problems: 1385
$A$ and $B$ play a game, given an integer $N$, $A$ writes down $1$ first, then every player sees the last number written and if it is $n$ then in his turn he writes $n+1$ or $2n$, but his number cannot be bigger than $N$. The player who writes $N$ wins. For which values of $N$ does $B$ win?
[i]Proposed by A. Slinko & S. Marshall, New Zealand[/i]
A magician and his assistant are performing the following trick. There is a row of $13$ empty closed boxes. The magician leaves the room, and a person from the audience hides a coin in each of two boxes of his choice, so that the assistant knows which boxes contain coins. The magician returns and the assistant is allowed to open one box that does not contain a coin. Next, the magician selects four boxes, which are then simultaneously opened. The goal of the magician is to open both boxes that contain coins. Devise a method that will allow the magician and his assistant to always successfully perform the trick.
(Igor Zhizhilkin)
[url=https://artofproblemsolving.com/community/c6h1801447p11962869]junior version posted here[/url]
Kid and Karlsson play a game. Initially they have a square piece of chocolate $2019\times 2019$ grid with $1\times 1$ cells . On every turn Kid divides an arbitrary piece of chololate into three rectanglular pieces by cells, and then Karlsson chooses one of them and eats it. The game finishes when it's impossible to make a legal move. Kid wins if there was made an even number of moves, Karlsson wins if there was made an odd number of moves.
Who has the winning strategy?
[i] (Д. Ширяев)[/i]
[hide=Thanks]Thanks to the user Vlados021 for translating the problem.[/hide]
Three cats--TheInnocentKitten, TheNeutralKitten, and TheGuiltyKitten labelled $P_1, P_2,$ and $P_3$ respectively with $P_{n+3} = P_{n}$--are playing a game with three rounds as follows:
[list=1]
[*] Each round has three turns. For round $r \in \{1,2,3\}$ and turn $t \in \{1,2,3\}$ in that round, player $P_{t+1-r}$ picks a non-negative integer. The turns in each round occur in increasing order of $t$, and the rounds occur in increasing order of $r$.
$\newline
\newline$
[*] [b]Motivations:[/b] Every player focuses primarily on maximizing the sum of their own choices and secondarily on minimizing the total of the other players’ sums. TheNeutralKitten and TheGuiltyKitten have the additional tertiary priority of minimizing TheInnocentKitten’s sum.
$\newline
\newline$
[*] For round $2$, player $P_{2}$ has no choice but to pick the number equal to what player $P_{1}$ chose in round $1$. Likewise, for round $3$, player $P_{3}$ must pick the number equal to what player $P_{2}$ chose in round $2$.
$\newline
\newline$
[*] If not all three players choose their numbers such that the values they chose in rounds 1,2,3 form an arithmetic progression in that order by the end of the game, all players' sums are set to $-1$ regardless of what they have chosen.
$\newline
\newline$
[*] If the sum of the choices in any given round is greater than $100$, all choices that round are set to $0$ at the end of that round. That is, rules $2$, $3$, and $4$ act as if each player chose $0$ that round.
$\newline
\newline$
[*] All players play optimally as per their motivations. Furthermore, all players know that all other players will play optimally (and so on.)
[/list]
Let $A$ and $B$ be TheInnocentKitten's sum and TheGuiltyKitten's sum respectively. Compute $1000A + B$ when all players play optimally.
Proposed by Harry Chen (Extile)
Ana and Bruno have an $8 \times 8$ checkered board. Ana paints each of the $64$ squares with some color. Then Bruno chooses two rows and two columns on the board and looks at the $4$ squares where they intersect. Bruno's goal is for these $4$ squares to be the same color. How many colors, at least, must Ana use so that Bruno can't fulfill his objective? Show how you can paint the board with this amount of colors and explain because if you use less colors then Bruno can always fulfill his goal.
We have two piles with $2000$ and $2017$ coins respectively.
Ann and Bob take alternate turns making the following moves:
The player whose turn is to move picks a pile with at least two coins, removes from that pile $t$ coins for some $2\le t \le 4$, and adds to the other pile $1$ coin. The players can choose a different $t$ at each turn, and the player who cannot make a move loses.
If Ann plays first determine which player has a winning strategy.
The main building of ETH Zurich is a rectangle divided into unit squares. Every side of a square is a wall, with certain walls having doors. The outer wall of the main building has no doors. A number of participants of the SMO have gathered in the main building lost. You can only move from one square to another through doors. We have indicates that there is a walkable path between every two squares of the main building.
Cyril wants the participants to find each other again by having everyone on the same square leads. To do this, he can give them the following instructions via walkie-talkie: North, East, South or West. After each instruction, each participant simultaneously attempts a square in that direction to go. If there is no door in the corresponding wall, he remains standing.
Show that Cyril can reach his goal after a finite number of directions, no matter which one square the participants at the beginning.
[hide=original wording]Das Hauptgebäude der ETH Zürich ist ein in Einheitsquadrate unterteiltes Rechteck. Jede Seite eines Quadrates ist eine Wand, wobei gewisse Wände Türen haben. Die Aussenwand des Hauptgebäudes hat keine Türen. Eine Anzahl von Teilnehmern der SMO hat sich im Hauptgebäude verirrt. Sie können sich nur durch Türen von einem Quadrat zum anderen bewegen. Wir nehmen an, dass zwischen je zwei Quadraten des Hauptgebäudes ein begehbarer Weg existiert.
Cyril möchte erreichen, dass sich die Teilnehmer wieder nden, indem er alle auf dasselbe Quadrat führt. Dazu kann er ihnen per Walkie-Talkie folgende Anweisungen geben: Nord, Ost, Süd oder West. Nach jeder Anweisung versucht jeder Teilnehmer gleichzeitig, ein Quadrat in diese Richtung zu gehen. Falls in der entsprechenden Wand keine Türe ist, bleibt er stehen.
Zeige, dass Cyril sein Ziel nach endlich vielen Anweisungen erreichen kann, egal auf welchen Quadraten sich die Teilnehmer am Anfang benden. [/hide]
On a circle $4n$ points are chosen ($n \ge 1$). The points are alternately colored yellow and blue. The yellow points are divided into $n$ pairs and the points in each pair are connected with a yellow line segment. In the same manner the blue points are divided into $n$ pairs and the points in each pair are connected with a blue segment. Assume that no three of the segments pass through a single point. Show that there are at least $n$ intersection points of blue and yellow segments.
Euhan and Minjune are playing a game. They choose a number $N$ so that they can only say integers up to $N$. Euhan starts by saying the $1$, and each player takes turns saying either $n+1$ or $4n$ (if possible), where $n$ is the last number said. The player who says $N$ wins. What is the smallest number larger than $2019$ for which Minjune has a winning strategy?
[i]Proposed by Janabel Xia[/i]
Sixty-four dice with the numbers ”one” to ”six” are placed on one table and formed into a square with eight horizontal and eight vertical rows of cubes pushed together. By rotating the dice, while maintaining their place, we want to finally have all sixty-four dice the "one" points upwards. Each dice however, may not be turned individually, but only every eight dice in a horizontal or vertical row together by $90^o$ to the longitudinal axis of this row may turn. Prove that it is always possible to solve the dice by repeatedly applying the permitted type of rotation to the required end position.
Let $ m,n\ge 2 $ and consider a rectangle formed by $ m\times n $ unit squares that are colored, either white, or either black. A [i]step[/i] is the action of selecting from it a rectangle of dimensions $ 1\times k, $ where $ k $ is an odd number smaller or equal to $ n, $ or a rectangle of dimensions $ l\times 1, $ where $ l $ is and odd number smaller than $ m, $ and coloring all the unit squares of this chosen rectangle with the color that appears the least in it.
[b]a)[/b] Show that, for any $ m,n\ge 5, $ there exists a succession of [i]steps[/i] that make the rectagle to be single-colored.
[b]b)[/b] What about $ m=n+1=5? $
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]
The numbers $1,2,3,\ldots ,n$ are written in a row. Two players, Maris and Filips, take turns making moves with Maris starting. A move consists of crossing out a number from the row which has not yet been crossed out. The game ends when there are exactly two uncrossed numbers left in the row. If the two remaining uncrossed numbers are coprime, Maris wins, otherwise Filips is the winner. For each positive integer $n\ge 4$ determine which player can guarantee a win.
There are $n$ $(n \ge 3)$ players in a table tennis tournament, in which any two players have a match. Player $A$ is called not out-performed by player $B$, if at least one of player $A$'s losers is not a $B$'s loser.
Determine, with proof, all possible values of $n$, such that the following case could happen: after finishing all the matches, every player is not out-performed by any other player.
The "Sea battle" game.
a) You are trying to find the $4$-field ship -- a rectangle $1x4$, situated on the $7x7$ playing board. You are allowed to ask a question, whether it occupies the particular field or not. How many questions is it necessary to ask to find that ship surely?
b) The same question, but the ship is a connected (i.e. its fields have common sides) set of $4$ fields.
There is $207$ boxes on the table which numbered $1,2, \dots , 207$ respectively. Firstly Aslı puts a red ball in each of the $100$ boxes that she chooses and puts a white ball in each of the remaining ones. After that Zehra, writes a pair $(i,j)$ on the blackboard such that $1\leq i \leq j \leq 207$. Finally, Aslı tells Zehra that for every pair; whether the color of the balls which is inside the box which numbered by these numbers are the same or not. Find the least possible value of $N$ such that Zehra can guarantee finding all colors that has been painted to balls in each of the boxes with writing $N$ pairs on the blackboard.
A [i]Nim-style game[/i] is defined as follows. Two positive integers $k$ and $n$ are specified, along with a finite set $S$ of $k$-tuples of integers (not necessarily positive). At the start of the game, the $k$-tuple $(n, 0, 0, ..., 0)$ is written on the blackboard.
A legal move consists of erasing the tuple $(a_1,a_2,...,a_k)$ which is written on the blackboard and replacing it with $(a_1+b_1, a_2+b_2, ..., a_k+b_k)$, where $(b_1, b_2, ..., b_k)$ is an element of the set $S$. Two players take turns making legal moves, and the first to write a negative integer loses. In the event that neither player is ever forced to write a negative integer, the game is a draw.
Prove that there is a choice of $k$ and $S$ with the following property: the first player has a winning strategy if $n$ is a power of 2, and otherwise the second player has a winning strategy.
[i]Proposed by Linus Hamilton[/i]
Agustín and Lucas, by turns, each time mark a box that has not yet been marked on a $101\times 101$ grid board. Augustine starts the game. You cannot check a box that already has two checked boxes in its row or column. The one who can't make his move loses. Decide which of the two players has a winning strategy.
Players $A$ and $B$ play the following game: $A$ tosses a coin $n$ times, and $B$ does $n+1$ times. The player who obtains more ”heads” wins; or in the case of equal balances, $A$ is assigned victory. Find the values of $n$ for which this game is fair (i.e. both players have equal chances for victory).
Azambuja writes a rational number $q$ on a blackboard. One operation is to delete $q$ and replace it by $q+1$; or by $q-1$; or by $\frac{q-1}{2q-1}$ if $q \neq \frac{1}{2}$. The final goal of Azambuja is to write the number $\frac{1}{2018}$ after performing a finite number of operations.
[b]a)[/b] Show that if the initial number written is $0$, then Azambuja cannot reach his goal.
[b]b)[/b] Find all initial numbers for which Azambuja can achieve his goal.
A positive integer is written on a blackboard. Players $A$ and $B$ play the following game: in each move one has to choose a proper divisor $m$ of the number $n$ written on the blackboard ($1<m<n$) and replaces $n$ with $n-m$. Player $A$ makes the first move, then players move alternately. The player who can't make a move loses the game. For which starting numbers is there a winning strategy for player $B$?
Pikachu, Charmander, and Vulpix are three of the four equally-skilled players in a Pokemon bracket tournament. Because they are equally skilled, whenever any two of the players battle, they are equally likely to win. In the bracket tournament, the four players are randomly paired into two rounds, each round consisting of two players. The winners of the first two rounds then play each other in the final round. The winner of the final match ranks first; the loser of the final round ranks second; and the two losers of the previous rounds jointly rank third. What is the probability that Charmander plays Vulpix in a round, but ranks lower than Pikachu?
$\textbf{(A) }\dfrac1{24}\qquad\textbf{(B) }\dfrac18\qquad\textbf{(C) }\dfrac13\qquad\textbf{(D) } \dfrac38 \qquad \textbf{(E) } \dfrac12$
There are $ 2016 $ positions marked around a circle, with a token on one of them. A legitimate move is to move the token either 1 position or 4 positions from its location, clockwise. The restriction is that the token can not occupy the same position more than once. Players $ A $ and $ B $ take turns making moves. Player $ A $ has the first move. The first player who cannot make a legitimate move loses. Determine which of the two players has a winning strategy.
Two players $A$ and $B$ play the following game. Before the game starts, $A$ chooses 1000 not necessarily different odd primes, and then $B$ chooses half of them and writes them on a blackboard. In each turn a player chooses a positive integer $n$, erases some primes $p_1$, $p_2$, $\dots$, $p_n$ from the blackboard and writes all the prime factors of $p_1 p_2 \dotsm p_n - 2$ instead (if a prime occurs several times in the prime factorization of $p_1 p_2 \dotsm p_n - 2$, it is written as many times as it occurs). Player $A$ starts, and the player whose move leaves the blackboard empty loses the game. Prove that one of the two players has a winning strategy and determine who.
Remark: Since 1 has no prime factors, erasing a single 3 is a legal move.
Anselmo and Claudio are playing alternatively a game with fruits in a box. The box initially has $32$ fruits. Anselmo plays first and each turn consists of taking away $1$, $2$ or $3$ fruits from the box or taking away $\frac{2}{3}$ of the fruits from the box (this is only possible when the number of the fruits left in the box is a multiple of $3$). The player that takes away the last fruit from the box wins. Which of these two players has a winning strategy? How should that player play in order to win?