教授跳樓 - 拼圖

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

--