[離散]有關幾題鴿籠原理的應用

[SUPERTR (日光月影)]

1.There are 100 people at a party. Each person has an even number (possibly
  zero) of acquaintances. Prove that there are three people at the party with
  the sasne number of acquaintances.


2.Prove that of any five points chosen within a square of side length 2, there
  are two whose distance apart is at most 2^0.5.

3.Prove that in a group of n>1 people there are two who have the same number
  of acquaiotances in the group. (It is assumed that no one is acquainted with
  him or herself.)

我想了很久，但還是沒想出解決的辦法

如果可以的話，能不能詳述一下作法

請大家多多幫忙

謝謝了

--


※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.122.148.59

推 hcsoso      :要不要說說你嘗試過的部分？
※ 編輯: SUPERTR         來自: 122.122.148.59       (03/24 21:08)
→ SUPERTR     :它第2題簡答是寫將其分成四個邊長1的正方形
→ SUPERTR     :但我依舊是解不出來= =
→ SUPERTR     :可以請給我一點提示嗎
→ a88241050   :分成4個正方形,至少有2個點在同一個正方形內
→ SUPERTR     :我知道了，謝謝a大了。
→ k6416337    :acquaintances是啥?
→ SUPERTR     :是熟人的意思，也就是認識的人
→ a88241050   :每個人認識的人數都是偶數個
→ k6416337    :那A認識B有代表B認識A嗎?
※ 編輯: SUPERTR         來自: 122.122.148.59       (03/24 21:41)
→ SUPERTR     :照題意，算是雙向的
→ SUPERTR     :我想可以看作是兩個點連成直線，各點有偶數線段連接