Determine the smallest positive integer $n$ for which the following statement holds true: From any $n$ consecutive integers one can select a non-empty set of consecutive integers such that their sum is divisible by $2019$. Proposed by Kartal Nagy, Hungary
Problem
Source: 2019 MEMO Problem I-4
Tags: number theory, memo, MEMO 2019
Mr.Chagol
29.08.2019 11:19
Most probably it is $675$. $2019 \mid (k+n-1)(k+n)-k(k+1)$ where we fix any $k$. After little calculation it is $2019\mid (n-1)(2k+n)$. So as $k$ is random, hence $n=675$ @below thanks typed that in a hurry
yamamaya
29.08.2019 11:51
Mr.Chagol wrote: Most probably it is $2020$. $2019 \mid (k+n-1)(k+n)-k(k+1)$ where we fix any $k$. After little calculation it is $2019\mid (n-1)(2k+n)$. So as $k$ is random, hence $n=2020$ Consider if n=675, since the sum of any 673 consecutive should be divisible by 673, and one can pick the first number divisible by 3.
yamamaya
29.08.2019 13:47
Mr.Chagol wrote: Most probably it is $675$. $2019 \mid (k+n-1)(k+n)-k(k+1)$ where we fix any $k$. After little calculation it is $2019\mid (n-1)(2k+n)$. So as $k$ is random, hence $n=675$ @below thanks typed that in a hurry I'm sorry, but let's consider if n could be lower to 674...
The numbers mentioned below are moded by 2019 (when we say 1, it should be 2019*k+1). Consider 674 consecutive integers.
(1) If the consecutive numbers contain 672, 673, 674; sum those 3 numbers.
(2) If the consecutive numbers contain 673*2-1, 673*2, 673*2+1; sum those 3 numbers.
(3) If the consecutive numbers contain 673*3-1, 673*3 (0), 673*3+1 (1); sum those 3 numbers.
Otherwise:
(4) The numbers maybe: 0, 1, ..., 673; sum from 0 to 672. There are 673 numbers and the sum can be divisible by 3.
(5) The numbers maybe: 673, 674, ..., 673*2; sum those 674 numbers! (I missed that)
(6) The numbers maybe: 673*2, 673*2+1, ..., 673*3; sum from 673*2+1 to 673*3. There are 673 numbers and the sum can be divisible by 3.
Neothehero
01.10.2019 12:21
The answer is $\fbox{340}$. We proceed with two parts. Part 1: Minimality We claim that $n$ cannot be less than $340$ by proving that the 339-element sequence $335,336,337,...,673$ does not consist of required subsequences. Suppose the contrary that there exists $335 \leq a \leq 673$ and $0 \leq k \leq 673-a$ such that $2019 \mid (a)+(a+1)+(a+2)+...+(a+k)$. So $2019 \mid (k+1)(a+ \frac{k}{2}) \implies 673 \mid (k+1)(k+2a)$. Since $1 \leq k+1 \leq 674-a \leq 339$ and $2a \leq k+2a \leq 673+a \leq 2*673$, we get that, $k+2a=673 \implies (a,k)=(335,3),(336,1)$ or, $k+2a=1346 \implies (a,k)=(673,0)$. Any of these three solutions does not meet the problem condition, completing the proof. Part 2: Construction Consider $340$ consecutive integers $m,m+1,m+2,\ldots,m+339$. For $1 \leq m \leq 334$ chooses subsequence $334,335,336,337,338,339$. For $335 \leq m \leq 672$ chooses subsequence $672,673,674$. For $673 \leq m \leq 1009$ chooses subsequence $1009,1010$. For $1010 \leq m \leq 1345$ chooses subsequence $1345,1346,1347$. For $1346 \leq m \leq 1680$ chooses subsequence $1680,1681,1682,1683,1684,1685$. For $1681 \leq m \leq 2019$ just chooses only the number $2019$. Every subsequences chosen have a sum that is divisible by $2019$, so we are done.
lazizbek42
09.01.2022 21:14
Answer:$\boxed {340}$