Found problems: 41
2024 ELMO Problems, 5
In triangle $ABC$ with $AB<AC$ and $AB+AC=2BC$, let $M$ be the midpoint of $\overline{BC}$. Choose point $P$ on the extension of $\overline{BA}$ past $A$ and point $Q$ on segment $\overline{AC}$ such that $M$ lies on $\overline{PQ}$. Let $X$ be on the opposite side of $\overline{AB}$ from $C$ such that $\overline{AX} \parallel \overline{BC}$ and $AX=AP=AQ$. Let $\overline{BX}$ intersect the circumcircle of $BMQ$ again at $Y \neq B$, and let $\overline{CX}$ intersect the circumcircle of $CMP$ again at $Z \neq C$. Prove that $A$, $Y$, and $Z$ are collinear.
[i]Tiger Zhang[/i]
2005 Colombia Team Selection Test, 6
$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]
2019 Belarus Team Selection Test, 3.3
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$. )
2019 Switzerland - Final Round, 4
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$. )
2019 Philippine TST, 1
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$. )
2019 India IMO Training Camp, P3
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$. )
2004 IMO Shortlist, 5
$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]
2023 USA EGMO Team Selection Test, 6
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]
2023 All-Russian Olympiad, 4
There is a queue of $n{}$ girls on one side of a tennis table, and a queue of $n{}$ boys on the other side. Both the girls and the boys are numbered from $1{}$ to $n{}$ in the order they stand. The first game is played by the girl and the boy with the number $1{}$ and then, after each game, the loser goes to the end of their queue, and the winner remains at the table. After a while, it turned out that each girl played exactly one game with each boy. Prove that if $n{}$ is odd, then a girl and a boy with odd numbers played in the last game.
[i]Proposed by A. Gribalko[/i]
2011 USA TSTST, 4
Acute triangle $ABC$ is inscribed in circle $\omega$. Let $H$ and $O$ denote its orthocenter and circumcenter, respectively. Let $M$ and $N$ be the midpoints of sides $AB$ and $AC$, respectively. Rays $MH$ and $NH$ meet $\omega$ at $P$ and $Q$, respectively. Lines $MN$ and $PQ$ meet at $R$. Prove that $OA\perp RA$.
2012 IMO, 3
The [i]liar's guessing game[/i] is a game played between two players $A$ and $B$. The rules of the game depend on two positive integers $k$ and $n$ which are known to both players.
At the start of the game $A$ chooses integers $x$ and $N$ with $1 \le x \le N.$ Player $A$ keeps $x$ secret, and truthfully tells $N$ to player $B$. Player $B$ now tries to obtain information about $x$ by asking player $A$ questions as follows: each question consists of $B$ specifying an arbitrary set $S$ of positive integers (possibly one specified in some previous question), and asking $A$ whether $x$ belongs to $S$. Player $B$ may ask as many questions as he wishes. After each question, player $A$ must immediately answer it with [i]yes[/i] or [i]no[/i], but is allowed to lie as many times as she wants; the only restriction is that, among any $k+1$ consecutive answers, at least one answer must be truthful.
After $B$ has asked as many questions as he wants, he must specify a set $X$ of at most $n$ positive integers. If $x$ belongs to $X$, then $B$ wins; otherwise, he loses. Prove that:
1. If $n \ge 2^k,$ then $B$ can guarantee a win.
2. For all sufficiently large $k$, there exists an integer $n \ge (1.99)^k$ such that $B$ cannot guarantee a win.
[i]Proposed by David Arthur, Canada[/i]
2019 Brazil Team Selection Test, 3
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$. )
2019 Macedonia National Olympiad, 5
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$. )
2019 Hong Kong TST, 3
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$. )
2018 IMO Shortlist, C3
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$. )
2024 All-Russian Olympiad, 3
Yuri is looking at the great Mayan table. The table has $200$ columns and $2^{200}$ rows. Yuri knows that each cell of the table depicts the sun or the moon, and any two rows are different (i.e. differ in at least one column). Each cell of the table is covered with a sheet. The wind has blown aways exactly two sheets from each row. Could it happen that now Yuri can find out for at least $10000$ rows what is depicted in each of them (in each of the columns)?
[i]Proposed by I. Bogdanov, K. Knop[/i]