simon 發問於 科學及數學數學 · 7 年前

# Pigeonhole principle

1a. Use Pigeonhole Principle to show that among any 4 numbers, say x1, x2, x3

and x4, one can find 2 numbers so that their difference is divisble by 3.

b. Show that in ant group of five people, there are two have the same number of

friends within the group.

(Note: If X is a friend of Y, then Y is a friend of X)

### 2 個解答

• 7 年前
最愛解答

我已解答：

http://hk.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.

係典型鴿籠題～

也介紹你去睇下：

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

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

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

2013-10-31 17:08:17 補充：

Hahaha~

I have my schedule~

今日只被檢舉三篇～

真係畀面～

• 7 年前

still free at 0920??? dont need to go to work?!

2013-11-01 00:29:04 補充：

hey come on,yoy wont be thinking that its ke reporting U ,right? What means by真係畀面～???

2013-11-01 00:32:11 補充：

no problem,I will sort it out!

2013-11-01 00:32:27 補充：

see email.pls

2013-11-01 00:32:58 補充：

pls see email