推 weijr:一半是用建構一個例子沒錯 10/21 10:47
→ weijr:但你這一半不完整。13次不可能，只是因為 C(13,2)+13+1<100 10/21 10:48
※ 引述《ping1902 (我已經老了)》之銘言：
: 應該是說 教授跳樓會死的樓數 在2~100中 (我不知道樓層頂算不算 算的話一樓也要考慮)
: 要想出一個方法 頂多只死兩個教授就知道哪個樓層是最小致死樓層
: 而且還要證明你這方法中用的跳樓次數的可能最多次數
: 是所有能找出最小致死樓層的方法中的最多次數裡面最少的
: 最後 你這方法中所用的可能最多次數 就是答案啦
以下的「答案」一詞指的是「最小致死樓層」
由ACGfans版友的想法來想
我們可以知道 第二個教授一定得要一層一層往上試
那麼如果第一個教授試的層數是 1<x1<x2<x3<...<x_n=100
那麼(部份答案的)總次數是 (令x0=1)
答案 2=x0+1 x1+1 x2+1 x3+1 ... x_(n-1) x_n=100
次數 2 3 4 5 n+1 ----
x0~x_(n-1)都是第一個教授試到它的下一個樓層而摔死 第二個教授往上試一層也掛了
所以(x_k)+1需要k+2次
在x_k之間的樓層所需次數則是 (若x_(k+1)>ans>x_k) ans-x_k+(k+1)
(第二個教授一層一層跳 跳到死為止)
但是答案是x_k的次數卻可以少一次 因為少跳一次x_k層
由他在(x_k)-1層的生還而確定答案是x_k
因此我們只要找到對所有k=0..n-1,
使(x_(k+1))-1-x_k+(k+1)=(x_(k+1))-x_k+k的最大值最小
由1+2+...+13=91<100 知 k>13 (還不夠k增加)
若k=14, 則所有k個(x_(k+1))-x_k+k的總合=x_n-x_0+(1+2+...+13)
=100-1+(91)=190
190/14=13.5xx => 個別的最大總合取14最小
而總合14平均分攤的情形是: (不平均分攤的話只會剩更多總合下來)
x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14
1 15 28 40 51 61 70 78 85 91 96 100 --- --- ---
總合13的情形, 易知排不滿100層:
x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14
1 14 26 37 47 56 64 71 77 82 86 89 91 92 ...
若k=15, 所有總合=100-1+105=205, 205/15=13.6xx => 個別的最大總合也≧14 不能更好
k=更大的數(K)時, 所有總合=99+(K(K-1))/2,
平均=99/K+(K-1)/2≧2√(99/2)-1/2=13.57xx
=> 個別的最大總合還是≧14 一樣不能更好
而我們已經有了一個最大總合14的例子了 故知答案為14次
--
上面這組答案(15,28,40,51,61,70,78,85,91,96,100)
和ACGfans版友求得的(14,27,39,50,60,69,77,84,90,95,99)只差一層樓
這是由於我的答案範圍是由2開始
(也就是如果答案在低樓層 若15樓就摔死教授1則教授2是由2樓起跳)
如果由1開始的話就會得到ACGfans的答案
不過一樣都是14次
--
有錯或不完整的請指教 謝謝
--
"LPH" is for "Let Program Heal us"....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 192.192.197.112