# Thread: Pigeon-hole Principle (2)

1. ## Pigeon-hole Principle (2)

(a) Let n >= 2. We select n + 1 different integers from the set {1, 2, ..., 2n}. Is it true that there will always be two among the selected integers so that one of them is equal to twice the other?
(b) Is it true that there will always be two among the selected integers so that one is a multiple of the other?

My attempt:
(a) is false. A counterexample for n = 5: {1, 3, 4, 5, 7, 9}.
I think (b) is true but cannot seem to prove it. Any ideas?

2. ## Re: Pigeon-hole Principle (2)

This says "solved", but I don't see a solution here... I was interested to see if this was correct:

Let's let $A=\{1,2,\ldots ,n\},B=\{n+1,n+2,\ldots ,2n\}$. Suppose we wanted to attempt to pick $n+1$ elements such that no one is a multiple of another. Since $|B|=n$, at least one choice must come from $A$. Let's pick $x_1\in A$. This eliminates at least one possible choice from $B$; namely, $2x_1$. Now there are only $n-1$ possible choices left in $B$ (at most) and $n$ choices left to make. It follows that we need to choose another $x_2\in A$, which eliminates at least one more choice from $B$. Iterating this process, we see that we need to pick every element from $A$ and can't pick anything from $B$, which is of course bad, since we have only chosen $n$ elements. Of course, we could probably come to a contradiction a bunch of different ways before exhausting all of $A$, but this seems to work.

I think this is right. If someone could make sure, that would be great; and if there are better solutions, I'd be interested in seeing those too.

3. ## Re: Pigeon-hole Principle (2)

Originally Posted by topspin1617
Let's pick $x_1\in A$. This eliminates at least one possible choice from $B$; namely, $2x_1$.
What if $2x_1 \in A$?

4. ## Re: Pigeon-hole Principle (2)

a) is not true:

If n=5, 2n=10; {1,2,3,4,5,6,7,8,9,10}

Now we will pick 6 elements from the above group:

{1,3,4,5,7,9}

I didn't see your solution for a...

An idea for part b)

I will give the idea via example when n=10.

n=10 the 2n=20

X={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19 ,20}

I will divide set X to some subsets:

A_1={1,2,4,8,16}

A_2={3,6,9,18}

A_4={5,10,20}

A_5={7,14}

A_6={11}

A_7={13}

A_8={17}

A_9={19}

If we take 11 elements there must be at least two of the that are in the same set!

5. ## Re: Pigeon-hole Principle (2)

Originally Posted by Also sprach Zarathustra
An idea for part b)

I will give the idea via example when n=10.

n=10 the 2n=20

X={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19 ,20}

I will divide set X to some subsets:

A_1={1,2,4,8,16}

A_2={3,6,9,18}

A_4={5,10,20}

A_5={7,14}

A_6={11}

A_7={13}

A_8={17}

A_9={19}

If we take 11 elements there must be at least two of the that are in the same set!
6 and 9 are in the same subset but one is not a multiple of the other. Where are 12 and 15?

6. ## Re: Pigeon-hole Principle (2)

Originally Posted by alexmahone
What if $2x_1 \in A$?
Ugh. Of course.

Have to think some more.

7. ## Re: Pigeon-hole Principle (2)

Maybe the other guy was on to something up there. For $1\leq r\leq n$, let $A_r=\{2^k\cdot (2r-1)\mid k\geq 0, 2^k\cdot (2r-1)\leq 2n\}$. Certainly every element of $\{1,2,\ldots ,2n\}$ is in at least one of the $A_r$. (Of course all of the odd numbers are; for the even numbers, factor out the highest power of 2 possible, and see that it is in the set corresponding to the remaining odd factor.) Note that there are exactly $n$ of these sets $A_r$. Also, notice that for any fixed $r$, every element of $A_r$ has a divisibility relation with every other element of that same set. This means that, if we were picking elements which share no such relation, the best we could do is pick one element from each set. Since there are only $n$ sets, the best we could possibly do is pick $n$ elements.

8. ## Re: Pigeon-hole Principle (2)

Originally Posted by topspin1617
Maybe the other guy was on to something up there. For $1\leq r\leq n$, let $A_r=\{2^k\cdot (2r-1)\mid k\geq 0, 2^k\cdot (2r-1)\leq 2n\}$. Certainly every element of $\{1,2,\ldots ,2n\}$ is in at least one of the $A_r$. (Of course all of the odd numbers are; for the even numbers, factor out the highest power of 2 possible, and see that it is in the set corresponding to the remaining odd factor.) Note that there are exactly $n$ of these sets $A_r$. Also, notice that for any fixed $r$, every element of $A_r$ has a divisibility relation with every other element of that same set. This means that, if we were picking elements which share no such relation, the best we could do is pick one element from each set. Since there are only $n$ sets, the best we could possibly do is pick $n$ elements.
Yeah, that's right. Good job!

### select n 1 different integers from the set {1,2,..,2n} . prove that there

Click on a term to search for related topics.