Re: [理工] [離散]-鴿籠原理

[doom8199 (～口卡口卡 修～)]

※ 引述《amidofun (amido)》之銘言：
: There are 20 students in a class, all born on different days of January, 1980.
: Show that there are two students born on the ith day and the jth day of January
: with│i-j│= 8.
: 我的想法是把一月分堆,如下:
: {01,09},{02,10},{03,11},{04,12},{05,13},{06,14},{07,15},{08,16}:1號~16號
: {17,25},{18,26},{19,27},{20,28},{21,29},{22,30},{23,31},{24}:17號~31號
: 共16組
: 根據鴿籠定理,20個學生必有4組絕對值的差等於8....
: 但題目只要求2個學生，即一組,那我這樣的證法有誤嗎?
: 這算暴力分堆法嗎= =?因為題庫班上的方法我比較不懂
: 還是我誤解題意了?

---

    假設這 20位學生的生日 為 1/a_1 、 1/a_2 、 ... 、 1/a_20

    且   1 ≦ a_1 ＜ a_2 ＜ ... ＜ a_20 ≦ 31  ____(1)   不失一般性


    令   b_i = a_i + 8   for   1≦i≦20

    所以  9 ≦ b_1 ＜ b_2 ＜ ... ＜ b_20 ≦ 39   ____(2)



    由  (1)(2) 式可知

    a_1 ~ a_20 、 b_1 ~ b_20

    這 40 個整數，  都介於  1~39 這 39 個整數之間

    所以必然存在 兩整數  a_i = b_j  (注意 a_i ≠ a_j  for all  1≦i,j≦20)

    即  a_i = a_j + 8


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.113.141.151
推 amidofun:用b_i,我比較懂了   剩下就是暴力分堆法可行嗎?XD
→ doom8199:可是你這樣算只是 "一組case" , 並非證明到 "所有的case"
→ doom8199:而且其實我不太懂你這樣分組的用意是啥 OTZ
推 amidofun:一組??所有??我不太懂"你不太懂的地方"
→ doom8199:就是為何你要這樣分組 @@?
→ doom8199:且照你的分組方式，為何不用考慮 {09,17} {10,18} 這些
推 amidofun:恩  其實分組方式不只一套  重點在於把31天分完
→ amidofun:不過  我也不太確定這方法有沒有瑕疵
→ doom8199:若我沒理解錯誤的話，你這樣算似乎跟原題目想問不太一樣
→ amidofun:所以方法有點暴力   要觀察用過的號數
→ doom8199:題目是想證明 20個相異的數字, 只要介於 1~31
→ doom8199:不論是哪 20個數字，必然存在其中兩個數字, 使得差值 = 8
→ doom8199:可是你的算法是 找出差值=8 的所有可能
→ amidofun:我也怕我的邏輯錯誤   所以上來討教一下
→ amidofun:我並沒有找出所有可能喔   例如{16,24}就沒有
→ amidofun:假如所有可能  會超過19組  就不能得證了
→ doom8199:恩，所以我才不解你這樣算的用意 @@''
→ amidofun:也違反31天&相異生日學生的限制
推 amidofun:舉例來說  如果所有差值=8的組合列出 有些日子會重複出現
→ doom8199:喔喔，了解您想表達甚麼意思了 ~~
→ doom8199:可是要如何證明 "這是最佳解的 case" ?
→ doom8199:萬一存在 17組相異數字， 使得任兩個數字的差不會等於 8
推 amidofun:不過分堆法的確有些問題 因為數值不太match 雖然有包含
→ doom8199:這樣証明就出問題了
→ doom8199:若你能證明這種分堆法是最平均的, 這樣這個證明就 ok 了
推 amidofun:可能暴力把所以日期組合列出XD  不過其實組合也沒有很多
→ amidofun:我能證明  數值超過50   大多數人不會用分堆....
→ doom8199:沒記錯的話，分堆的問題很難。若今天是 3個 or 4個一堆
→ doom8199:且需滿足某些特性，討論起來會非常複雜 OTZ
推 amidofun:依照人類歸納的天性  感覺2個可以一般化  組數=差值*2
推 amidofun:特別的是 31天跟32天沒差就是了.....閃人了zzz
推 bluncha:分堆法可以證明"存在"，我覺得沒有錯
推 imnewlegend:這樣有bug  直接證就好
→ imnewlegend:挺直觀的