Pigeon Hole Principle x

Question

How many different numbers must be selected from the first 25 positive integers to be certain that at least one of them will be twice the other ?

Answer 1

Here's how I did it. Group the integers we get by doubling

A:$1,2,4,8,16$

B:$3,6,12,24$

C:$5,10,20$

D:$7,14$

E:$9,18$

F:$11,22$

We have $7$ odd numbers from $13$ to $25$ not included and we can take them all. We can take $1$ each from groups $F$, $E$, and $D$, $2$ each from groups $C$ and $B$ and $3$ from group $A$ giving $17$ at most with no doubles, so if we choose 18, we are certain of having a double.

Answer 2

Generalizing saulspatz' answer: partition $\{1,\dots, n\}$ into groups of the form $G_a=\{a\cdot2^k\}$, where $a$ is odd. There are $\lceil n/2 \rceil$ such groups, one for each odd number on $\{1,\dots, n\}$.

On each group $G_a$, we can alternate between picking a number $($starting from $a)$ and not picking its double. In this way, we'll be able to pick $\lceil |G_a|/2\rceil$ numbers from each group. This is the most we can do without infringing on the double rule. Adding any one number will result in there being a guaranteed double pair, and yields the answer.

The answer therefore has the form

$$1+\sum_{k=1}^{\lceil n/2 \rceil}\left\lceil \frac{\left|G_{2k-1}\right|}2 \right\rceil.$$

We can calculate $\left|G_{2k-1}\right|$. We have $G_a = \{a\cdot 2^k\,|\,k=0,\dots, k_a\}$ where $k_a$ is the maximum integer $k$ such that $a\cdot 2^k \leq n$. It follows that

$$k\leq \log_2(n/a) \implies k_a = \left\lfloor\log_2(n/a)\right\rfloor$$

and hence $|G_a| = 1+ \left\lfloor\log_2(n/a)\right\rfloor$. Therefore, the answer is

\begin{align} 1+\sum_{k=1}^{\lceil n/2 \rceil}\left\lceil \frac{1+ \left\lfloor\log_2\left(\frac{n}{2k-1}\right)\right\rfloor}2 \right\rceil &= 1+\sum_{k=1}^{\lceil n/2 \rceil}\left\lceil \frac{ \left\lfloor1+\log_2\left(\frac{n}{2k-1}\right)\right\rfloor}2 \right\rceil \\&= 1+\sum_{k=1}^{\lceil n/2 \rceil}\left\lceil \frac{ \left\lfloor \log_2(2)+\log_2\left(\frac{n}{2k-1}\right)\right\rfloor}2 \right\rceil \\&= 1+\sum_{k=1}^{\lceil n/2 \rceil}\left\lceil \frac{ \left\lfloor \log_2\left(\frac{2n}{2k-1}\right)\right\rfloor}2 \right\rceil \end{align}

You can check that for $n=25$ this yields the answer of $18$, as expected. Curiously, this is consistently very close to $\frac23n$ for large $n$. I don't quite know why.

---

EDIT: Okay, I got a convincing heuristic (convincing to me, at least) as to why the answer is close to $\frac23n$. In keeping with the notation above, for each value of $k=0,2,4,\dots$ $($the values of $k$ we don't skip when building a maximal set without a double pair$)$, we will count the number of values $a$ for which $k_a \geq k$. We hence have:

\begin{align} \sum_{j\geq 0}\, |\{a\,:\, a \,\text{ is odd and }\, k_{a}\geq 2j\}| &= \sum_{j\geq 0}\, |\{a\,:\, a \,\text{ is odd and }\, a\leq n/2^{2j}\}| \\&\simeq \frac12\,\sum_{j\geq 0}\, |\{a\,:\, a\leq n/2^{2j}\}| \\&\simeq \frac12\,\sum_{j\geq 0}\, \frac{n}{4^{j}} \\&= \frac{n}2\cdot\frac{1}{1-\frac14} = \frac{n}2 \cdot \frac43 = \frac23n \end{align}