Ordering sequences of prime decompositions

Question

C.f. Engel's Problem Solving Strategies; p. 132, #33:

Out of $n+1$ integers $\leq 2n$, find $p,q$ s.t. $p|q$.

Rather than soliciting a solution I'm wondering if there's a way I can make my attempt complete.... Please don't spoil the problem with random solutions! :-)

We can show there are at most $n$ primes $1\leq p\leq 2n$; call them $p_1,p_2,\dots,p_k$; $k\leq n$. Letting $s\in\{1,2,\dots, 2n\}$, write $s$ uniquely in prime-power form: $s=p_1^{s_1}p_{2}^{s_2}\dots p_k^{s_k}$. Define $\sigma(s)=(s_1,s_2,\dots,s_k)$. On the set $\{\sigma(s):1\leq s\leq 2n\}$, put a partial order $\sigma(s)\leq \sigma(t)\iff s_i\leq t_i $ for $1\leq i\leq k$, where $\sigma(t)=(t_1,t_2,\dots,t_k)$. It is clear that $s|t\iff \sigma(s)\leq \sigma(t)$. The problem is reduced to showing that out of all $n+1$ sequences, at least $2$ must be related.

To me, all that seems to remain is a combinatorics problem. Suppose that all $n+1$ sequences cannot be related. Why is this a contradiction? I can see why in a couple of extreme cases but not in the general case. Struggling to find the pigeonhole so to speak. Any hints?

Answer 1

First, I believe the actual problem can be more explicitly stated as something like

Out of $n + 1$ distinct positive integers $\le 2n$, prove you can find distinct $p,q$ s.t. $p \mid q$.

The "pigeonhole", so to speak, occurs when you check just one prime, i.e., $2$, and just treat potential values of the odd part of each integer as a separate group. Doing this simplifies your solution attempt to something which can then be fairly easily shown, such as I've done below. In particular, note each integer $1 \le i \le 2n$ can be uniquely expressed as a product of some power of $2$ (including just a power of $0$) and an odd part, i.e.,

$$i = 2^j k, \text{ with } j \ge 0, \gcd(k,2) = 1 \tag{1}\label{eq1A}$$

The range $1$ to $2n$ has $n$ odd integers which $k$ can represent, i.e., $1, 3, 5, \ldots, 2n - 1$. Since there are $n + 1$ distinct integers which have been selected, by the Pigeonhole principle, at least $2$ of them, call them $p$ and $q$ with $q \gt p$, have the same $k$, say $k_1$, i.e.,

$$p = 2^{j_1}k_1, \; q = 2^{j_2}k_1 \text{ with } j_2 \gt j_1 \tag{2}\label{eq2A}$$

Thus, $q = \left(2^{j_2 - j_1}\right)p$ meaning that $p \mid q$.