Problem:
Three strictly increasing sequences
of positive integers are given. Every positive integer belongs to exactly one of the three sequences. For every positive integer , the following conditions hold:
(i) ;
(ii) ;
(iii) the number is even.
Find , and .
Solutions — 2
Solution 1
Solution:
Since is a strictly increasing sequence of positive integers, it is clear that . Hence, . However, the given sequences do not contain equal terms, so and . Similarly, from (ii) and (iii), . It is also easy to see that . Let us for any count the number of terms in all three sequences that are less or equal to . There are such terms in the first sequence (that is, ), such terms in the second sequence and such terms in the third sequence . It is terms in total. By (i) any positive integer less or equal must appear among these terms exactly once; thus, the total number of these terms equals
Now we take instead of in (iv):
This means that and the number has to belong to either of the first two sequences. The inequalities imply that , , and, by (1),
Next we prove that . Indeed, number 1 has to belong to one of the given sequences, and if then or . The latter case is impossible because . Then we must have , and either , or and . In both cases we obtain a contradiction by setting in (iv). This proves that , and, together with (2), defines a unique sequence :
.
Hence,
and all the integers between and belong to the sequence . Hence, these integers have the form
and .
Answer. .
Solution 2
Solution:
Denote by the trivial fact derived at the beginning of the first solution. One can easily fill the sequences inductively. In fact, like in the first solution, we have . Now we will find the place for number 2. If , then by (iii) , which is impossible. If , then by (ii) we have , hence which is also impossible. So the only way is to put . Then by (ii) .
| 1 | 2 | 3 | 4 | 5 | ||
|---|---|---|---|---|---|---|
| 1 | ||||||
| 2 | ||||||
| 3 |
Now, because of (iv), we have . Also, , because otherwise by (*) and (ii) and there is no number left for . So we have . Then by (iii) . Also, , because otherwise by (ii) and there are no numbers left for . So we have . Using the same arguments we derive and , hence, . Now, (by (iii)). Also, , because otherwise by (ii) , and this leads to , which is not true. Hence, . Then .
| 1 | 2 | 3 | 4 | 5 | ||
|---|---|---|---|---|---|---|
| 1 | 4 | |||||
| 2 | 7 | |||||
| 3 | 5 | 6 | 8 |
Now, we can repeat the arguments from the last paragraph: Because of (iv) we have . By and (ii) we have (otherwise and there is no number left for ). So we have . By (iii), . By (ii), , therefore (otherwise there are no numbers left for ). So we have . Similarly
Finally, (by (iii)), (otherwise by (ii) , and this leads to , which is not true). Hence, and .
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 4 | 9 | ||||||||
| 2 | 7 | 14 | ||||||||
| 3 | 5 | 6 | 8 | 10 | 11 | 12 | 13 | 15 |
We formulate the claim which can be easily proved by induction. (We will skip the formal proof. However, it is just an obvious generalization of the last two paragraphs.) For and , we have
The rest is straightforward: