14
$\begingroup$

Let $n$ be greater or equal to $1$, and let $S$ be an $(n+1)$-subset of $[2n]$. Prove that there exist two numbers in $S$ such that one divides the other.

Any help is appreciated!

$\endgroup$
14
$\begingroup$

HINT: Create a pigeonhole for each odd positive integer $2k+1<2n$, and put into it all numbers in $[2n]$ of the form $(2k+1)2^r$ for some $r\ge 0$.

$\endgroup$
  • 1
    $\begingroup$ Ok, so for any set S=(1, 2, ..., 2n), we choose all odd numbers from that S, so So=(1, 3,...,2k+1) such 2k+1 < 2n. For each element in S choose those that satisfy (2k+1)2^r, which are multiples of each element in So. Let this set be S2 = (2, 6,...,(2k+1)2^r), as long as (2k+1)2^r < 2n. S2 is necessarily bigger than So, and thus, each element in So can be 'mapped' to multiple multiples of itself. Consequently, any set bigger than S, of size n+1, must also have this property. Is this reasoning correct? $\endgroup$ – user64093 Feb 26 '13 at 18:38
  • $\begingroup$ I just love this proof, I saw it in 1999 but forgot how to do it so I'm glad to find it here. Your answer is a bit terse tho, I had to stare at it for a while, a novice might have trouble following it. $\endgroup$ – Gregory Grant May 29 '15 at 3:09
  • $\begingroup$ @Gregory: Well, it was intended just to be a (fairly generous) hint. $\endgroup$ – Brian M. Scott May 29 '15 at 3:19
  • $\begingroup$ @BrianM.Scott I got ya. I did go ahead and post an answer with more details. Hope you don't take that wrong, it's not criticism of your answer, it's homage to it. $\endgroup$ – Gregory Grant May 29 '15 at 3:22
9
$\begingroup$

I thought it would be worthwhile to write out Brian's proof with more detail.

Let $A=\{1,2,\dots,2n\}$. Write $A=E\cup O$ where $E$ are the evens and $O$ are the odds. Then $|O|$, the size of $O$, is $n$. Now let $x\in A$. Then by the unique factorization of integers we can write $x=2^ab$ where $b$ is odd. The association $f:x\mapsto b$ therefore gives a well defined mapping $A\rightarrow O$. Since $|O|=n$, $|f(C)|\leq n$ for any subset $C\subseteq A$. Therefore, if $C\subseteq A$ has $n+1$ elements, there must be two elements $c_1,c_2\in C$ such that $f(c_1)=f(c_2)$. In other words $c_1=2^{a_1}b$ and $c_2=2^{a_2}b$. So if $a_1<a_2$ then $c_1$ divides $c_2$. Otherwise $a_1>a_2$ and $c_2$ divides $c_1$. Q.E.D.

$\endgroup$
  • $\begingroup$ Sorry for reviving this thread. I wish to understand why we can write $x = 2^ab$ based on the unique factorization of integers. $\endgroup$ – LanceHAOH Nov 27 '17 at 16:21
  • $\begingroup$ @LanceHAOH Because $2$ is prime. We can factor any positive integer into a product of powers of distinct primes $p_1^{a_1}\cdots p_n^{a_n}$. At most one of those primes can be $2$. $\endgroup$ – Gregory Grant Nov 27 '17 at 16:42
  • $\begingroup$ If I understood you correctly, we multiply all $p_i^{a_i}$ where $p_i^{a_i}$ is odd. This result, b, is still odd. Since factorization of integers is unique, only integers with the same b and conseqentially $2^ab$ will be mapped to the same partition. $\endgroup$ – LanceHAOH Nov 27 '17 at 23:35
  • $\begingroup$ @LanceHAOH Sounds good $\endgroup$ – Gregory Grant Nov 28 '17 at 2:46
3
$\begingroup$

I realize this question is old, but I solved it recently when someone else asked me how to prove it.

The proof I came up with doesn't use the pigeonhole principle, instead it uses Mathematical Induction:

Assume the statement is true for $[{1,2,....,2k}]$

Consider the set $P$= $[{1,2,.....,2k,2k+1,2k+2} ]$

Its easier if we partition it, so we have:

$P_1$ = $[{1,2,....,2k}]$ ,$P_2$ =$ [{2k+1,2k+2}]$

We have to select at least $k$ items from $P_1$ as if we select any less than $k$ items from $P_1$, say we select $k-1$, then the additional three items must come from $P_2$, but this is impossible, as $P_2$ only has two items , so we assume the worst case, and select exactly $k$ items from $P_1$. If we were to select more, by our inductive hypothesis, the proof would be complete.

Okay, lets say our selection is $S_k$ .

Now since it is the worst case, we select our remaining two items $2k+1$ and $2k+2$, as if we selected the remaining two items from $P_1$ we would already be done, by our inductive hypothesis.

Consider $2k+2 = 2(k+1)$ . Clearly $k+1 | 2k+2 $

If we choose $k+1$ as part of $S_k$, we are done.

If we did not choose $k+1$ as part of $S_k$ it is part of $P_1 - S_K$ .

Now consider $S_k \cup \ k+1 $

Something in $S_k$ MUST divide $k+1$ or $k+1$ MUST divide something in $S_k$. This is because $S_k \cup \ k+1$ contains $k+1$ items, so by our inductive hypothesis this must be the case. But if $k+1$ divides something in $S_k$, we have a contradiction, as the least multiple of $k+1$ is $2k+2$, which is certainly not in $S_k$.

So something in $S_k$ MUST divide $k+1$ .

If something in $S_K$ divides $k+1$, then something in $S_k$ divides $2k+2$, and the proof is complete.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.