Maths Olympiad Prep

Library / /14 of 16

Combinatorics Difficulty 6.8 National Olympiad Prove it Spain

Consider increasing integer sequences with elements from 1,,1091, \dots, 10^9. Such a sequence is Adriatic if its first element equals 11 and if every element is at least twice the preceding element. A sequence is Tyrrhenian if its final element equals 10610^6 and if every element is strictly greater than the sum of all preceding elements. Decide whether the number of elements of Adriatic sequences is (i) smaller than or (ii) equal to or (iii) greater than the number of Tyrrhenian sequences.

Solution

Consider the Adriatic sequence a1,,an\langle a_1, \dots, a_n \rangle starting with a1=1a_1 = 1. Construct a new sequence
a21,a3a2,,anan1,106 \langle a_2 - 1, a_3 - a_2, \dots, a_n - a_{n-1}, 10^6 \rangle
from it. Note that the new sequence is Tyrrhenian, as
(a21)+(a3a2)++(anan1)=ak11<akak1 (a_2 - 1) + (a_3 - a_2) + \dots + (a_n - a_{n-1}) = a_{k-1} - 1 < a_k - a_{k-1}
holds for k=2,,n1k = 2, \dots, n-1 and as
(a21)+(a3a2)++(anan1)=an1<106. (a_2 - 1) + (a_3 - a_2) + \dots + (a_n - a_{n-1}) = a_n - 1 < 10^6.
Next, consider the Thyrrenian sequence t1,t2,,tn\langle t_1, t_2, \dots, t_n \rangle with tn=106t_n = 10^6. Construct a new sequence
1,1+t1,1+t1+t2,,1+t1++tn1 \langle 1, 1 + t_1, 1 + t_1 + t_2, \dots, 1 + t_1 + \dots + t_{n-1} \rangle
from it. Note that this new sequence is Adriatic, since
2(1+t1+t2++tk1)1+t1++tk 2(1 + t_1 + t_2 + \dots + t_{k-1}) \le 1 + t_1 + \dots + t_k
is equivalent to the Thyrrenian property t1++tk1<tkt_1 + \dots + t_{k-1} < t_k.

These two constructions yield two injections and demonstrate that the number of Adriatic sequences equals the number of Thyrrenian sequences. (In fact the second injection is the inverse of the first injection, so that we have a clean bijection between the two sets.) \Box

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.