1
#IMO 2024
vital echo
1, Find all real number $\alpha,$ such that for any positive integer $n,$
$$\lfloor\alpha\rfloor +\lfloor 2\alpha\rfloor +\cdots +\lfloor n\alpha\rfloor$$is a multiple of $n.$
heavy badgerBOT
arohi
vital echo
- Find all positive integer pairs $(a,b),$ such that there exists positive integer $g,N,$
$$\gcd (a^n+b,b^n+a)=g$$holds for all integer $n\ge N$
heavy badgerBOT
arohi
vital echo
- Let $a_1, a_2, a_3, \dots$ be an infinite sequence of positive integers, and let $N$ be a positive integer. Suppose that, for each $n > N$, $a_n$ is equal to the number of times $a_{n-1}$ appears in the list $a_1, a_2, \dots, a_{n-1}$.
Prove that at least one of the sequence $a_1, a_3, a_5, \dots$ and $a_2, a_4, a_6, \dots$ is eventually periodic.
(An infinite sequence $b_1, b_2, b_3, \dots$ is eventually periodic if there exist positive integers $p$ and $M$ such that $b_{m+p} = b_m$ for all $m \ge M$.)
heavy badgerBOT
arohi
vital echo
Turbo the snail plays a game on a board with $2024$ rows and $2023$ columns. There are hidden monsters in $2022$ of the cells. Initially, Turbo does not know where any of the monsters are, but he knows that there is exactly one monster in each row except the first row and the last row, and that each column contains at most one monster.
Turbo makes a series of attempts to go from the first row to the last row. On each attempt, he chooses to start on any cell in the first row, then repeatedly moves to an adjacent cell sharing a common side. (He is allowed to return to a previously visited cell.) If he reaches a cell with a monster, his attempt ends and he is transported back to the first row to start a new attempt. The monsters do not move, and Turbo remembers whether or not each cell he has visited contains a monster. If he reaches any cell in the last row, his attempt ends and the game is over.
Determine the minimum value of $n$ for which Turbo has a strategy that guarantees reaching the last row on the $n$-th attempt or earlier, regardless of the locations of the monsters.
heavy badgerBOT
arohi
vital echo
Let $ABC$ be a triangle with $AB < AC < BC$. Let the incentive and incircle of triangle $ABC$ be $I$ and $\omega$, respectively. Let $X$ be the point on line $BC$ different from $C$ such that the line through $X$ parallel to $AC$ is tangent to $\omega$. Similarly, let $Y$ be the point on line $BC$ different from $B$ such that the line through $Y$ parallel to $AB$ is tangent to $\omega$. Let $AI$ intersect the circumcircle of triangle $ABC$ at $P \ne A$. Let $K$ and $L$ be the midpoints of $AC$ and $AB$, respectively.
Prove that $\angle KIL + \angle YPX = 180^{\circ}$.
heavy badgerBOT
arohi
vital echo
Let $\mathbb{Q}$ be the set of rational numbers. A function $f: \mathbb{Q} \to \mathbb{Q}$ is called aquaesulian if the following property holds: for every $x,y \in \mathbb{Q}$,
[ f(x+f(y)) = f(x) + y \quad \text{or} \quad f(f(x)+y) = x + f(y). ]Show that there exists an integer $c$ such that for any aquaesulian function $f$ there are at most $c$ different rational numbers of the form $f(r) + f(-r)$ for some rational number $r$, and find the smallest possible value of $c$.
heavy badgerBOT
arohi
ebon axle
Problem-1 The answer is that $\alpha$ must be an even integer. Let $S(n, \alpha)$ denote the sum in question.
Analysis for $\alpha$ an integer. If $\alpha$ is an integer, then the sum equals [ S(n, \alpha) = (1+2+\dots+n) \alpha = \frac{n(n+1)}{2} \cdot \alpha ]which is obviously a multiple of $n$ if $2 \mid \alpha$; meanwhile, if $\alpha$ is an odd integer then $n = 2$ gives a counterexample.
Main case. Suppose $\alpha$ is not an integer; we show the desired condition can never be true. Note that replacing $\alpha$ with $\alpha \pm 2$ changes by [ S(n \pm 2, \alpha) - S(n, \alpha) = 2(1+2+\dots+n) = n(n+1) \equiv 0 \pmod n ]for every $n$. Thus, by shifting appropriately we may assume $-1 < \alpha < 1$ and $\alpha \notin {\mathbb Z}$.
If $0 < \alpha < 1$, then let $m \ge 2$ be the smallest integer such that $m \alpha \ge 1$. Then [ S(m, \alpha) = \underbrace{0 + \dots + 0}{m-1\text{ terms}} + 1 = 1 ]is not a multiple of $m$.
If $-1 < \alpha < 0$, then let $m \ge 2$ be the smallest integer such that $m \alpha \le -1$. Then [ S(m, \alpha) = \underbrace{(-1) + \dots + (-1)}{m-1\text{ terms}} + 0 = -(m-1) ]is not a multiple of $m$.
heavy badgerBOT
jamal
ebon axle
The answer is $(a,b)=(1,1)$ only, which obviously works since the sequence is always $2$.
Conversely, assume the sequence [ x_n \coloneqq \gcd(a^n+b, b^n+a) ]is eventually constant. The main crux of the other direction is to consider [ M \coloneqq ab+1. ]Remark: [Motivation] The reason to consider the number is the same technique used in IMO 2005/4, namely the idea to consider $n = -1$''. The point is that the two rational numbers \[ \frac 1a + b = \frac{ab+1}{b}, \qquad \frac 1b + a = \frac{ab+1}{a} \]have a large common factor: we could write $x_{-1} = ab + 1$'', loosely speaking.
Now, the sequence is really only defined for $n \ge 1$, so one should instead take $n \equiv -1 \bmod{\varphi(M)}$ --- and this is exactly what we do.
Obviously $\gcd(a,M) = \gcd(b,M) = 1$. Let $n$ be a sufficiently large multiple of $\varphi(M)$ so that [ x_{n-1} = x_n = x_{n+1} = \dotsb. ]We consider the first three terms; the first one is the ``key'' one that gets the bulk of the work, and the rest is bookkeeping and extraction.
Consider $x_{n-1}$. Note that [ a (a^{n-1} + b) = a^n + ab \equiv 1 + (-1) \equiv 0 \pmod M ]and similarly $b (b^n + a) \equiv 0 \pmod M$. Hence $M \mid x_{n-1}$.
Consider $x_n$, which is now known to be divisible by $M$. Note that \begin{align*} 0 &\equiv a^n + b \equiv 1 + b \pmod M \ 0 &\equiv b^n + a \equiv 1 + a \pmod M. \end{align*}So $a \equiv b \equiv -1 \pmod M$.
Consider $x_{n+1}$, which is now known to be divisible by $M$. Note that [ 0 \equiv a^{n+1} + b \equiv b^{n+1} + a \equiv a + b \pmod M. ]We knew $a \equiv b \equiv -1 \pmod M$, hence this means $0 \equiv 2 \pmod M$, so $M = 2$.
From $M = 2$ we then conclude $a = b = 1$, as desired.
Remark: [No alternate solutions known] At the time nobody seems to know any solution not depending critically on $M$ or prime numbers dividing $M$. They vary in execution once some term of the form $x_{k\varphi(n)-1}$ is taken, but avoiding the key idea altogether does not currently seem possible.
heavy badgerBOT
jamal
ebon axle
Interesting combinatorics in disguise of sequence. The key is to prove that sufficiently large numbers appear finitely many times in such sequence, and such number of appearance should be equal for all sufficiently large numbers.
Denote $f(n, i)$ the number of occurrences of $i$ among the first $n$ entries $a_1, \ldots, a_n$ of the sequence. We have $a_n = f(n-1, a_{n-1})$ for all $n > N$. Select a sufficiently large integer $M > N$ such that $f(N, j) = 0$ for all $j \ge M$ and $f(N, j) < M$ for all $j <M$.
We begin by observing that starting from $n = N+1$, any pairs $(a_n, a_{n+1})$ will appear only once in the sequence. It means that all the numbers that precedents a same number $j$ in the sequence must be mutually different.
Claim 1: For all $t > N$ and $M \le i < j$, $f(t, i) \ge f(t, j)$.
Proof
WLOG assume that $j = i+1$. For any $t > N$, note that since $f(N, j) = f(N, i) = 0$, all occurrences of $i$ and $j$ must be in $a_{N+1}, \ldots, a_t$. Let $i_1, \ldots, i_{f(t, j)}$ be the indices such that $a_{i_l} = j$ for $1\le l \le f(t, j)$, then we have $f(i_l - 1, a_{i_l - 1}) = j$. There must then exist $k_l < i_l-1$ such that $f(k_l, a_{i_l - 1}) = i$ and $a_{k_l} = a_{i_l-1}$ , and thus $a_{k_l+1} = i$. Note that all $a_{i_l-1}$ should be mutually different, so all $k_l$ are mutually different. So $i$ occurs at least as many times as $j$ within $a_1, \ldots, a_t$. This implies $f(t, i) \ge f(t, j)$.Claim 2: $f(t, K)\le K-1$ for all $t$.
Proof
Assume the contradiction and consider the indice $t$ such that $a_t = K$ and $f(t, K) = K$. Let $i_1<i_2<\ldots <i_K$ be the indices such that $a_{i_l} = K$. Note that all $a_{i_l-1}$ must be mutually different, so one of $a_{i_l-1}$ is greater than $K$. Then, $f(i_l-1, a_{i_l-1}) = K > f(t-1, K) \ge f(i_l-1, K)$, contradicts claim 1.
heavy badgerBOT
jamal
ebon axle
Due to claim 1 and claim 2, for all $t$ and $i \ge K$, we have $f(t, i) \le K-1$. This means that for any given $i$, $\lim_{t\to \infty} f(t, i)$ converges to $B_i$ for some $B_i \le K-1$ (due to monotonicity in $t$). Due to claim 1 again we can see that $B_i\ge B_j$ for all $K\le i < j$, so $\lim_{i\to \infty} B_i = c$ for some $0\le c \le K-1$. Hence, there exists constants $T, M, c$ such that $f(t, i) = c$ for all $t > T, i > M$.
Claim 3: $c \ge 1$ and the numbers $1, 2, \ldots, c$ are the only numbers that occur infinitely often in the sequence.
Proof
To show that $c \ge 1$ it is sufficient to show that any number $x$ must occur once in the sequence $(a_n)$. Note that there must exist a number $a$ that occurs infinitely many times in the sequence. Let $l$ be the indices of its $x^\text{th}$ occurrence, then $a_{l+1} = x$, as desired.
Now it is obvious to see that $1, 2, \ldots, c$ occur infinitely often in the sequence. We show that any $i > c$ does not occur infinitely often. Assume the contradiction, then since for all $j > M$, $f(t, j)$ is eventually $c$, or $f(t, j)$ will occur only $c$ times in the sequence, then after the occurrence of $j$ it can only be the numbers from $1, 2, \ldots, c$. This means that the occurrence of $i > c$ can only be after a number $j' < M$. Since there are only finitely many such $j'$, the occurrence of $i$ must be finite.
Claim 3 implies that there exists sufficiently large integers $N'$ and $M$ such that for all $n > N'$, it is either that $a_n > M$, or $a_n \le c$. Note that we can again select $N'$ to be large enough so that $f(N', i) > c$ for all $1\le i \le c$, so that any numbers that comes after $1\le i \le c$ must be larger than $M$. This creates an alternating sequence between "large" and "small" number. It is sufficient to show that the sequence of "small" number is eventually periodic. The tricky part of this is to control the gap between occurrences of the same number.
heavy badgerBOT
jamal
ebon axle
Claim 4: There exists a constant $D$ such that for any $t$, $\max_{1\le i \le c} f(t, i) - \min_{1\le i\le c} f(t, i) \le D$.
Proof
For any $1\le x < y\le c$, there is a constant $L_{x, y}$ for any $t$, $f(t, x) \ge f(t, y) - L_{x, y}$. Note that when $t > N'$, any occurrences of $y$ must be precedented by an occurrence of a number $j > M$. Such $j > M$ must give an occurrence of $x < y$ some time before that.
Let $L = \max(L_{x, y})$ over all $x < y$. Then, if we assume the contradiction that $\max_{1\le i \le c} f(t, i) - \min_{1\le i\le c} f(t, i)$ is not uniformly bounded on $t$, then there must be a sufficiently large $t$ and an $1\le i \le c-1$ such that $\min_{1\le j \le i} f(t, j) > \max_{i+1\le j \le c} f(t, j)$. In fact, let $t$ be the number such that $\max_{1\le i \le c} f(t, i) - \min_{1\le i\le c} f(t, i) > 3L$. Let $j_1, j_2$ be the indices that $f(t, j_1) = \max_{1\le i\le c} f(t, i), f(t, j_2) = \min_{1\le i\le c} f(t, i)$. By claim 3, we must have $j_1 < j_2$. Furthermore, $f(t, i) \ge f(t, j_1) - L$ for all $i < j_1$, and $f(t_i) \le f(t, j_2) + L$ for all $i > j_2$. Since there can't be $j_1 < k_1 < k_2 < j_2$ such that $f(t, k_2) \ge f(t, j_1) - L$ and $f(t, k_1) \le f(t, j_2) + L$, it must be the case that there is an index $k$ such that $f(t, i) \ge f(t, j_1) - L)$ for all $i \le k$, and $f(t, i) \le f(t, j_2) + L$ for all $i > k$. Since $f(t, j_1) - L > f(t, j_2) + L$, we arrive at the claim.
Then, at the first time $t$ that this happens, $a_t \le i$, and $a_{t+1}$ is larger than $\max_{i+1\le j \le c} f(t, j)$. Then, $a_{t+2}$ must be in $1, 2, \ldots, i$, and we can use induction to show that from then on, no more occurrences of $i+1, \ldots, c$ can happen, which contradicts claim 3.
For a number $n > M$, define $i_{n, 1} < i_{n, 2} < \ldots < i_{n, c}$ the indices that $a_{i_{n, k}} = n$. Denote the difference tuple $T_n = (i_{n, 2} - i_{n, 1}, \ldots, i_{n, c} - i_{n, c-1})$.
heavy badgerBOT
jamal
ebon axle
Claim 5: There is a constant $D'$ such that $i_{n, h} - i_{n, h-1} \le D'$ for all $n > M$ and $2\le h\le c$.
Proof
Note that the difference between $f(t, i)$ and $f(t, j)$ for $1\le i < j\le c$ is bounded above by $D$ at any time $t$ (claim 4). Consider $a_{i_{n, h-1}} = n, a_{i_{n, h-1}+1} = h-1$ and $a_{i_{n, h}} = n, a_{i_{n, h}+1} = h$. Note that for $i_{n, h-1} \le t \le i_{n, h}-2$, among $f(t, 1), \ldots, f(t, c)$, there are exactly $h-1$ values that are at least $n$, and all other values must be smaller than $n$. As the gap between the maximum and minimum of $f(t, i)$ is at most $D$, we can see that the values initially smaller than $n$ must be at least $n-D$, and thus the appearance of $a$ such that $f(i_{n, h-1}, a) < n$ between $i_{n, h-1} \le t \le i_{n, h}-2$ can only be at most $D$. Likewise, the appearance of $a$ such that $f(i_{n, h-1}, a) \ge n$ between $i_{n, h-1} \le t \le i_{n, h}-2$ is also at most $D$, as $f(t, a)$ can only increase at maximal to $n+D$.
This implies a rough bound $i_{n, h} - i_{n, h-1} \le 2Dc$. Let $D' = 2Dc$ and we are done.
Now, since there are at most $D'^{c-1}$ values for the tuples $T_n$ for $n \ge M$, $T_n$ must be eventually periodic. Let $T$ be the period of $T_n$, and let $b = i_{n+T, 1} - i_{n, 1}$, then for every sufficiently large $n$ and $1\le h\le c$, we have $i_{n+T, h} - i_{n, h} = i_{n+T, H} - i_{n+T, 1} - (i_{n, h} - i_{n, 1}) + i_{n+T,1} - i_{n, 1} = i_{n+T,1} - i_{n, 1}$.
Now, we can proceed similar to claim 5 to show that there is a constant $B$ such that $i_{n+T,1} - i_{n, 1} \le B$ for all $n$ (brief idea: the difference $i_{n+T,1} - i_{n, 1}$ is the difference between the $n^\text{th}$ 1 and $(n+T)^\text{th}$ 1, hence occurrences of $2, \ldots, c$ can only be at most $T+2D$ for each of them). This again means that $i_{n+T,1} - i_{n, 1} \le B$ is eventually periodic, so there is a period $C$ such that $i_{n+T+C,1} - i_{n+C, 1} = i_{n+T,1} - i_{n, 1}$ for all $n$ sufficiently large.
It is important to note that eventual periodicity is implied due to a non trivial fact that once a pattern repeats, then by induction it will keep repeating. I'll leave this as some details for others to work on.
Let $b = i_{n+T+C, 1} - i_{n, 1}$. Then for any $n$ sufficiently large and $1\le h\le c, a_{i_{n, h} +1} = h = a_{i_{n+T+C, h} + 1} = a_{i_{n, h} + b+1}$. This implies that the "small" sequence is eventually periodic, as desired.
Due to my laziness, I might have avoided many small details of the proof. Any comments are appreciated.
ebon axle
comments:I believe this is truly a combinatorics problem despite looking like algebra, but most of the core arguments are playing around with combinatorial arguments of occurrences of numbers. Algebraic formulation is for better readability. One of my friends have another combinatorial formulation that might be easier to argue on: assume that you have infinite bags of marbles that are labelled $1,2,3, \ldots$. At the beginning, you randomly put marbles into the bag, but after time $N$, if the last marble is placed into a bag with $k-1$ marbles, then you place the next marble into the bag $k$.