There are $101$ positive integers $a_1, a_2, \ldots, a_{101}$ such that for every index $i$, with $1 \leq i \leq 101$, $a_i+1$ is a multiple of $a_{i+1}$. Find the greatest possible value of the largest of the $101$ numbers.
Problem
Source: Argentina Cono Sur TST 2024 P2
Tags: number theory
13.11.2024 04:20
Let $a_k$ the largest of the 101 numbers. -Supose that $a_k>201$. First we are going to proof by induction on $n$ that $a_{k-n}=a_k-n$ for all $n=0, 1, 2, ...100$ (Is easy to see that $a_k, a_{k-1}, ..., a_{k-100}$ are all the numbers $a_1, a_2, ...., a_{101}$ where k isn't necessarily 1. Just think them as modulo 101). Case base: Note that $a_k \mid a_{k-1} +1 \Rightarrow a_k \le a_{k-1}+1 \le a_k+1$, so $a_{k-1}=a_k$, or $a_{k-1}=a_k -1$, but $a_k$ and $a_k+1$ are coprimes so $a_{k-1}=a_k -1$. Inductive step: If $a_{k-t}=a_k-t$ for some $0\le t \le 99$ we have that: $a_{k-t}=a_k-t\mid a_{k-(t+1)} +1 \Rightarrow a_k-t\le a_{k-(t+1)} +1\le a_k +1$, so $a_{k-(t+1)}$ has all this possibilities: $a_k-(t+1), a_k-t, a_k-(t-1), a_k -(t-2), ..., a_k$. If $a_{k-(t+1)}=a_k-(u)$, $0\le u \le t$, we have that: $a_{k-t}=a_k-t \mid a_{k-(t+1)} +1= a_k-(u) +1 \Rightarrow a_k-t \mid(a_k-u+1)- ( a_k-t)=t-u+1>0$, (definition of u)$ \Rightarrow a_k-t \le t-u+1 \Rightarrow a_k \le 2t -u +1 \le 2*100 - 0 +1=201$. Contradiction. So that implies $a_{k-(t+1)}=a_k-(t+1)$, end of the induction. Then, we know that $a_{k-100}=a_k-100$, so we have that: $a_{k-100}=a_k-100 \mid a_k +1 \Rightarrow a_k-100 \mid (a_k+1) - (a_k - 100)=101 \Rightarrow a_k - 100 \le 101 \Rightarrow a_k \le 201$ Contradiction. -We conclude that $a_k\le 201$. Consider the next configuration: $a_i=100 +i$ for all $i=1, 2, ...101$. Note that: For all $1, 2, ..., 100$, $a_i+1=100+i+1=a_{i+1}$, so $a_i+1$ is a multiple of $a_{i+1}$. $a_{101}+1=202= 101*2=a_1 * 2$ so $a_{101}+1$ is a multiple of $a_1$. -The answer is 201.
10.01.2025 18:32
$\color{green} \boxed{\textbf{SOLUTION}}$ We have, $i=a_1 \le a_{101}+1\le a_{100}+2 \cdots \le a_{2} + 100 \le a_{1} + 100=i+100$ So $a_k \in [i, i+100]$ As every number have to be different so $(a_1,a_2,...a_{101})$ must be a combination of $(i,i+1,i+2...,i+100)$ Let the are not consecutive, $a_{k-1} = i + m$ and $a_k = i+n$ We have $i+n | i+m+1 \implies n < m+1 \implies n-1 < m$ But $m,n$ are not equal so $n < m$ Now, $ i+n \le (m-n) +1$ And $102 \ge (m-n) +1 \ge i+n$ Which gives the maximum number is $102$ But while taking them consecutive, $a_k = i + (k-1)$ Its easy to see all $k \le 100$ does work now for $i=a_1| a_{101}+1=i+101|101$ gives $a_1=101,...a_{101}=201$ So $\boxed{201}$