Thread: 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?

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

Let's let . Suppose we wanted to attempt to pick elements such that no one is a multiple of another. Since , at least one choice must come from . Let's pick . This eliminates at least one possible choice from ; namely, . Now there are only possible choices left in (at most) and choices left to make. It follows that we need to choose another , which eliminates at least one more choice from . Iterating this process, we see that we need to pick every element from and can't pick anything from , which is of course bad, since we have only chosen elements. Of course, we could probably come to a contradiction a bunch of different ways before exhausting all of , 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.

Originally Posted by topspin1617

Let's pick . This eliminates at least one possible choice from ; namely, .

What if ?

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!

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?

Originally Posted by alexmahone

What if ?

Ugh. Of course.

Have to think some more.

Maybe the other guy was on to something up there. For , let . Certainly every element of is in at least one of the . (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 of these sets . Also, notice that for any fixed , every element of 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 sets, the best we could possibly do is pick elements.

Originally Posted by topspin1617

Maybe the other guy was on to something up there. For , let . Certainly every element of is in at least one of the . (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 of these sets . Also, notice that for any fixed , every element of 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 sets, the best we could possibly do is pick elements.

Yeah, that's right. Good job!