Determine all integers $n$ for which there exist an integer $k\geq 2$ and positive integers $x_1,x_2,\hdots,x_k$ so that $$x_1x_2+x_2x_3+\hdots+x_{k-1}x_k=n\text{ and } x_1+x_2+\hdots+x_k=2019.$$
Problem
Source: 2019 Baltic Way P4
Tags: algebra
20.11.2019 20:59
This problem was proposed by Burii.
24.11.2019 18:01
We claim that the answer is all positive integers $n$ in the range $[2018, 1010 \cdot 1009].$ First let's show that no other $n$ work. Consider some $n$ which satisfies the condition of the problem. We have $(\sum_{2|i} x_i) (\sum_{2|i-1} x_i) \ge x_1x_2 + x_2x_3 + x_3x_4 + \cdots + x_{k-1} x_k = n.$ However $\sum_{2|i} x_i + \sum_{2|i-1} x_i = 2019$ and so the LHS is at most $1009 \cdot 1010.$ Hence all functional $n$ are at most $1009 \cdot 1010.$ Now, notice that if $x_i > 1$, the quantity in the problem is not increased if we instead break it up into $x_i$ $1$'s. Hence, by iterating this process we can see that the minimum possible value of $x_1 x_2 + x_2 x_3 + \cdots + x_{k-1} x_k$ is $2018.$ So all functional $n$ are in the interval $[2018, 1009 \cdot 1010].$ Let's now show that all $n$ in this interval actually work. Fix some $2018 \le n \le 1009 \cdot 1010.$ Suppose that $1 \le k \le 1008$ so that $k(2019 - k) \le n < (k+1)(2018 - k).$ Consider setting $x_1 = a, x_2 = k+1 - b, x_3 = 2018 - k - a, x_3 = b$ for some $a, b$ to be specified later. Then we have $x_1x_2 + x_2x_3 + x_3x_4 = (k+1)(2018 - k ) - ab.$ So if we could find $1 \le a \le 2018-k, 1 \le b \le k+1$ such that $ab = (k+1)(2018-k) - n$, then we'd be done. Notice that $(k+1)(2018-k) - n \le (k+1)(2018-k) - k(2019-k) = 2018 - 2k.$ Hence, we can simply set $a = (k+1)(2018 - k) - n, b = 1$ because $2018 - k \ge 2018 - 2k$. By doing the above for all $1 \le k \le 1009$, we've shown that all $n \in [2018, 1009 \cdot 1010]$ indeed satisfy the condition of the problem. Therefore, we've shown that the answer is all $n$ in $[2018, 1009 \cdot 1010].$ $\square$
23.10.2020 05:31
example for $n=1009\cdot 1010$ ?
23.10.2020 05:59
Jjesus wrote: example for $n=1009\cdot 1010$ ? Clearly $x_1=1009$ and $x_2=1010$ works
15.07.2021 17:38
explain pls, i can't understand this Pathological wrote: Suppose that $1 \le k \le 1008$ so that $k(2019 - k) \le n < (k+1)(2018 - k).$