Consider increasing integer sequences with elements from $1,\ldots,10^6$. Such a sequence is Adriatic if its first element equals 1 and if every element is at least twice the preceding element. A sequence is Tyrrhenian if its final element equals $10^6$ and if every element is strictly greater than the sum of all preceding elements. Decide whether the number of Adriatic sequences is smaller than, equal to, or greater than the number of Tyrrhenian sequences. (Proposed by Gerhard Woeginger, Austria)
Problem
Source: MMC 2014 Problem 2
Tags: combinatorics proposed, combinatorics
09.06.2014 05:46
Of course, any sequence with the first term $1$ can be given by listing its increments just as well, but what does this have to do with the Apennine peninsula?
13.06.2014 18:18
Consider increasing integer sequences with elements from $ 1 $~ $ x $. Such a sequence is Adriatic if its first element equals 1 and if every element is at least twice the preceding element. A sequence is Tyrrhenian if its final element equals x and if every element is strictly greater than the sum of all preceding elements. And let the number of Adriatic sequence be $ f(x) $, the number of Tyrrhenian sequence be $ g(x) $. Then $ f(x) $ satisfy that $ f(n)=f(n-1)+f([\frac{n}{2}]) $, and so do $ g(x) $. $ \Rightarrow f(x)=g(x) $ [we can also do: $ b_i=a_i-a_{i-1},b_m=x $ ]
13.06.2014 18:22
Remark there is more than one choice for $a_n$ to get the same Tyrrhenian sequence. Hence your conclusion doesn't seem to be correct.
26.03.2017 17:06
I will prove that the number of sequences of both types is equal for every natural number. Let us fix a certain number $n$. Let $A$ be the set of all Adriatic sequences with elements from $1,...,n$, and $T$ be the set of all Tyrrhenian sequences with elements from $1,...,n$. We will make a bijection from the elements of $T$ to the elements of $A$. Indeed let $$b_{1}, \; b_{2}, \; ... \; b_{k}, \; n$$be a sequence from $T$. Because it is Tyrrhenian we have that $b_{s+1} \ge \sum\limits_{i=1}^s b_{i} + 1$ with $1 \le s \le k$ and $b_{k+1} = n$. Observe the sequence: $$1, \; b_{1} + 1, \; b_{1} + b_{2} + 1, ... \; , \; b_{1} + b_{2} + ...+b_{k} + 1$$It's easy to see that $n \ge \sum\limits_{i=1}^{s} b_{i} + 1 \ge 2(\sum\limits_{i=1}^{s-1} b_{i} + 1)$ for $1 \le s \le k$ so this new sequence is Adriatic. It's easy to see that the same Adriatic sequence cannot be obtained in this manner from two different Tyrrhenian sequences. It remains to prove that every Adriatic sequence has a corresponding Tyrrhenian sequence. Indeed, such a sequence can be obtained from the Adriatic sequence: $$1, \; a_{1}, \; a_{2}, \; ... \; , \; a_{k} $$ as the sequence of differences between two adjacent elements of the Adriatic sequence and adding the element $n$ in the end: $$a_{1} - 1, \; a_{2} - a_{1}, \; ... \; , \; a_{k} - a_{k-1}, \; n $$ Using the inequalities $a_{i+1} \ge 2a_{i}$ we se that this sequence is Tyrrhenian, so our correspondence is a bijection and the number of both types of sequences is equal.