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

2016-11-23 12:50 am

回答 (1)

2016-11-24 10:21 am
✔ 最佳答案
..... 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.


收錄日期: 2021-05-02 14:12:33
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20161122165048AAFLXqL

檢視 Wayback Machine 備份