7 distinct positive integers with pigeonhole principle

Question

Prove that if you choose 7 distinct positive integers that every integer less than $127$, you will find at least one pair $(a,b)​$ such that $b<a\le 2b$.

I tried to create sets to use pigeon hole principle to proof this. Please provide hints.

Answer 1

Hint : $127 = 2^7 - 1$.

Consider the sets $\{2^{k},...,2^{k+1} -1\}$ for $k=0,1,2,3,4,5$. For example, these would be $\{1\}, \{2,3\}, \{4,5,6,7\}$ and so on. These are seven subsets.

• Prove that if $a>b$ belong in the same subset, then $2b\geq a > b$.

• Show that if seven numbers sum to less than $127$ then at least two of them belong in the same subset.

Answer 2

Or without Pigeon-Hole: Seven distinct positive integers can be arranged in order as $$ 1\le a_1<a_2<a_3<a_4<a_5<a_6<a_7.$$ If no pair $(a,b)$ with $b<a\le 2b$ exists, we conclude $$ a_{i+1}\ge 2a_i+1\quad \text{for }1\le i\le 6.$$ Hence $$a_7\ge 2a_6+1\ge 4a_5+3\ge \ldots \ge 64a_1+63 \ge 127$$ and more generally $$a_i\ge 2^i-1 $$ and so $$ a_1+\cdots+a_7\ge 1+3+7+\cdots+127=247\gg 127.$$