Maths Olympiad Prep

Library / /21 of 63

Algebra Difficulty 6.5 National olympiad Prove it Japan

Let cc be a non-negative integer. Find all sequences of positive integers {an}n1\{a_n\}_{n \ge 1} such that for any positive integer nn, the following condition holds:
There are exactly ana_n positive integers ii satisfying aian+1+ca_i \le a_{n+1} + c.

Solution

Assume that an+1an+2a_{n+1} \ge a_{n+2} holds for some positive integers nn. Since any positive integer ii with aian+2+ca_i \le a_{n+2} + c must also satisfy aian+1+ca_i \le a_{n+1} + c, it follows that anan+1a_n \ge a_{n+1}. Hence, if an<an+1a_n < a_{n+1} holds for some positive integer nn, then an+1<an+2a_{n+1} < a_{n+2} follows, and by induction, we have an<an+1<an+2<an+3<a_n < a_{n+1} < a_{n+2} < a_{n+3} < \dots.

Similarly, when an>an+1a_n > a_{n+1} holds for some positive integer nn, we have an>an+1>an+2>a_n > a_{n+1} > a_{n+2} > \dots, especially an+danda_{n+d} \le a_n - d for any non-negative integer dd. This leads to a contradiction since an+an0a_{n+a_n} \le 0.

Suppose that an=an+1a_n = a_{n+1} for all positive integers nn. Then, as all integers i2i \ge 2 satisfy ai=a2a2+ca_i = a_2 \le a_2 + c, this contradicts the fact that there are exactly a1a_1 positive integers ii satisfying it. Therefore, there exists a positive integer kk such that ak<ak+1a_k < a_{k+1}, and from the above discussion, we have a1a2ak<ak+1<ak+2<a_1 \le a_2 \le \dots \le a_k < a_{k+1} < a_{k+2} < \dots.

For integers nkn \ge k, since any integer i>n+c+1i > n+c+1 satisfies ai>an+c+1an+1+ca_i > a_{n+c+1} \ge a_{n+1} + c, we have ann+c+1a_n \le n+c+1. Therefore, if we set bn=annb_n = a_n - n (nkn \ge k), then we have bnc+1b_n \le c+1 and bkbk+1bk+2b_k \le b_{k+1} \le b_{k+2} \le \dots. Thus, there exist an integer dd and an integer MkM \ge k such that for nMn \ge M, bn=db_n = d, i.e., an=n+da_n = n+d. Since a1a2aM+c+1<aM+c+2<a_1 \le a_2 \le \dots \le a_{M+c+1} < a_{M+c+2} < \dots, for any positive integer ii, aiaM+1+c=aM+c+1a_i \le a_{M+1}+c = a_{M+c+1} and iM+c+1i \le M+c+1 are equivalent. Therefore, aM=M+c+1a_M = M+c+1, which is also equal to M+dM+d, and for integers nMn \ge M, we have an=n+c+1a_n = n+c+1.

Suppose that for an integer N2N \ge 2, we have an=n+c+1a_n = n+c+1 for all nNn \ge N. Since a1a2aN+c<aN+c+1<a_1 \le a_2 \le \dots \le a_{N+c} < a_{N+c+1} < \dots, for any positive integer ii, aiaN+c=aN+ca_i \le a_N + c = a_{N+c} and iN+ci \le N+c are equivalent. Therefore, aN1=N+ca_{N-1} = N+c.

Thus, by induction, we have an=n+c+1a_n = n+c+1 for any positive integer nn. This indeed satisfies the problem condition because aian+1+ca_i \le a_{n+1} + c and iani \le a_n are equivalent for any positive integer ii.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.