# 解答2條數學問題 Pigeonhole principle

1)show that among any 4 numbers , say x1 x2 x3 x4 , one can find 2 numbers so

that their difference is divisible by 3

2)show that in any group of five people , there are two who have the same number of friends within the group.

### 1 個解答

• 7 年前
最愛解答

好！　又係典型鴿籠題～

解答之前介紹你去睇下：

http://tw.knowledge.yahoo.com/question/question?qi...

http://tw.knowledge.yahoo.com/question/question?qi...

http://tw.knowledge.yahoo.com/question/question?qi...

Solution 1

(You should mention the 4 numbers are integers.)

When a positive integer is divided by 3, the remainder can either be 0, or 1, or 2 only.

Suppose when x1, x2, x3, x4 is respectively divided by 3, the corresponding remainders are r1, r2, r3, r4.

Then, because r1, r2, r3, r4 in {0, 1, 2}, by pigeonhole principle, there must exists ri and rj which are the same, where i and j are distinct.

Suppose xi = 3Qi + ri and xj = 3Qj + rj, where Qi and Qj are integers.

Then, xi - xj = 3(Qi - Qj) is divisible by 3.

Solution 2

In a group of five people, one can have no friend, or one friend, or two friends, or three friends, or four friends (be friends with everyone in the group). It looks like there are five pigeon holes (possible numbers of friends) but actually, if someone in a group has four friends, there cannot be anyone with no friends in that group. So there are only four pigeon holes: either zero through three friends, or one through four friends. Pigeons are five people of the group.

In my words, there are 5 people in total.

Case 1:

If there is a person who has no friend within this group.

Then the number of friends of the people in this group can either be 0, 1, 2, 3 (it cannot be 4, otherwise that person mentioned earlier would have a friend).

Five persons with 4 possible numbers of friends, then by pigeonhole principle, there must exists the same number of friends.

Case 2:

If there is no person who has no friend within the group.

Then the number of friends of the people in this group can either be 1, 2, 3, 4.

Five persons with 4 possible numbers of friends, then by pigeonhole principle, there must exists the same number of friends.