for a positive integer $n$, there are positive integers $a_1, a_2, ... a_n$ that satisfy these two. (1) $a_1=1, a_n=2020$ (2) for all integer $i$, $i$satisfies $2\leq i\leq n, a_i-a_{i-1}=-2$ or $3$. find the greatest $n$
Problem
Source: KJMO 2020 p6
Tags: KJMO, KMO
30.09.2021 20:41
jmsung1004 wrote: find the greatest $n$ Find the smallest $n$, right?
01.10.2021 06:10
no, largest $n$
01.10.2021 06:17
$\{a_i\}_{i=1}^{n}=\{1,4,2,5,3,\cdots,2019,2017,2020,\colorbox{yellow}{\textcolor{red}{2018,2016,2014,2017,2020}}\times n\}$ So $n=\infty$
01.10.2021 11:58
a22886 wrote: $\{a_i\}_{i=1}^{n}=\{1,4,2,5,3,\cdots,2019,2017,2020,\colorbox{yellow}{\textcolor{red}{2018,2016,2014,2017,2020}}\times n\}$ So $n=\infty$ Indeed, there is no largest value.
01.10.2021 12:17
Actually, the official problem states this: KJMO 2020/6 wrote: For a positive integer $n$, there exists $n$ distinct positive integers $a_1, a_2, \ldots, a_n$, satisfying the following two conditions: $a_1=1, a_n=2020$ For all positive integer $i$ with $2 \le i \le n$, $a_i-a_{i-1}=-2 \ \text{or} \ 3$. Find the largest $n$.
30.11.2021 14:45
Let $x$ be the number of values of $i$ where $a_i - a_{i-1} = 3$ and $y$ be the number of values of $i$ where $a_i - a_{i-1} = -2$. Then $1 + 3x - 2y = 2020 \iff 3x - 2y = 2019$. Since $5(x - y) = 2(3x - 2y) - (x + y) = 4038 - (x + y) \equiv 0 \pmod{5}$, then $x + y \equiv 3 \pmod{5}$. From $x + y = n - 1$, we get $n \equiv 4 \pmod{5}$. If $n \ge 2020$, then $n \ge 2024$. Let $M = \text{max}\{a_1, a_2,\dots, a_n\}$. Since $a_1, a_2,\dots, a_n$ are distinct positive integers, then $M \ge n \ge 2024$. If $M = 2024$, then $n = 2024$, all the integers from $1$ to $2024$ are in the sequence, and the last four terms are forced to be $2021, 2024, 2022, 2020$. If $2023$ is a term in the sequence, then the term before it must be either $2020$ or $2025$, a contradiction. Thus, $2023$ is not a term in the sequence, a contradiction. If $M \ge 2025$, then the term before it must be $M - 3$ and the term after it must be $M - 2$. The term after $M - 2$ must be $M - 4$. Then the term after $M - 4$ must be either $M - 1$ or $M - 6$. If it is $M - 1$, then the term after it must be either $M + 2$ or $M - 3$, which are both impossible. If it is $M - 6$, then the term before $M - 3$ must be $M - 1$, and the term before $M - 1$ must be either $M + 1$ or $M - 6$, which are both impossible. Thus, $n \le 2019$. For $n = 2019$, we can let $a_2 = 4, a_3 = 2, a_4 = 5, a_5 = 3$, and $a_{i+5} = a_i + 5$ for all $1 \le i \le 2014$. It is easy to see these satisfy the conditions. Therefore, the largest possible value of $n$ is $\boxed{2019}$.