Thread: Combinatorics - show result?

If integers are chosen from integers , show that, among the chosen integers, there are two, such that one of them divides the other.

I cant remember exactly how to do this but what you have to note is that any integer can be written in the form where and a is odd. Note also that in this case a has n values since there is n odd and n even integers between 1 and 2n.

Now you have to use the pigeonhole principle. How exactly i cant remember. But im guessing since there n values of a and you choose n+1 integers you'll end up at the fact that one 'hole' has 2 'pigeons' in it.

Originally Posted by fardeen_gen

If integers are chosen from integers , show that, among the chosen integers, there are two, such that one of them divides the other.

You could probably use induction. Proof. Base case: For , we choose integers of . And . Inductive step: Suppose that integers are chosen from the integers where and there are two, such that one divides the other. Now append and . Then if we choose of the integers we know have to use the Pigeonhole principle. You could have a case where you choose the integers such that the integer in the inductive hypothesis are contained. Or could have both numbers not contained. Finally you could have one contained and the other not.