0
$\begingroup$

I'm unsure how to apply the pigeonhole principle to this problem.

Prove that for any choice of $7$ distinct numbers from the set of integers from $1$ to $126$ inclusive, there will always be two numbers $x$ and $y$ such that $x<y≤2x$.

In this context, I'm unsure what would be regarded as the "pigeons" and the "pigeonholes" or how to incorporate them.

Thanks for any help anyone can provide.

$\endgroup$
2
  • 5
    $\begingroup$ Basically if you pick any two numbers from the set {$x,x+1,...2x$}, the property will always be satisfied. Try to divide $\{1,2,..126\}$ into 6 such sets. $\endgroup$
    – Rainbow
    Feb 8, 2014 at 4:06
  • $\begingroup$ did you observe that $2^7=128$ has a close relation with this problem? $\endgroup$
    – Hawk
    Feb 8, 2014 at 5:10

2 Answers 2

Reset to default
4
$\begingroup$

Take the pigeonholes to be the following 6 sets. $$\{1, 2\}, \{3, 4, 5, 6\}, \{7, 8, .. 14\}, \{15, 16, .. 30\}, \{31, 32,.. 62\}, \{63, 64.. 126\}$$

The sets collectively form the natural numbers from 1 to 126 inclusive. There are $6$ holes and $7$ pigeons implying at least two natural numbers must be chosen from the same set.

Each set is of the form $\{p, p +1, p+2,.. 2p\}$. Let $x, y$ be the two elements chosen from the same set. Without loss of generality we may assume $x \lt y$ but $y \le 2p$ and $p \le x$, $\implies y \le 2x $

$\endgroup$
2
$\begingroup$

Hint: The choice of $126$ suggests the conclusion is not true for $127$. See if you can construct a counterexample for $127$. (Further hint: If there is a counterexample, one of the $7$ numbers must be $127$. Why?)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .