※ 引述《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