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