Maths Olympiad Prep

Library / /5 of 8

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Middle European Mathematical Olympiad (MEMO)

Problem:
Three strictly increasing sequences
a1,a2,a3,,b1,b2,b3,,c1,c2,c3, a_{1}, a_{2}, a_{3}, \ldots, \quad b_{1}, b_{2}, b_{3}, \ldots, \quad c_{1}, c_{2}, c_{3}, \ldots
of positive integers are given. Every positive integer belongs to exactly one of the three sequences. For every positive integer nn, the following conditions hold:
(i) can=bn+1c_{a_{n}}=b_{n}+1;
(ii) an+1>bna_{n+1}>b_{n};
(iii) the number cn+1cn(n+1)cn+1ncnc_{n+1} c_{n}-(n+1) c_{n+1}-n c_{n} is even.
Find a2010,b2010a_{2010}, b_{2010}, and c2010c_{2010}.

Solutions — 2

Solution 1

Solution:
Since {cn}\{c_{n}\} is a strictly increasing sequence of positive integers, it is clear that cnn,nNc_{n} \geq n, n \in \mathbb{N}. Hence, canan,nNc_{a_{n}} \geq a_{n}, n \in \mathbb{N}. However, the given sequences do not contain equal terms, so can>anc_{a_{n}}>a_{n} and bn=can1>an,nNb_{n}=c_{a_{n}}-1>a_{n}, n \in \mathbb{N}. Similarly, from (ii) and (iii), an+1>bn+1=can,nNa_{n+1}>b_{n}+1=c_{a_{n}}, n \in \mathbb{N}. It is also easy to see that bn<can<bn+1b_{n}<c_{a_{n}}<b_{n+1}. Let us for any nNn \in \mathbb{N} count the number of terms in all three sequences that are less or equal to canc_{a_{n}}. There are nn such terms in the first sequence (that is, a1,a2,,ana_{1}, a_{2}, \ldots, a_{n} ), nn such terms in the second sequence (b1,b2,,bn)\left(b_{1}, b_{2}, \ldots, b_{n}\right) and ana_{n} such terms in the third sequence (c1,c2,,can)\left(c_{1}, c_{2}, \ldots, c_{a_{n}}\right). It is 2n+an2 n+a_{n} terms in total. By (i) any positive integer less or equal canc_{a_{n}} must appear among these terms exactly once; thus, the total number of these terms equals
2n+an=can 2 n+a_{n}=c_{a_{n}}
Now we take ana_{n} instead of nn in (iv):
can+1can(an+1)can+1ancan=can+1(an+2n)(an+1)can+1an(an+2n)==can+1(2n1)an22anncan+1an2ncan+1can0(mod2) \begin{aligned} & c_{a_{n}+1} c_{a_{n}}-\left(a_{n}+1\right) c_{a_{n}+1}-a_{n} c_{a_{n}}=c_{a_{n}+1}\left(a_{n}+2 n\right)-\left(a_{n}+1\right) c_{a_{n}+1}-a_{n}\left(a_{n}+2 n\right)= \\ & =c_{a_{n}+1}(2 n-1)-a_{n}^{2}-2 a_{n} n \equiv c_{a_{n}+1}-a_{n}-2 n \equiv c_{a_{n}+1}-c_{a_{n}} \equiv 0 \quad(\bmod 2) \end{aligned}
This means that can+1can+1c_{a_{n}+1} \neq c_{a_{n}}+1 and the number can+1c_{a_{n}}+1 has to belong to either of the first two sequences. The inequalities an<bn<can<an+1<bn+1a_{n}<b_{n}<c_{a_{n}}<a_{n+1}<b_{n+1} imply that can+1=an+1c_{a_{n}}+1=a_{n+1}, nNn \in \mathbb{N}, and, by (1),
an+1=an+2n+1,nN a_{n+1}=a_{n}+2 n+1, \quad n \in \mathbb{N}
Next we prove that a1=1a_{1}=1. Indeed, number 1 has to belong to one of the given sequences, and if a1>1a_{1}>1 then c1=1c_{1}=1 or b1=1b_{1}=1. The latter case is impossible because b1>a1b_{1}>a_{1}. Then we must have c1=1c_{1}=1, and either c2=2c_{2}=2, or a1=2a_{1}=2 and ca1=c2=a1+2=4c_{a_{1}}=c_{2}=a_{1}+2=4. In both cases we obtain a contradiction by setting n=1n=1 in (iv). This proves that a1=1a_{1}=1, and, together with (2), defines a unique sequence {an}\{a_{n}\} :
an=an1+(2n1)=an2+(2n3)+(2n1)==a1+3+5++(2n1)=n2,nNa_{n}=a_{n-1}+(2 n-1)=a_{n-2}+(2 n-3)+(2 n-1)=\cdots=a_{1}+3+5+\ldots+(2 n-1)=n^{2}, \quad n \in \mathbb{N}.
Hence,
a2010=20102b2010=ca20101=a2010+220101=201122c1936=c442=ca44=a44+244=442+88=2024a45=452=2025 \begin{aligned} a_{2010} & =2010^{2} \\ b_{2010} & =c_{a_{2010}}-1=a_{2010}+2 \cdot 2010-1=2011^{2}-2 \\ c_{1936} & =c_{44^{2}}=c_{a_{44}}=a_{44}+2 \cdot 44=44^{2}+88=2024 \\ a_{45} & =45^{2}=2025 \end{aligned}
and all the integers between a45a_{45} and b45=ca451=a45+2451=a45+89b_{45}=c_{a_{45}}-1=a_{45}+2 \cdot 45-1=a_{45}+89 belong to the sequence {cn}\{c_{n}\}. Hence, these integers have the form
c1936+k=a45+k,k=1,2,,88 c_{1936+k}=a_{45}+k, \quad k=1,2, \ldots, 88
and c2010=c1936+74=a45+74=2099c_{2010}=c_{1936+74}=a_{45}+74=2099.
Answer. a2010=20102,b2010=201122,c2010=2099a_{2010}=2010^{2}, b_{2010}=2011^{2}-2, c_{2010}=2099.

