For a sequence of positive integers $\{x_n\}$ where $x_1 = 2$ and $x_{n + 1} - x_n \in \{0, 3\}$ for all positve integers $n$, then $\{x_n\}$ is called a "frog sequence". Find all real numbers $d$ that satisfy the following condition. (Condition) For two frog sequence $\{a_n\}, \{b_n\}$, if there exists a positive integer $n$ such that $a_n = 1000b_n$, then there exists a positive integer $m$ such that $a_m = d\cdot b_m$.
Problem
Source: KMO 2024 P2
Tags: algebra
dgkim
09.11.2024 16:27
I wonder why nobody has posted the solution yet
The answer is all integers in $[1,1000]$ in the form $3k+1$ (in other words, $1,4,7,\dots ,1000$).
To prove that others are impossible, simply consider the following two pairs of sequences:
$$a_n=\left\{\begin{matrix} 3n-1 & (n<667) \\ 2000 & (otherwise) \\ \end{matrix}\right. , b_n=2$$$$a_n=\left\{\begin{matrix} 3n-1 & (n<1667) \\ 5000 & (otherwise) \\ \end{matrix}\right. ,b_n=\left\{\begin{matrix} 2 & (n=1) \\ 5 & (otherwise) \\ \end{matrix}\right.$$Now we'll prove that any $d$ in $\{3k+1\mid 0\leq k\leq 333,k\in \mathbb{Z} \}$ satisfies the condition.
For $d=1,1000$ it is trivial.
Let $d=3k+1$ and $c_m=\frac{a_m}{b_m}$. Assume that there doesn't exist $m$ such that $c_m=3k+1$.
Since $c_1=1$ and $c_n=1000$ for some $n$, there exists a positive integer $t$ such that $c_t<3k+1$ and $c_{t+1}>3k+1$.
Here $c_t>1$ and $c_t<c_{t+1}$ so $a_{t+1}=a_t+3$ and $b_{t+1}=b_t$.
Therefore
$$ a_t<(3k+1)b_t<a_t+3$$However, $(3k+1)b_t\equiv 2\equiv a_t\pmod{3}$, so a contradiction.
Therefore, $1,4,7,\dots ,1000$ all satisfies the condition.
seoneo
14.11.2024 17:48
Step 1: \(d = 1, 4, 7, \ldots, 1000\) all satisfy the condition. Suppose that there does not exist \(m\) for which \(a_m = d \cdot b_m\). Let $a_n = 1000 b_n$ for some positive integer $n$. and let the value of \(b_n\) at this point be \(x\). Then \(a_n = 1000 x\). The frog sequence can increase by \(0\) or \(3\) at each step, so the sequence \(\{a_n\}\) includes all integers of the form \(2, 5, 8, \ldots, 1000x\). For each $i=2,5, \ldots , x$, let $k_i$ be the index $k$ such that $a_k = di$. Note that $di \equiv 2 \pmod{3}$ for the existence. $k_{i+3} \ge k_i$ and so $b_{k_{i+3}} \ge b_{k_i}$. $a_{k_x} = dx$ and $k_x \le n$, it follows that $b_{k_x} \le x$. On the other hand, from the hypothesis, $b_{k_x}<x$ holds. That is $b_{k_x} \le x-3$. Now $a_{k_{x-x}} = d(x-3)$ and from the hypothesis, $b_{k_{x-3}} \le x-6$. One can proceed like this to have $b_{k_2 \le 2}$ and $b_{k_2} \neq 2$ which leads a contradintion. tep 2: No other values are possible. $a_1 = 2$, $a_2 = 5$, $\cdots$, $a_{667} = 2 + 3\cdot 666 = 2000 = a_n$, $n \ge 667$ $b_1 = 2 = b_2 = \cdots$ Then $d = \frac{2}{2}$, $\frac{5}{2}$, $\ldots$, $\frac{2000}{2}$ and no other values are possible. From $a_1 = 2$, $a_2 = 5$, $\cdots$, $a_{1667} = 2 + 3 \cdot 1666 = 5000$ and $b_1 = 2$, $b_2 = 5 = \cdots$ Then $ d= \frac{2}{2}$, $\frac{5}{5}$, $\ldots$, $\frac{5000}{5}$. From the both observations, we conclude the only values of $d$ are those intersecting integers. Solved by my colleague. This was posted at https://artofproblemsolving.com/community/u281710h3441818p33188885