Incredibly troll. We can actually make the set of $a_i+b_i$ to be the set $a_k-i$ for $i=0,1, \ldots, k-1$. First, put $b_i=0$ if $a_i>a_k-k$, and then match from largest to smallest the remaining $a_i$ to the smallest remaining $a_k-k+j$, and set $b_i$ as the diffrence. This suffices.

This is the idea

trivial by jensen, skill issue.

Marinchoo wrote: Incredibly troll. We can actually make the set of $a_i+b_i$ to be the set $a_k-i$ for $i=0,1, \ldots, k-1$. First, put $b_i=0$ if $a_i>a_k-k$, and then match from largest to smallest the remaining $a_i$ to the smallest remaining $a_k-k+j$, and set $b_i$ as the diffrence. This suffices. How to consider this idea, I couldn't get it during the contest for 3 hours

falantrng wrote: Let $n \ge k \ge 3$ be integers. Show that for every integer sequence $1 \le a_1 < a_2 < . . . < a_k \le n$ one can choose non-negative integers $b_1, b_2, . . . , b_k$, satisfying the following conditions: $0 \le b_i \le n$ for each $1 \le i \le k$, all the positive $b_i$ are distinct, the sums $a_i + b_i$, $1 \le i \le k$, form a permutation of the first $k$ terms of a non-constant arithmetic progression. The problem is very tricky. It asks for arithmetic sequence, while you can just consider the sequence of consecutive numbers, only this makes problem harder one.

X.Allaberdiyev wrote: Marinchoo wrote: Incredibly troll. We can actually make the set of $a_i+b_i$ to be the set $a_k-i$ for $i=0,1, \ldots, k-1$. First, put $b_i=0$ if $a_i>a_k-k$, and then match from largest to smallest the remaining $a_i$ to the smallest remaining $a_k-k+j$, and set $b_i$ as the diffrence. This suffices. How to consider this idea, I couldn't get it during the contest for 3 hours Here is (my) motivation behind the solution: play around with small $n$, $k$, and fixed $a_i$. Intuitively, due to size reasons, the common difference in the arithmetic sequence can be no more than $2$ for big $n$ if $k\approx n$, so we only look at these solutions for the small cases. You can quickly reject the idea of common difference $2$ by comparing the number of solutions with difference $1$ to the number of solutions with difference $2$. Now that you're thinking about consecutive numbers, consider the solutions you get for the small cases and notice that choosing the largest number to be $a_k$ works fine. The finish from there is straightforward.

For a solution involving induction. We induct on n with the claim: - For all $n \geq k \geq 3$ there exist $b_i$ which fulfil the problem condition as well as: - either all $b_i$ are 0 - the only time we have $b_i$= 0 is if $a_{k-s}= n-s$ in which case $b_t= 0 $ for all $ t \geq k-s$ The base case $ n=3$ is obvious. Assume it is true for $n=q$, and now we prove it for $q+1$ Now obviously if $k=q+1$ the result is obvious. From here on assume $k<=q$. If $a_k<q+1$ then our $b_i$ exist by induction. So now we have to show that our desired $b_i$ exist for a sequence $(a_1,... a_s, q-f, q-f +1,...,q+1)$, $f$ could also be -1, whats important that starting from $a_k=q+1$ there exists an index $s$ such that $a_s< a_(s+1)-1$. If this is not the case then the sequence is already an arithmetic progresion. Now consider the $b_i $ for the sequence $(a_1,...a_s, a_{s+1}-1,a_{s+2}-1,...,q)$. Notice by our induction claim , $b_i=0 $ for $ s+1<=i<=k$ and only these b. So now perform the following operation: If $b_i=0$, replace $a_i $with $ a_i +1$ Else replace $b_i $ with $b_i +1$. It is not difficult to see that these $b_i $ work.

nvm this is wrong

Very Nice : The arithmetic sequence $a_i+b_i$ can be a permutation of $\{n-(k-1),n-(k-2),\dots,n-1,n\}$. If any $a_i$ already belong to this set let their corresponding $b_i$ be equal to zero. Notice that all the remaining $a_i$ are smaller than any term remaining in this sequence. Now we can assign the largest remaining $a_i$ to the smallest term left in the sequence. Repeating this will solve the problem.

Proposed by Romania!

It seems not many people got the hint that number 2 implies that the desired configuration is very simple (I personally would not expect it either), but it is a somewhat fun "experiment" to talk about to future generations. Too bad nobody figured out (so far) an alternative construction, it would deserve a special prize during the competition.

This was the original wording of this problem in the shortlist. Somehow the jury decided to change the statement. This statement of course is absolutely the same, but a student in my team got confused with this sentence: "all the positive $b_i$ are distinct". I think the game wording was a bit clearer about that. Do you think so?

Attachments:

That was my original wording. I would also challenge you to determine if the resulted progression can be with ratio 2, for any given sequence $(a_i)_i$.

We will show that we can choose the $b_i$ such that the terms of the arithmetic progression are $\{n-k+1,n-k+2,\ldots,n\}$. We proceed by induction with the base case being clear because we can extend the problem to $k\ge 1$. Now suppose we have $1\le a_1<\ldots<a_{k+1}\le n$. Clearly, all the $a_i$ with $i\le k$ are at most $n-1$ so we can find $b_i$ for $i\le k$ such that $a_i+b_i$ form the set $\{n-k,n-k+1,\ldots,n-1\}$ for $i\le k$. Now if $a_{k+1}=n$ we can just pick $b_{k+1}=0$ and we are done. Therefore, we will suppose that $a_{k+1}\le n-1$. After doing the same process on $a_2,a_3,\ldots,a_{k+1}$, we get that $a_i+b_i$ form the set $\{n-k,n-k+1,\ldots,n-1\}$ for $2\le i\le k+1$. Now let $b_1=n-a_1$. It is not hard to see that this is the bigger than all the other $b$s so we are done. $\blacksquare$

Free-like ahh question. Notice that the condition ii is really suspicious as it means you can have zeros if you wanted, which makes us think that you can actually, setup the "arithmetic" sequence to have values close to the original sequence. Therefore we are gonna make a use of that inmediately, from base cases also check that the construction actually has to be very simple so we will in fact just consider the last $k$ terms before reaching $a_k+1$, if an $a_i$ is already there just ser $b_i=0$, now suppose that we have set all terms from $a_j$ to $a_k$ to have their $b=0$ so assign $a_1$ a $b_1$ so that it is largest value not taken before from the last $k$ terms before reaching $a_k$, then repeat for $a_2$ and so on until $a_{j-1}$, this way no two differences can be equal as they are strictly decreasing, thus we are done .