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

看板Grad-ProbAsk作者 (～口卡口卡　修～)時間16年前 (2010/01/09 02:34), 編輯推噓10(10推 0噓 24→)
留言34則, 4人參與, 最新討論串2/4 (看更多)
※ 引述《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
推
01/09 02:40, , 1F
用b_i,我比較懂了 剩下就是暴力分堆法可行嗎?XD
01/09 02:40, 1F
→
01/09 02:41, , 2F
可是你這樣算只是 "一組case" , 並非證明到 "所有的case"
01/09 02:41, 2F
→
01/09 02:43, , 3F
而且其實我不太懂你這樣分組的用意是啥 OTZ
01/09 02:43, 3F
推
01/09 02:47, , 4F
一組??所有??我不太懂"你不太懂的地方"
01/09 02:47, 4F
→
01/09 02:48, , 5F
就是為何你要這樣分組 @@?
01/09 02:48, 5F
→
01/09 02:49, , 6F
且照你的分組方式，為何不用考慮 {09,17} {10,18} 這些
01/09 02:49, 6F
推
01/09 02:51, , 7F
恩 其實分組方式不只一套 重點在於把31天分完
01/09 02:51, 7F
→
01/09 02:52, , 8F
不過 我也不太確定這方法有沒有瑕疵
01/09 02:52, 8F
→
01/09 02:53, , 9F
若我沒理解錯誤的話，你這樣算似乎跟原題目想問不太一樣
01/09 02:53, 9F
→
01/09 02:53, , 10F
所以方法有點暴力 要觀察用過的號數
01/09 02:53, 10F
→
01/09 02:54, , 11F
題目是想證明 20個相異的數字, 只要介於 1~31
01/09 02:54, 11F
→
01/09 02:55, , 12F
不論是哪 20個數字，必然存在其中兩個數字, 使得差值 = 8
01/09 02:55, 12F
→
01/09 02:55, , 13F
可是你的算法是 找出差值=8 的所有可能
01/09 02:55, 13F
→
01/09 02:55, , 14F
我也怕我的邏輯錯誤 所以上來討教一下
01/09 02:55, 14F
→
01/09 02:57, , 15F
我並沒有找出所有可能喔 例如{16,24}就沒有
01/09 02:57, 15F
→
01/09 02:59, , 16F
假如所有可能 會超過19組 就不能得證了
01/09 02:59, 16F
→
01/09 02:59, , 17F
恩，所以我才不解你這樣算的用意 @@''
01/09 02:59, 17F
→
01/09 03:01, , 18F
也違反31天&相異生日學生的限制
01/09 03:01, 18F
推
01/09 03:04, , 19F
舉例來說 如果所有差值=8的組合列出 有些日子會重複出現
01/09 03:04, 19F
→
01/09 03:09, , 20F
喔喔，了解您想表達甚麼意思了 ~~
01/09 03:09, 20F
→
01/09 03:10, , 21F
可是要如何證明 "這是最佳解的 case" ?
01/09 03:10, 21F
→
01/09 03:13, , 22F
萬一存在 17組相異數字， 使得任兩個數字的差不會等於 8
01/09 03:13, 22F
推
01/09 03:13, , 23F
不過分堆法的確有些問題 因為數值不太match 雖然有包含
01/09 03:13, 23F
→
01/09 03:14, , 24F
這樣証明就出問題了
01/09 03:14, 24F
→
01/09 03:15, , 25F
若你能證明這種分堆法是最平均的, 這樣這個證明就 ok 了
01/09 03:15, 25F
推
01/09 03:16, , 26F
可能暴力把所以日期組合列出XD 不過其實組合也沒有很多
01/09 03:16, 26F
→
01/09 03:18, , 27F
我能證明 數值超過50 大多數人不會用分堆....
01/09 03:18, 27F
→
01/09 03:20, , 28F
沒記錯的話，分堆的問題很難。若今天是 3個 or 4個一堆
01/09 03:20, 28F
→
01/09 03:21, , 29F
且需滿足某些特性，討論起來會非常複雜 OTZ
01/09 03:21, 29F
推
01/09 03:23, , 30F
依照人類歸納的天性 感覺2個可以一般化 組數=差值*2
01/09 03:23, 30F
推
01/09 03:28, , 31F
特別的是 31天跟32天沒差就是了.....閃人了zzz
01/09 03:28, 31F
推
01/09 09:41, , 32F
分堆法可以證明"存在"，我覺得沒有錯
01/09 09:41, 32F
推
01/20 04:32, , 33F
這樣有bug 直接證就好
01/20 04:32, 33F
→
01/20 04:33, , 34F
挺直觀的
01/20 04:33, 34F
‣ 更多 doom8199 的文章
文章代碼(AID): #1BHtgpmO (Grad-ProbAsk)
‣ 更多 doom8199 的文章
文章代碼(AID): #1BHtgpmO (Grad-ProbAsk)