promotion image of download ymail app
Promoted
匿名
匿名 發問於 科學及數學數學 · 3 年前

Use Pigeonhole Principle to show that among any 4 numbers, one can find 2 numbers so that their difference is divisible by 3.?

1 個解答

評分
  • Lopez
    Lv 5
    3 年前
    最愛解答

    ..... 4 numbers .....

    should be restricted to

    ..... 4 natural numbers .....

    Pigeonhole Principle

    n objects are distributed among m sets,

    then at least one of the sets will contain at least ⌊(n - 1)/m⌋ + 1 objects,

    where ⌊...⌋ is the floor function.

    Natural numbers can be divide into 3 sets :

    A0 = { 3k|k = 0 , 1 , 2 , 3 , ..... } = ( 0 , 3 , 6 , 9 , ..... }

    A1 = { 3k + 1|k = 0 , 1 , 2 , 3 , ..... } = ( 1 , 4 , 7 , 10 , ..... }

    A2 = { 3k + 2|k = 0 , 1 , 2 , 3 , ..... } = ( 2 , 5 , 8 , 11 , ..... }

    For this question, n = 4 , m = 3 ,

    by the Pigeonhole Principle , we have :

    at least one of the sets will contain at least ⌊(n - 1)/m⌋ + 1 numbers .

    ⌊(n - 1)/m⌋ + 1

    = ⌊(4 - 1)/3⌋ + 1

    = ⌊1⌋ + 1

    = 1 + 1

    = 2

    Hence, at least one of the sets will contain at least 2 numbers.

    Namely, there exists 2 numbers in Ai = { 3k + i }, for some i in { 0 , 1 , 2 } .

    Suppose these 2 numbers are 3s + i , 3t + i , where s , t are natural numbers.

    their difference = ( 3s + i ) - ( 3t + i ) = 3( s - t ) , which is divisible by 3 .

    Q.E.D.

    • Commenter avatar登入以回覆解答
還有問題嗎?立即提問即可得到解答。