Positive integers $a_1, a_2, \ldots, a_{101}$ are such that $a_i+1$ is divisible by $a_{i+1}$ for all $1 \le i \le 101$, where $a_{102} = a_1$. What is the largest possible value of $\max(a_1, a_2, \ldots, a_{101})$? Proposed by Oleksiy Masalitin
Problem
Source: Ukrainian Mathematical Olympiad 2023. Day 1, Problem 9.2
Tags: number theory, Divisibility
05.04.2023 12:20
The desired largest possible value is $201$, attained by $(a_1,a_2,\ldots,a_{101})=(101,102,\ldots,201 \}$. WLOG assume that $a_{101}$ is the largest of the $a_i$, and $a_{101}=k>201$. Claim: $a_{101-i}=k-i$ for all $0 \leq i \leq 100$. Proof: We proceed inductively. For $i=0$ we have nothing to prove. Assume that $a_{101-i}=k-i$ for some $i$. Then, $k-i=a_{101-i} \mid a_{101-(i+1)}+1$. If $a_{101-(i+1)}+1 \geq 2(k-i),$ then $k+1 \geq a_{101-(i+1)}+1 \geq 2(k-i)=(k+1)+(k-2i-1)>(k+1)+(201-2 \cdot 100-1)=k+1,$ which is a contradiction. Therefore, $a_{101-(i+1)}+1=k-i,$ and so $a_{101-(i+1)}=k-(i+1),$ as desired $\blacksquare$ To the problem, from the Claim we obtain that $a_1=k-100$, and so $k-100=a_1 \mid a_{101}+1=k+1,$ hence $k-100 \mid 101$, which is a contradiction since $k-100 >101$. Therefore, the desired maximum is indeed $201$.
23.06.2023 15:02
Orestis_Lignos wrote: The desired largest possible value is $201$, attained by $(a_1,a_2,\ldots,a_{101})=(101,102,\ldots,201 \}$. WLOG assume that $a_{101}$ is the largest of the $a_i$, and $a_{101}=k>201$. Claim: $a_{101-i}=k-i$ for all $0 \leq i \leq 100$. Proof: We proceed inductively. For $i=0$ we have nothing to prove. Assume that $a_{101-i}=k-i$ for some $i$. Then, $k-i=a_{101-i} \mid a_{101-(i+1)}+1$. If $a_{101-(i+1)}+1 \geq 2(k-i),$ then $k+1 \geq a_{101-(i+1)}+1 \geq 2(k-i)=(k+1)+(k-2i-1)>(k+1)+(201-2 \cdot 100-1)=k+1,$ which is a contradiction. Therefore, $a_{101-(i+1)}+1=k-i,$ and so $a_{101-(i+1)}=k-(i+1),$ as desired $\blacksquare$ To the problem, from the Claim we obtain that $a_1=k-100$, and so $k-100=a_1 \mid a_{101}+1=k+1,$ hence $k-100 \mid 101$, which is a contradiction since $k-100 >101$. Therefore, the desired maximum is indeed $201$. I guess you also need to add the construction: 101, 102, 103, 104,.......,201