Found problems: 622
John and Mary play the following game. First they choose integers $n > m > 0$ and put $n$ sweets on an empty table. Then they start to make moves alternately. A move consists of choosing a nonnegative integer $k\le m$ and taking $k$ sweets away from the table (if $k = 0$ , nothing happens in fact). In doing so no value for $k$ can be chosen more than once (by none of the players) or can be greater than the number of sweets at the table at the moment of choice. The game is over when one of the players can make no more moves.
John and Mary decided that at the beginning Mary chooses the numbers $m$ and $n$ and then John determines whether the performer of the last move wins or looses. Can Mary choose $m$ and $n$ in such way that independently of John’s decision she will be able to win?
A board consists of $2021 \times 2021$ squares all of which are white, except for one corner square which is black. Alma and Bertha play the following game. At the beginning, there is a piece on the black square. In each turn, the player must move the piece to a new square in the same row or column as the one in which the piece is currently. All squares that the piece moves across, including the ending square but excluding the starting square, must be white, and all squares that the piece moves across, including the ending square, become black by this move. Alma begins, and the first player unable to move loses. Which player may prepare a strategy which secures her the victory?
[img]https://cdn.artofproblemsolving.com/attachments/a/7/270d82f37b729bfe661f8a92cea8be67e5625c.png[/img]
A hunter and an invisible rabbit play a game on an infinite square grid. First the hunter fixes a colouring of the cells with finitely many colours. The rabbit then secretly chooses a cell to start in. Every minute, the rabbit reports the colour of its current cell to the hunter, and then secretly moves to an adjacent cell that it has not visited before (two cells are adjacent if they share an edge). The hunter wins if after some finite time either:[list][*]the rabbit cannot move; or
[*]the hunter can determine the cell in which the rabbit started.[/list]Decide whether there exists a winning strategy for the hunter.
[i]Proposed by Aron Thomas[/i]
Mugdho and Dipto play a game on a numbered row of $n \geq 5$ squares. At the beginning, a pebble is put on the first square and then the players make consecutive moves; Mugdho starts. During a move a player is allowed to choose one of the following:
[list]
[*] move the pebble one square rightward
[*] move the pebble four squares rightward
[*] move the pebble two squares leftward
[/list]
All of the possible moves are only allowed if the pebble stays within the borders of the square row. The player who moves the pebble to the last square (a. k. a $n$-th) wins. Determine for which values of $n$ each of the players has a winning strategy.
A positive integer $a$ is selected, and some positive integers are written on a board. Alice and Bob play the following game. On Alice's turn, she must replace some integer $n$ on the board with $n+a$, and on Bob's turn he must replace some even integer $n$ on the board with $n/2$. Alice goes first and they alternate turns. If on his turn Bob has no valid moves, the game ends.
After analyzing the integers on the board, Bob realizes that, regardless of what moves Alice makes, he will be able to force the game to end eventually. Show that, in fact, for this value of $a$ and these integers on the board, the game is guaranteed to end regardless of Alice's or Bob's moves.
Turbo the snail sits on a point on a circle with circumference $1$. Given an infinite sequence of positive real numbers $c_1, c_2, c_3, \dots$, Turbo successively crawls distances $c_1, c_2, c_3, \dots$ around the circle, each time choosing to crawl either clockwise or counterclockwise.
Determine the largest constant $C > 0$ with the following property: for every sequence of positive real numbers $c_1, c_2, c_3, \dots$ with $c_i < C$ for all $i$, Turbo can (after studying the sequence) ensure that there is some point on the circle that it will never visit or crawl across.
Three numbered tiles are arranged in a tray as shown:
[img]https://cdn.artofproblemsolving.com/attachments/d/0/d449364f92b7fae971fd348a82bafd25aa8ea1.jpg[/img]
Show that we cannot interchange the $1$ and the $3$ by a sequence of moves where we slide a tile to the adjacent vacant space.
For any integer $n\geq 2$, we compute the integer $h(n)$ by applying the following procedure to its decimal representation. Let $r$ be the rightmost digit of $n$.
[list][*]If $r=0$, then the decimal representation of $h(n)$ results from the decimal representation of $n$ by removing this rightmost digit $0$.
[*]If $1\leq r \leq 9$ we split the decimal representation of $n$ into a maximal right part $R$ that solely consists of digits not less than $r$ and into a left part $L$ that either is empty or ends with a digit strictly smaller than $r$. Then the decimal representation of $h(n)$ consists of the decimal representation of $L$, followed by two copies of the decimal representation of $R-1$. For instance, for the number $17,151,345,543$, we will have $L=17,151$, $R=345,543$ and $h(n)=17,151,345,542,345,542$.[/list]
Prove that, starting with an arbitrary integer $n\geq 2$, iterated application of $h$ produces the integer $1$ after finitely many steps.
[i]Proposed by Gerhard Woeginger, Austria[/i]
The expression $1\oplus2\oplus3\oplus4\oplus5\oplus6\oplus7\oplus8\oplus9$ is written on a blackboard. Bill and Peter play the following game. They replace $\oplus$ by $+$ or $\cdot$, making their moves in turn, and one of them can use only $+$, while the other one can use only $\cdot$. At the beginning, Bill selects the sign he will use, and he tries to make the result an even number. Peter tries to make the result an odd number. Prove that Peter can always win.
[hide=Original Wording]The expression $1*2*3*4*5*6*7*8*9$ is written on a blackboard. Bill and Peter play the following game. They replace $*$ by $+$ or $\cdot$, making their moves in turn, and one of them can use only $+$, while the other one can use only $\cdot$. At the beginning Bill selects the sign he will use, and he tries to make the result an even number. Peter tries to make the result an odd number. Prove that Peter can always win.[/hide]
Let $m$ and $n$ be fixed positive integers. Tsvety and Freyja play a game on an infinite grid of unit square cells. Tsvety has secretly written a real number inside of each cell so that the sum of the numbers within every rectangle of size either $m$ by $n$ or $n$ by $m$ is zero. Freyja wants to learn all of these numbers.
One by one, Freyja asks Tsvety about some cell in the grid, and Tsvety truthfully reveals what number is written in it. Freyja wins if, at any point, Freyja can simultaneously deduce the number written in every cell of the entire infinite grid (If this never occurs, Freyja has lost the game and Tsvety wins).
In terms of $m$ and $n$, find the smallest number of questions that Freyja must ask to win, or show that no finite number of questions suffice.
[i]Nikolai Beluhov[/i]
Isaak and Jeremy play the following game.
Isaak says to Jeremy that he thinks a few $2^n$ integers $k_1,..,k_{2^n}$.
Jeremy asks questions of the form: ''Is it true that $k_i<k_j$ ?'' in which Isaak answers by always telling the truth.
After $n2^{n-1}$ questions, Jeramy must decide whether numbers of Isaak are all distinct each other or not.
Prove that Jeremy has bo way to be ''sure'' for his final decision.
(UK)
In a football tournament there are n teams, with ${n \ge 4}$, and each pair of teams meets exactly once. Suppose that, at the end of the tournament, the final scores form an arithmetic sequence where each team scores ${1}$ more point than the following team on the scoreboard. Determine the maximum possible score of the lowest scoring team, assuming usual scoring for football games (where the winner of a game gets ${3}$ points, the loser ${0}$ points, and if there is a tie both teams get ${1}$ point).
There are $n$ coins in a row. Two players take turns picking a coin and flipping it. The location of the heads and tails should not repeat. Loses the one who can not make a move. Which of player can always win, no matter how his opponent plays?
$200$ soldiers occupy in a rectangle (military call it a square and educated military a carree): $20$ men (per row) times $10$ men (per column). In each row, we consider the tallest man (if some are of equal height, choose any of them) and of the $10$ men considered we select the shortest (if some are of equal height, choose any of them). Call him $A$. Next the soldiers assume their initial positions and in each column the shortest soldier is selected, of these $20$, the tallest is chosen. Call him $B$. Two colonels bet on which of the two soldiers chosen by these two distinct procedures is taller: $A$ or $B$. Which colonel wins the bet?
The integers $1, 2, 3, 4, 5$ and $6$ are written on a board. You can perform the following kind of move: select two of the numbers, say $a$ and $b$, such that $4a - 2b$ is nonnegative; erase $a$ and $b$, then write down $4a - 2b$ on the board (hence replacing two of the numbers by just one). Continue performing such moves until only one number remains on the board. What is the smallest possible positive value of this last remaining number?
Vlad draws 100 rays in the Euclidean plane. David then draws a line $\ell$ and pays Vlad one pound for each ray that $\ell$ intersects. Naturally, David wants to pay as little as possible. What is the largest amount of money that Vlad can get from David?
[i]Proposed by Vlad Spătaru[/i]
Let $n$ be a given positive integer. Sisyphus performs a sequence of turns on a board consisting of $n + 1$ squares in a row, numbered $0$ to $n$ from left to right. Initially, $n$ stones are put into square $0$, and the other squares are empty. At every turn, Sisyphus chooses any nonempty square, say with $k$ stones, takes one of these stones and moves it to the right by at most $k$ squares (the stone should say within the board). Sisyphus' aim is to move all $n$ stones to square $n$.
Prove that Sisyphus cannot reach the aim in less than
\[ \left \lceil \frac{n}{1} \right \rceil + \left \lceil \frac{n}{2} \right \rceil + \left \lceil \frac{n}{3} \right \rceil + \dots + \left \lceil \frac{n}{n} \right \rceil \]
turns. (As usual, $\lceil x \rceil$ stands for the least integer not smaller than $x$. )
We have $105$ coins, among which we know that there are three fake ones. Authentic coins have all the same weight, which is greater than that of the false ones, which also have the same weight. Determine from can $26$ authentic coins be selected by weighing only two in one two pan balance.
Let $n$ be a positive integer. Two players $A$ and $B$ play a game in which they take turns choosing positive integers $k \le n$. The rules of the game are:
(i) A player cannot choose a number that has been chosen by either player on any previous turn.
(ii) A player cannot choose a number consecutive to any of those the player has already chosen on any previous turn.
(iii) The game is a draw if all numbers have been chosen; otherwise the player who cannot choose a number anymore loses the game.
The player $A$ takes the first turn. Determine the outcome of the game, assuming that both players use optimal strategies.
[i]Proposed by Finland[/i]
Let $n$ be a given positive integer. Sisyphus performs a sequence of turns on a board consisting of $n + 1$ squares in a row, numbered $0$ to $n$ from left to right. Initially, $n$ stones are put into square $0$, and the other squares are empty. At every turn, Sisyphus chooses any nonempty square, say with $k$ stones, takes one of these stones and moves it to the right by at most $k$ squares (the stone should say within the board). Sisyphus' aim is to move all $n$ stones to square $n$.
Prove that Sisyphus cannot reach the aim in less than
\[ \left \lceil \frac{n}{1} \right \rceil + \left \lceil \frac{n}{2} \right \rceil + \left \lceil \frac{n}{3} \right \rceil + \dots + \left \lceil \frac{n}{n} \right \rceil \]
turns. (As usual, $\lceil x \rceil$ stands for the least integer not smaller than $x$. )
Let \( m \) and \( n \) be positive integers. Kellem and Carmen play the following game: initially, the number $0$ is on the board. Starting with Kellem and alternating turns, they add powers of \( m \) to the previous number on the board, such that the new value on the board does not exceed \( n \). The player who writes \( n \) wins. Determine, for each pair \( (m, n) \), who has the winning strategy.
[b]Note:[/b] A power of \( m \) is a number of the form \( m^k \), where \( k \) is a non-negative integer.
John and James wish to divide $25$ coins, of denominations $1, 2, 3, \ldots , 25$ kopeks. In each move, one of them chooses a coin, and the other player decides who must take this coin. John makes the initial choice of a coin, and in subsequent moves, the choice is made by the player having more kopeks at the time. In the event that there is a tie, the choice is made by the same player in the preceding move. After all the coins have been taken, the player with more kokeps wins. Which player has a winning strategy?
[i](6 points)[/i]
At the beginning of a two-player game, the number $2004!$ is written on the blackboard. The players move alternately. In each move, a positive integer smaller than the number on the blackboard and divisible by at most $20$ different prime numbers is chosen. This is subtracted from the number on the blackboard, which is erased and replaced by the difference. The winner is the player who obtains $0$. Does the player who goes first or the one who goes second have a guaranteed win, and how should that be achieved?
Let $n$ be a positive integer. Two players $A$ and $B$ play a game in which they take turns choosing positive integers $k \le n$. The rules of the game are:
(i) A player cannot choose a number that has been chosen by either player on any previous turn.
(ii) A player cannot choose a number consecutive to any of those the player has already chosen on any previous turn.
(iii) The game is a draw if all numbers have been chosen; otherwise the player who cannot choose a number anymore loses the game.
The player $A$ takes the first turn. Determine the outcome of the game, assuming that both players use optimal strategies.
[i]Proposed by Finland[/i]
Let $n$ be a given positive integer. Sisyphus performs a sequence of turns on a board consisting of $n + 1$ squares in a row, numbered $0$ to $n$ from left to right. Initially, $n$ stones are put into square $0$, and the other squares are empty. At every turn, Sisyphus chooses any nonempty square, say with $k$ stones, takes one of these stones and moves it to the right by at most $k$ squares (the stone should say within the board). Sisyphus' aim is to move all $n$ stones to square $n$.
Prove that Sisyphus cannot reach the aim in less than
\[ \left \lceil \frac{n}{1} \right \rceil + \left \lceil \frac{n}{2} \right \rceil + \left \lceil \frac{n}{3} \right \rceil + \dots + \left \lceil \frac{n}{n} \right \rceil \]
turns. (As usual, $\lceil x \rceil$ stands for the least integer not smaller than $x$. )