Given a set of n+1 numbers from 1,2....,2n . How to prove by induction that there exists two numbers in the set such that one divides the other ???
4
-
$\begingroup$ Actually, one is twice the other. Here pigeonhole seems better than induction. Consider the n subsets {1,2},{2,4},..,{n,2n}. $\endgroup$– Pietro MajerCommented Jul 22, 2010 at 10:08
-
3$\begingroup$ This is a problem for the epsilons :) $\endgroup$– Gjergji ZaimiCommented Jul 22, 2010 at 10:12
-
2$\begingroup$ @Pietro: I dont think one has to be twice of the other. In the classical solution one considers the n chains C_k={k,2k,4k,...} for $k\in \{1,3,5,\dots, 2n-1\}$ and then use the pigeonhole principle. $\endgroup$– Gjergji ZaimiCommented Jul 22, 2010 at 10:22
-
$\begingroup$ oops! . $\endgroup$– Pietro MajerCommented Jul 22, 2010 at 10:44
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Assume we have the statement for 2n, and we are given n+2 numbers up to 2n+2. If n+1 amon them are at most 2n, then we are done by induction. So only n of them can be at most 2n, that is, 2n+1 and 2n+2 are among the numbers. Then n+1 is not among the numbers (as n+1 divides 2n+2). We can now replace 2n+2 by n+1 and still keep the condition. This is a contradiction, as now we have n+1 numbers up to 2n. QED.
answered Jul 22, 2010 at 10:39
$\begingroup$
$\endgroup$
3
As Gjergji points out, I believe this is a problem that Erdos liked to test young children with, and the classical solution uses the pigeonhole principle. However, I will answer the OP's question, since there is indeed a proof by induction.
Clearly, the claim holds for $n=1$. Now, assume that it holds for $n-1$, and consider a subset $X$ of size $n+1$ from $[2n]$. If $X$ contains at least $n$ elements from $[2n-2]$, then we are done by induction. So, $X$ must contain both $2n-1$ and $2n$. Now, if $n \in X$, we are done. So, let $X'$ be obtained from $X$ by removing $2n$ and adding $n$. By induction, $X'$ contains two numbers one of which divides the other, and hence $X$ does too.
answered Jul 22, 2010 at 10:37
-
$\begingroup$ Wasn't Erdos' problem to prove that two of them are relatively prime? That one has an instant solution; this appears not to. $\endgroup$ Commented Jul 22, 2010 at 13:54
-
4$\begingroup$ This one has an instant solution too. Two of the numbers must have the same odd part. QED. $\endgroup$ Commented Jul 22, 2010 at 15:06
-
1$\begingroup$ Is there a list (somewhere) of Erdos-type questions for the "epsilons"? $\endgroup$ Commented Jul 22, 2010 at 15:51