Found problems: 815
In Happy City there are $2014$ citizens called $A_1, A_2, \dots , A_{2014}$. Each of them is either [i]happy[/i] or [i]unhappy[/i] at any moment in time. The mood of any citizen $A$ changes (from being unhappy to being happy or vice versa) if and only if some other happy citizen smiles at $A$. On Monday morning there were $N$ happy citizens in the city.
The following happened on Monday during the day: the citizen $A_1$ smiled at citizen $A_2$, then $A_2$ smiled at $A_3$, etc., and, finally, $A_{2013}$ smiled at $A_{2014}$. Nobody smiled at anyone else apart from this. Exactly the same repeated on Tuesday, Wednesday and Thursday. There were exactly $2000$ happy citizens on Thursday evening.
Determine the largest possible value of $N$.
Given is an acute triangle $ ABC$ and the points $ A_1,B_1,C_1$, that are the feet of its altitudes from $ A,B,C$ respectively. A circle passes through $ A_1$ and $ B_1$ and touches the smaller arc $ AB$ of the circumcircle of $ ABC$ in point $ C_2$. Points $ A_2$ and $ B_2$ are defined analogously.
Prove that the lines $ A_1A_2$, $ B_1B_2$, $ C_1C_2$ have a common point, which lies on the Euler line of $ ABC$.
Elmo has 2023 cookie jars, all initially empty. Every day, he chooses two distinct jars and places a cookie in each. Every night, Cookie Monster finds a jar with the most cookies and eats all of them. If this process continues indefinitely, what is the maximum possible number of cookies that the Cookie Monster could eat in one night?
[i]Proposed by Espen Slettnes[/i]
Let $a_1, a_2, \ldots, a_n$ be $n$ positive integers, and let $b_1, b_2, \ldots, b_m$ be $m$ positive integers such that $a_1 a_2 \cdots a_n = b_1 b_2 \cdots b_m$. Prove that a rectangular table with $n$ rows and $m$ columns can be filled with positive integer entries in such a way that
* the product of the entries in the $i$-th row is $a_i$ (for each $i \in \left\{1,2,\ldots,n\right\}$);
* the product of the entries in the $j$-th row is $b_j$ (for each $i \in \left\{1,2,\ldots,m\right\}$).
There are $n \geq 3$ islands in a city. Initially, the ferry company offers some routes between some pairs of islands so that it is impossible to divide the islands into two groups such that no two islands in different groups are connected by a ferry route.
After each year, the ferry company will close a ferry route between some two islands $X$ and $Y$. At the same time, in order to maintain its service, the company will open new routes according to the following rule: for any island which is connected to a ferry route to exactly one of $X$ and $Y$, a new route between this island and the other of $X$ and $Y$ is added.
Suppose at any moment, if we partition all islands into two nonempty groups in any way, then it is known that the ferry company will close a certain route connecting two islands from the two groups after some years. Prove that after some years there will be an island which is connected to all other islands by ferry routes.
On a flat plane in Camelot, King Arthur builds a labyrinth $\mathfrak{L}$ consisting of $n$ walls, each of which is an infinite straight line. No two walls are parallel, and no three walls have a common point. Merlin then paints one side of each wall entirely red and the other side entirely blue.
At the intersection of two walls there are four corners: two diagonally opposite corners where a red side and a blue side meet, one corner where two red sides meet, and one corner where two blue sides meet. At each such intersection, there is a two-way door connecting the two diagonally opposite corners at which sides of different colours meet.
After Merlin paints the walls, Morgana then places some knights in the labyrinth. The knights can walk through doors, but cannot walk through walls.
Let $k(\mathfrak{L})$ be the largest number $k$ such that, no matter how Merlin paints the labyrinth $\mathfrak{L},$ Morgana can always place at least $k$ knights such that no two of them can ever meet. For each $n,$ what are all possible values for $k(\mathfrak{L}),$ where $\mathfrak{L}$ is a labyrinth with $n$ walls?
We are given $2n$ natural numbers
\[1, 1, 2, 2, 3, 3, \ldots, n - 1, n - 1, n, n.\]
Find all $n$ for which these numbers can be arranged in a row such that for each $k \leq n$, there are exactly $k$ numbers between the two numbers $k$.
The integers $-1$, $2$, $-3$, $4$, $-5$, $6$ are written on a blackboard. At each move, we erase two numbers $a$ and $b$, then we re-write $2a+b$ and $2b+a$. How many of the sextuples $(0,0,0,3,-9,9)$, $(0,1,1,3,6,-6)$, $(0,0,0,3,-6,9)$, $(0,1,1,-3,6,-9)$, $(0,0,2,5,5,6)$ can be gotten?
$
\textbf{(A)}\ 1
\qquad\textbf{(B)}\ 2
\qquad\textbf{(C)}\ 3
\qquad\textbf{(D)}\ 4
\qquad\textbf{(E)}\ 5
$
Consider a $2018 \times 2019$ board with integers in each unit square. Two unit squares are said to be neighbours if they share a common edge. In each turn, you choose some unit squares. Then for each chosen unit square the average of all its neighbours is calculated. Finally, after these calculations are done, the number in each chosen unit square is replaced by the corresponding average.
Is it always possible to make the numbers in all squares become the same after finitely many turns?
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.
Let $n> 2$ be an integer. A child has $n^2$ candies, which are distributed in $n$ boxes. An operation consists in choosing two boxes that together contain an even number of candies and redistribute the candy from those boxes so that both contain the same amount of candy. Determine all the values of $n$ for which the child, after some operations, can get each box containing $n$ candies, no matter which the initial distribution of candies is.
There three piles of pebbles, containing 5, 49, and 51 pebbles respectively. It is allowed to combine any two piles into a new one or to split any pile consisting of even number of pebbles into two equal piles. Is it possible to have 105 piles with one pebble in each in the end?
[i](3 points)[/i]
Two rational numbers \(\tfrac{m}{n}\) and \(\tfrac{n}{m}\) are written on a blackboard, where \(m\) and \(n\) are relatively prime positive integers. At any point, Evan may pick two of the numbers \(x\) and \(y\) written on the board and write either their arithmetic mean \(\tfrac{x+y}{2}\) or their harmonic mean \(\tfrac{2xy}{x+y}\) on the board as well. Find all pairs \((m,n)\) such that Evan can write 1 on the board in finitely many steps.
[i]Proposed by Yannick Yao[/i]
Anna and Bob play the following game. In the beginning, Bob writes down the numbers $1, 2, ... , 2022$ on a piece of paper, such that half of the numbers are on the left and half on the right. Furthermore, we assume that the $1011$ numbers on both sides are written in some order.
After Bob does this, Anna has the opportunity to swap the positions of the two numbers lying on different sides of the paper if they have different parity. Anna wins if, after finitely many moves, all odd numbers end up on the left, in increasing order, and all even ones end up on the right, in increasing order. Can Bob write down a arrangement of numbers for which Anna cannot win?
For example, Bob could write down numbers in the following way: $$4, 2, 5, 7, 9, ... , 2021\,\,\,\,\,\,\,\,\,\,,\, \,\,\,\,\,\,\,\,\,\,,\, 3, 1, 6, 8, 10, ... , 2022$$ Then Anna could swap the numbers $1, 4$ and then swap $2, 3$ to win. However, if Anna swapped
the pairs $3, 4$ and $1, 2$, the resulting numbers on the left and on the right would not be in increasing order, and hence Anna would not win.
Four frogs are positioned at four points on a straight line such that the distance between any two neighbouring points is 1 unit length. Suppose the every frog can jump to its corresponding point of reflection, by taking any one of the other 3 frogs as the reference point. Prove that, there is no such case that the distance between any two neighbouring points, where the frogs stay, are all equal to 2008 unit length.
There is a deck of cards placed at every points $A_1, A_2, \ldots , A_n$ and $O$, where $n \geq 3$. We can do one of the following two operations at each step:
$1)$ If there are more than 2 cards at some points $A_i$, we can withdraw three cards from that deck and place one each at $A_{i-1}, A_{i+1}$ and $O$. (Here $A_0=A_n$ and $A_{n+1}=A_1$);
$2)$ If there are more than or equal to $n$ cards at point $O$, we can withdraw $n$ cards from that deck and place one each at $A_1, A_2, \ldots , A_n$.
Show that if the total number of cards is more than or equal to $n^2+3n+1$, we can make the number of cards at every points more than or equal to $n+1$ after finitely many steps.
Let $ X$ be a set of 10,000 integers, none of them is divisible by 47. Prove that there exists a 2007-element subset $ Y$ of $ X$ such that $ a \minus{} b \plus{} c \minus{} d \plus{} e$ is not divisible by 47 for any $ a,b,c,d,e \in Y.$
[i]Author: Gerhard Wöginger, Netherlands[/i]
A grid consists of all points of the form $(m, n)$ where $m$ and $n$ are integers with $|m|\le 2019,|n| \le 2019$ and $|m| +|n| < 4038$. We call the points $(m,n)$ of the grid with either $|m| = 2019$ or $|n| = 2019$ the [i]boundary points[/i]. The four lines $x = \pm 2019$ and $y= \pm 2019$ are called [i]boundary lines[/i]. Two points in the grid are called [i]neighbours [/i] if the distance between them is equal to $1$.
Anna and Bob play a game on this grid.
Anna starts with a token at the point $(0,0)$. They take turns, with Bob playing first.
1) On each of his turns. Bob [i]deletes [/i] at most two boundary points on each boundary line.
2) On each of her turns. Anna makes exactly three [i]steps[/i] , where a [i]step [/i] consists of moving her token from its current point to any neighbouring point, which has not been deleted.
As soon as Anna places her token on some boundary point which has not been deleted, the game is over and Anna wins.
Does Anna have a winning strategy?
[i]Proposed by Demetres Christofides, Cyprus[/i]
Let $n$ be a positive integer, and Megavan has a $(3n+1)\times (3n+1)$ board. All squares, except one, are tiled by non-overlapping $1\times 3$ triominoes. In each step, he can choose a triomino that is untouched in the step right before it, and then shift this triomino horizontally or vertically by one square, as long as the triominoes remain non-overlapping after this move.
Show that there exist some $k$, such that after $k$ moves Megavan can no longer make any valid moves irregardless of the initial configuration, and find the smallest possible $k$ for each $n$.
[i](Note: While he cannot undo a move immediately before the current step, he may still choose to move a triomino that has already been moved at least two steps before.)[/i]
[i]Proposed by Ivan Chan Kai Chin[/i]
Sydney the squirrel is at $(0, 0)$ and is trying to get to $(2021, 2022)$. She can move only by reflecting her position over any line that can be formed by connecting two lattice points, provided that the reflection puts her on another lattice point. Is it possible for Sydney to reach $(2021, 2022)$?
The number $12$ is written on the whiteboard. Each minute, the number on the board is either multiplied or divided by one of the numbers $2$ or $3$ (a division is possible only if the result is an integer) . Prove that the number that will be written on the board in exactly one hour will not be equal to $54$.
There are $n$ students standing in a circle, one behind the other. The students have heights $h_1<h_2<\dots <h_n$. If a student with height $h_k$ is standing directly behind a student with height $h_{k-2}$ or less, the two students are permitted to switch places. Prove that it is not possible to make more than $\binom{n}{3}$ such switches before reaching a position in which no further switches are possible.
For given positive integers $n$ and $N$, let $P_n$ be the set of all polynomials $f(x)=a_0+a_1x+\cdots+a_nx^n$ with integer coefficients such that:
[list]
(a) $|a_j| \le N$ for $j = 0,1, \cdots ,n$;
(b) The set $\{ j \mid a_j = N\}$ has at most two elements.
[/list]
Find the number of elements of the set $\{f(2N) \mid f(x) \in P_n\}$.
Let $ABC$ be an isosceles triangle with $AC=BC$, whose incentre is $I$. Let $P$ be a point on the circumcircle of the triangle $AIB$ lying inside the triangle $ABC$. The lines through $P$ parallel to $CA$ and $CB$ meet $AB$ at $D$ and $E$, respectively. The line through $P$ parallel to $AB$ meets $CA$ and $CB$ at $F$ and $G$, respectively. Prove that the lines $DF$ and $EG$ intersect on the circumcircle of the triangle $ABC$.
[i]Proposed by Hojoo Lee, Korea[/i]
Starting with the triple $(1007\sqrt{2},2014\sqrt{2},1007\sqrt{14})$, define a sequence of triples $(x_{n},y_{n},z_{n})$ by
$x_{n+1}=\sqrt{x_{n}(y_{n}+z_{n}-x_{n})}$
$y_{n+1}=\sqrt{y_{n}(z_{n}+x_{n}-y_{n})}$
$ z_{n+1}=\sqrt{z_{n}(x_{n}+y_{n}-z_{n})}$
for $n\geq 0$.Show that each of the sequences $\langle x_n\rangle _{n\geq 0},\langle y_n\rangle_{n\geq 0},\langle z_n\rangle_{n\geq 0}$ converges to a limit and find these limits.