Find the least value of $k\in \mathbb{N}$ with the following property: There doesn’t exist an arithmetic progression with 2019 members, from which exactly $k$ are integers.
Problem
Source: X International Festival of Young Mathematicians Sozopol 2019, Theme for 10-12 grade
Tags: algebra, Arithmetic Progression
04.10.2019 23:09
Let be $(a_i), i\in\{1,2,\dots,2019\}$ an arithmetic progression which contains exactly $k$ integer therms and $r=a_{i+1}-a_i, \forall i\in\{1,2,\dots,2018\}$. Let be $b_p, p\in\{1,2,\dots,k\}$ the natural numbers for which $a_{_{b_p}}$ are integers, $1\le b_1<b_2<\dots<b_k\le 2019$. Property: $b_p$ are the therms of an arithmetic progression. Proof: Denote $m=\min{(b_{p+1}-b_p)}\in\mathbb{N}, 1\le p\le k-1$. $a_{_{b_{p+1}}}-a_{_{b_p}}=mr\in\mathbb{Z}$. Then $a_{_{b_1+um}}-a_{_{b_1}}=umr\in\mathbb{Z}\Longrightarrow a_{_{b_1+um}}\in\mathbb{Z}, \forall u\in\mathbb{N}$ such that $b_1+um\le b_k$. Results: $b_1+um\in\{b_2,b_3,\dots,b_k\}\quad(1)$. Assume $\exists v\in\mathbb{N}, 2\le v\le k$ such that $m\nmid b_{v}-b_1\Longrightarrow b_{v}-b_1=cm+n, c\in\mathbb{N}\cup\{0\},1\le n<m\Longrightarrow \exists w\in\mathbb{N}$ such that $b_w=b_v-cm, b_w-b_1=n<m$, contradiction with $m=\min{(b_{p+1}-b_p)}\in\mathbb{N}, 1\le p\le k-1$. Hence, $\forall 2\le p\le k, m|b_p-b_1$. Results: $\{b_2,b_3,\dots,b_k\}\in\{b_1+um\}, 1\le u\le \left\lfloor\dfrac{b_k-b_1}{m}\right\rfloor\quad(2)$. From $(1)$ and $(2)$ results $\{b_2,b_3,\dots,b_k\}=\{b_1+um\}, 1\le u\le \left\lfloor\dfrac{b_k-b_1}{m}\right\rfloor$, hence $(b_p), p\in\{1,2,\dots,k\}$ is an arithmetic progression with the common difference $m$. Next, we determine: for a given $m\in\mathbb{N}$, what are the possible values of $k$ such that the progression $(a_i)$ contains exactly $k$ integer therms. Using the notations from the previous paragraph, results: $b_1\in\{1,2,\dots,m\}, b_k\in\{2019-(m-1), 2019-(m-2),\dots,2019\}$. $k=\dfrac{b_k-b_1}{m}+1$. $\dfrac{2020-2m}{m}+1\le k\le \dfrac{2018}{m}+1\Longrightarrow$ $\Longrightarrow \dfrac{2020}{k+1}\le m\le\dfrac{2018}{k-1}\quad(3)$. If $\dfrac{2018}{k-1}-\dfrac{2020}{k+1}\ge 1$, exists an integer $m$ with the property $(3)$. $\dfrac{2018}{k-1}-\dfrac{2020}{k+1}\ge 1\Longrightarrow k^2+2k-4039\le0\Longrightarrow k\le62$. Hence, for $k\le62$, exists an integer $m$ with the property: exists an arithmetic progression with the common difference $m$ which has exactly $k$ integer therms. We must verify the values $k\ge63$ for which does not exist an integer $m$ with the property $(3)$. For $k=63: \dfrac{2020}{64}<32<\dfrac{2018}{62}$; For $k=64: \dfrac{2020}{65}<32<\dfrac{2018}{63}$; For $k=65: \dfrac{2020}{66}<31<\dfrac{2018}{64}$; For $k=66: \dfrac{2020}{67}<31<\dfrac{2018}{65}$; For $k=67: \dfrac{2020}{68}<30<\dfrac{2018}{66}$; For $k=68: \dfrac{2020}{69}<30<\dfrac{2018}{67}$; For $k=69: \dfrac{2020}{70}<29<\dfrac{2018}{68}$; For $k=70: \dfrac{2020}{71}<29<\dfrac{2018}{69}$; For $k=71: 28<\dfrac{2020}{72}<\dfrac{2018}{70}<29$. Results: the least value of $k$ for which doesn’t exist an arithmetic progression with 2019 therms, from which exactly $k$ are integers is $k_{min}=71$.