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.

1 個解答

評分
  • 1 十年 前
    最佳解答

    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.

還有問題嗎?立即提問即可得到解答。