Help: "Dirichlet pigeonhole principle" discrete math problem

Question

I need to prove that According to "Dirichlet pigeonhole principle" if the numbers 1-64 are given and we choose 33 of those, prove that there is at least one couple of numbers so that one number is the divider of the other.

 

Thank you

 

Tom

Answer 1

Here's the general idea:

 

Choose 33 numbers. Assume for the sake of contradiction that no chosen number is the divisor of another. Now, let x be the smallest number chosen. Since we're choosing 33 numbers, we're leaving out 31 numbers. Therefore, the largest possible value for x is 32. But if x = 32, then 64 must not be in the set since 64/32 = 2. So, the largest possible value for x is 31. But if x = 31, then 62 must not be in the set. So, the largest possible value for x is 30. But if x = 30, then 60 must not be in the set. We may continue this way, eliminating every even number as we go. When x = 4, 8 must not be in the set. When x = 3, 6 must not be in the set. When x = 2, 4 must not be in the set. When x = 1, 2 must not be in the set. Therefore, no even number can be in the set. Only 32 numbers (the odd numbers) remain, but we chose 33 numbers. By one formulation of the pigeonhole principle, if n = 32 numbers are distributed over m = 33 places, and n < m, at least one place must contain no number. This is a contradiction. Therefore, at least one chosen number is the divisor of another.