Found problems: 815
There are 20 people at a party. Each person holds some number of coins. Every minute, each person who has at least 19 coins simultaneously gives one coin to every other person at the party. (So, it is possible that $A$ gives $B$ a coin and $B$ gives $A$ a coin at the same time.) Suppose that this process continues indefinitely. That is, for any positive integer $n$, there exists a person who will give away coins during the $n$th minute. What is the smallest number of coins that could be at the party?
[i]Proposed by Ray Li[/i]
Consider all binary sequences (sequences consisting of 0’s and 1’s). In such a sequence the following four types of operation are allowed: (a) $010 \rightarrow 1$, (b) $1 \rightarrow 010$, (c) $110 \rightarrow 0$, and (d) $0 \rightarrow 110$. Determine if it is possible to obtain the sequence $100...0$ (with $2003$ zeroes) from the sequence $0...01$ (with $2003$ zeroes).
You have some cyan, magenta, and yellow beads on a non-reorientable circle, and you can perform only the following operations:
1. Move a cyan bead right (clockwise) past a yellow bead, and turn the yellow bead magenta.
2. Move a magenta bead left of a cyan bead, and insert a yellow bead left of where the magenta bead ends up.
3. Do either of the above, switching the roles of the words ``magenta'' and ``left'' with those of ``yellow'' and ``right'', respectively.
4. Pick any two disjoint consecutive pairs of beads, each either yellow-magenta or magenta-yellow, appearing somewhere in the circle, and swap the orders of each pair.
5. Remove four consecutive beads of one color.
Starting with the circle: ``yellow, yellow, magenta, magenta, cyan, cyan, cyan'', determine whether or not you can reach
a) ``yellow, magenta, yellow, magenta, cyan, cyan, cyan'',
b) ``cyan, yellow, cyan, magenta, cyan'',
c) ``magenta, magenta, cyan, cyan, cyan'',
d) ``yellow, cyan, cyan, cyan''.
[i]Proposed by Sammy Luo[/i]
Let $ABC$ be a triangle. Let $\theta$ be a fixed angle for which \[\theta<\frac12\min(\angle A,\angle B,\angle C).\]
Points $S_A$ and $T_A$ lie on segment $BC$ such that $\angle BAS_A=\angle T_AAC=\theta$. Let $P_A$ and $Q_A$ be the feet from $B$ and $C$ to $\overline{AS_A}$ and $\overline{AT_A}$ respectively. Then $\ell_A$ is defined as the perpendicular bisector of $\overline{P_AQ_A}$.
Define $\ell_B$ and $\ell_C$ analogously by repeating this construction two more times (using the same value of $\theta$). Prove that $\ell_A$, $\ell_B$, and $\ell_C$ are concurrent or all parallel.
It is considered a regular polygon with $n$ sides, where $n(n>3)$ is an odd number that does not divide by 3. From the vertices of the polygon are arbitrarily chosen $m(0\leq m\leq n)$ vertices that are colored in red and the others in black. A triangle with the vertices at the vertices of the polygon it is considered $monocolor$ ,if all of its vertices are of the same color. Prove that the number of all $monocolor$ isosceles triangles with the vertices at the given polygon ends does not depend on the way of coloring of the vertices of the polygon. Determine the number of all these $monocolor$ isosceles triangles.
Karl starts with $n$ cards labeled $1,2,3,\dots,n$ lined up in a random order on his desk. He calls a pair $(a,b)$ of these cards [i]swapped[/i] if $a>b$ and the card labeled $a$ is to the left of the card labeled $b$. For instance, in the sequence of cards $3,1,4,2$, there are three swapped pairs of cards, $(3,1)$, $(3,2)$, and $(4,2)$.
He picks up the card labeled 1 and inserts it back into the sequence in the opposite position: if the card labeled 1 had $i$ card to its left, then it now has $i$ cards to its right. He then picks up the card labeled $2$ and reinserts it in the same manner, and so on until he has picked up and put back each of the cards $1,2,\dots,n$ exactly once in that order. (For example, the process starting at $3,1,4,2$ would be $3,1,4,2\to 3,4,1,2\to 2,3,4,1\to 2,4,3,1\to 2,3,4,1$.)
Show that, no matter what lineup of cards Karl started with, his final lineup has the same number of swapped pairs as the starting lineup.
Let $ c > 2,$ and let $ a(1), a(2), \ldots$ be a sequence of nonnegative real numbers such that
\[ a(m \plus{} n) \leq 2 \cdot a(m) \plus{} 2 \cdot a(n) \text{ for all } m,n \geq 1,
\]
and $ a\left(2^k \right) \leq \frac {1}{(k \plus{} 1)^c} \text{ for all } k \geq 0.$ Prove that the sequence $ a(n)$ is bounded.
[i]Author: Vjekoslav Kovač, Croatia[/i]
Elisa has $2023$ treasure chests, all of which are unlocked and empty at first. Each day, Elisa adds a new gem to one of the unlocked chests of her choice, and afterwards, a fairy acts according to the following rules:
[list=disc]
[*]if more than one chests are unlocked, it locks one of them, or
[*]if there is only one unlocked chest, it unlocks all the chests.
[/list]
Given that this process goes on forever, prove that there is a constant $C$ with the following property: Elisa can ensure that the difference between the numbers of gems in any two chests never exceeds $C$, regardless of how the fairy chooses the chests to unlock.
Players $A$ and $B$ play a "paintful" game on the real line. Player $A$ has a pot of paint with four units of black ink. A quantity $p$ of this ink suffices to blacken a (closed) real interval of length $p$. In every round, player $A$ picks some positive integer $m$ and provides $1/2^m $ units of ink from the pot. Player $B$ then picks an integer $k$ and blackens the interval from $k/2^m$ to $(k+1)/2^m$ (some parts of this interval may have been blackened before). The goal of player $A$ is to reach a situation where the pot is empty and the interval $[0,1]$ is not completely blackened.
Decide whether there exists a strategy for player $A$ to win in a finite number of moves.
If $a, b, c$ are non-zero reals, prove that $|\frac{b} {a}-\frac{b} {c}|+|\frac{c} {a}-\frac{c}{b}|+|bc+1|>1$.
In the universe of Pi Zone, points are labeled with $2 \times 2$ arrays of positive reals. One can teleport from point $M$ to point $M'$ if $M$ can be obtained from $M'$ by multiplying either a row or column by some positive real. For example, one can teleport from $\left( \begin{array}{cc} 1 & 2 \\ 3 & 4 \end{array} \right)$ to $\left( \begin{array}{cc} 1 & 20 \\ 3 & 40 \end{array} \right)$ and then to $\left( \begin{array}{cc} 1 & 20 \\ 6 & 80 \end{array} \right)$.
A [i]tourist attraction[/i] is a point where each of the entries of the associated array is either $1$, $2$, $4$, $8$ or $16$. A company wishes to build a hotel on each of several points so that at least one hotel is accessible from every tourist attraction by teleporting, possibly multiple times. What is the minimum number of hotels necessary?
[i]Proposed by Michael Kural[/i]
Let $n$ be a positive integer. Tasty and Stacy are given a circular necklace with $3n$ sapphire beads and $3n$ turquoise beads, such that no three consecutive beads have the same color. They play a cooperative game where they alternate turns removing three consecutive beads, subject to the following conditions:
[list]
[*]Tasty must remove three consecutive beads which are turquoise, sapphire, and turquoise, in that order, on each of his turns.
[*]Stacy must remove three consecutive beads which are sapphire, turquoise, and sapphire, in that order, on each of her turns.
[/list]
They win if all the beads are removed in $2n$ turns. Prove that if they can win with Tasty going first, they can also win with Stacy going first.
[i]Yannick Yao[/i]
Cells of a $2000\times2000$ board are colored according to the following rules:
1)At any moment a cell can be colored, if none of its neighbors are colored
2)At any moment a $1\times2$ rectangle can be colored, if exactly two of its neighbors are colored.
3)At any moment a $2\times2$ squared can be colored, if 8 of its neighbors are colored
(Two cells are considered to be neighboring, if they share a common side). Can the entire $2000\times2000$ board be colored?
[I]Proposed by K. Kohas[/i]
A number of signal lights are equally spaced along a one-way railroad track, labeled in oder $ 1,2, \ldots, N, N \geq 2.$ As a safety rule, a train is not allowed to pass a signal if any other train is in motion on the length of track between it and the following signal. However, there is no limit to the number of trains that can be parked motionless at a signal, one behind the other. (Assume the trains have zero length.) A series of $ K$ freight trains must be driven from Signal 1 to Signal $ N.$ Each train travels at a distinct but constant spped at all times when it is not blocked by the safety rule. Show that, regardless of the order in which the trains are arranged, the same time will elapse between the first train's departure from Signal 1 and the last train's arrival at Signal $ N.$
A circle is inscribed in the trapezoid [i]ABCD[/i]. Let [i]K, L, M, N[/i] be the points of tangency of this circle with the diagonals [i]AC[/i] and [i]BD[/i], respectively ([i]K[/i] is between [i]A[/i] and [i]L[/i], and [i]M[/i] is between [i]B[/i] and [i]N[/i]). Given that $AK\cdot LC=16$ and $BM\cdot ND=\frac94$, find the radius of the circle.
[color=red][Moderator edit: A solution of this problem can be found on http://www.ajorza.org/math/mathfiles/scans/belarus.pdf , page 20 (the statement of the problem is on page 6). The author of the problem is I. Voronovich.][/color]
Let $(M,g)$ be an $n$-dimensional complete Riemannian manifold with $n \ge 2$. Suppose $M$ is connected and $\text{Ric} \ge (n-1)g$, where $\text{Ric}$ is the Ricci tensor of $(M,g)$. Denote by $\text{d}g$ the Riemannian measure of $(M,g)$ and by $d(x,y)$ the geodesic distance between $x$ and $y$. Prove that
\[\int_{M \times M} \cos d(x,y) \text{d}g(x)\text{d}g(y) \ge 0.\]
Moreover, equality holds if and only if $(M,g)$ is isometric to the unit round sphere $S^n$.
The numbers $ 1, 2,\ldots, 50 $ are written on a blackboard. Each minute any two numbers are erased and their positive difference is written instead. At the end one number remains. Which values can take this number?
In each cell of an $n\times n$ board is a lightbulb. Initially, all of the lights are off. Each move consists of changing the state of all of the lights in a row or of all of the lights in a column (off lights are turned on and on lights are turned off).
Show that if after a certain number of moves, at least one light is on, then at this moment at least $n$ lights are on.
Several positive integers are written in a row. Iteratively, Alice chooses two adjacent numbers $x$ and $y$ such that $x>y$ and $x$ is to the left of $y$, and replaces the pair $(x,y)$ by either $(y+1,x)$ or $(x-1,x)$. Prove that she can perform only finitely many such iterations.
[i]Proposed by Warut Suksompong, Thailand[/i]
Let $\mathcal{A}$ denote the set of all polynomials in three variables $x, y, z$ with integer coefficients. Let $\mathcal{B}$ denote the subset of $\mathcal{A}$ formed by all polynomials which can be expressed as
\begin{align*}
(x + y + z)P(x, y, z) + (xy + yz + zx)Q(x, y, z) + xyzR(x, y, z)
\end{align*}
with $P, Q, R \in \mathcal{A}$. Find the smallest non-negative integer $n$ such that $x^i y^j z^k \in \mathcal{B}$ for all non-negative integers $i, j, k$ satisfying $i + j + k \geq n$.
Given $2017$ positive real numbers $a_1,a_2,\dots ,a_{2017}$. For each $n>2017$, set $$a_n=\max\{ a_{i_1}a_{i_2}a_{i_3}|i_1+i_2+i_3=n, 1\leq i_1\leq i_2\leq i_3\leq n-1\}.$$
Prove that there exists a positive integer $m\leq 2017$ and a positive integer $N>4m$ such that $a_na_{n-4m}=a_{n-2m}^2$ for every $n>N$.
The numbers $2, 2, ..., 2$ are written on a blackboard (the number $2$ is repeated $n$ times). One step consists of choosing two numbers from the blackboard, denoting them as $a$ and $b$, and replacing them with $\sqrt{\frac{ab + 1}{2}}$.
$(a)$ If $x$ is the number left on the blackboard after $n - 1$ applications of the above operation, prove that $x \ge \sqrt{\frac{n + 3}{n}}$.
$(b)$ Prove that there are infinitely many numbers for which the equality holds and infinitely many for which the inequality is strict.
The $n$ contestant of EGMO are named $C_1, C_2, \cdots C_n$. After the competition, they queue in front of the restaurant according to the following rules.
[list]
[*]The Jury chooses the initial order of the contestants in the queue.
[*]Every minute, the Jury chooses an integer $i$ with $1 \leq i \leq n$.
[list]
[*]If contestant $C_i$ has at least $i$ other contestants in front of her, she pays one euro to the Jury and moves forward in the queue by exactly $i$ positions.
[*]If contestant $C_i$ has fewer than $i$ other contestants in front of her, the restaurant opens and process ends.
[/list]
[/list]
[list=a]
[*]Prove that the process cannot continue indefinitely, regardless of the Jury’s choices.
[*]Determine for every $n$ the maximum number of euros that the Jury can collect by cunningly choosing the initial order and the sequence of moves.
[/list]
Three nonnegative real numbers $ r_1$, $ r_2$, $ r_3$ are written on a blackboard. These numbers have the property that there exist integers $ a_1$, $ a_2$, $ a_3$, not all zero, satisfying $ a_1r_1 \plus{} a_2r_2 \plus{} a_3r_3 \equal{} 0$. We are permitted to perform the following operation: find two numbers $ x$, $ y$ on the blackboard with $ x \le y$, then erase $ y$ and write $ y \minus{} x$ in its place. Prove that after a finite number of such operations, we can end up with at least one $ 0$ on the blackboard.
Let $n\geqslant 2$ be a positive integer. Paul has a $1\times n^2$ rectangular strip consisting of $n^2$ unit squares, where the $i^{\text{th}}$ square is labelled with $i$ for all $1\leqslant i\leqslant n^2$. He wishes to cut the strip into several pieces, where each piece consists of a number of consecutive unit squares, and then [i]translate[/i] (without rotating or flipping) the pieces to obtain an $n\times n$ square satisfying the following property: if the unit square in the $i^{\text{th}}$ row and $j^{\text{th}}$ column is labelled with $a_{ij}$, then $a_{ij}-(i+j-1)$ is divisible by $n$.
Determine the smallest number of pieces Paul needs to make in order to accomplish this.