Solution 2

Solution:
Denote by ()(*) the trivial fact an<cana_{n}<c_{a_{n}} derived at the beginning of the first solution. One can easily fill the sequences inductively. In fact, like in the first solution, we have a1=1a_{1}=1. Now we will find the place for number 2. If a2=2a_{2}=2, then by (iii) 2=a2>b12=a_{2}>b_{1}, which is impossible. If c1=2c_{1}=2, then by (ii) we have 2=c1=ca1=b1+12=c_{1}=c_{a_{1}}=b_{1}+1, hence b1=1b_{1}=1 which is also impossible. So the only way is to put b2=2b_{2}=2. Then by (ii) c1=ca1=b1+1=3c_{1}=c_{a_{1}}=b_{1}+1=3.

nn12345\ldots
ana_{n}1
bnb_{n}2
cnc_{n}3

Now, because of (iv), we have c24c_{2} \neq 4. Also, b24b_{2} \neq 4, because otherwise by (*) and (ii) a2<ca2=b2+1=5a_{2}<c_{a_{2}}=b_{2}+1=5 and there is no number left for a2a_{2}. So we have a2=4a_{2}=4. Then by (iii) a35a_{3} \neq 5. Also, b25b_{2} \neq 5, because otherwise by (ii) c4=ca2=b2+1=6c_{4}=c_{a_{2}}=b_{2}+1=6 and there are no numbers left for c2,c3c_{2}, c_{3}. So we have c2=5c_{2}=5. Using the same arguments we derive a36a_{3} \neq 6 and b26b_{2} \neq 6, hence, c3=6c_{3}=6. Now, a37a_{3} \neq 7 (by (iii)). Also, c47c_{4} \neq 7, because otherwise by (ii) 7=c4=ca2=b2+17=c_{4}=c_{a_{2}}=b_{2}+1, and this leads to b2=6b_{2}=6, which is not true. Hence, b2=7b_{2}=7. Then c4=ca2=b2+1=8c_{4}=c_{a_{2}}=b_{2}+1=8.
nn12345\ldots
ana_{n}14
bnb_{n}27
cnc_{n}3568

Now, we can repeat the arguments from the last paragraph: Because of (iv) we have c59c_{5} \neq 9. By ()(*) and (ii) we have b39b_{3} \neq 9 (otherwise a3<ca3=b3+1=10a_{3}<c_{a_{3}}=b_{3}+1=10 and there is no number left for a3a_{3} ). So we have a3=9a_{3}=9. By (iii), a410a_{4} \neq 10. By (ii), c9=ca3=b3+1c_{9}=c_{a_{3}}=b_{3}+1, therefore b310b_{3} \neq 10 (otherwise there are no numbers left for c5,,c8c_{5}, \ldots, c_{8} ). So we have c5=10c_{5}=10. Similarly
a411,b311c6=11a412,b312c7=12a413,b313c8=13 \begin{aligned} & a_{4} \neq 11, b_{3} \neq 11 \quad \Longrightarrow \quad c_{6}=11 \\ & a_{4} \neq 12, b_{3} \neq 12 \quad \Longrightarrow \quad c_{7}=12 \\ & a_{4} \neq 13, b_{3} \neq 13 \quad \Longrightarrow \quad c_{8}=13 \end{aligned}
Finally, a414a_{4} \neq 14 (by (iii)), c914c_{9} \neq 14 (otherwise by (ii) 14=c9=ca3=b3+114=c_{9}=c_{a_{3}}=b_{3}+1, and this leads to b3=13b_{3}=13, which is not true). Hence, b3=14b_{3}=14 and c9=ca3=b3+1=15c_{9}=c_{a_{3}}=b_{3}+1=15.
nn123456789\ldots
ana_{n}149
bnb_{n}2714
cnc_{n}35681011121315

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 kNk \in \mathbb{N} and i=1,2,,2k2i=1,2, \ldots, 2 k-2, we have
ak=k2bk=k2+2k1c(k1)2+i=k2+ick2=k2+2k \begin{aligned} & a_{k}=k^{2} \\ & b_{k}=k^{2}+2 k-1 \\ & c_{(k-1)^{2}+i}=k^{2}+i \\ & c_{k^{2}}=k^{2}+2 k \end{aligned}
The rest is straightforward:
a2010=20102,b2010=20102+220101,c2010=c442+74=452+74=2099 a_{2010}=2010^{2}, \quad b_{2010}=2010^{2}+2 \cdot 2010-1, \quad c_{2010}=c_{44^{2}+74}=45^{2}+74=2099

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 reproduced verbatim; metadata (topic, difficulty) added by this project.