Box Principle

For the natural numbers from 1 to 100, 51 of them randomly picked, show that there exists two numbers, say A and B, from the 51 numbers such that A divides B.
Solution.
Consider the 50 odd numbers 1,3, 5, ..., 99. For each one, form a box containing
the number and all powers of 2 times the number. So the first box contains
1,2,4,8,16, ...and the next box contains3,6,12,24,48, ...and so on. Then amongthe
51 numbers chosen, the pigeonhole principle tells us that there are two that are
contained in the same box. They mustbe of the form 2mk and 2nk with the same
odd number k. So one will divide theother.


2007-04-01 19:15:23 補充：
最後個句應是They must be of the form (2^m)k and (2^n)k with the same odd number k. So one will divide the other.