我試著利用eieio做法中的想法來做一般化的情形吧 若n顆要秤k次才能找出偽幣且分出輕重 我們看第一次選的 這第一次秤的必然是兩邊一樣多個 (否則得到的輕重沒有意義) 設兩邊各r個 那麼 當這一次不等重時 可能範圍縮小到2r種 這一次等重時 可能範圍縮小到2n-4r種 而全部既然秤k次才能得到答案 2r和2n-4r都必須要≦3^(k-1) 為了要能平均分配 2r和2n-4r必須儘量接近 最好的情形是2r=2n-4r 這時r=n/3 也就是當n被3整除時可以得r=n/3 這時由2r≦3^(k-1) => 2n/3≦3^(k-1) => 2n≦3^k => n≦(3^k)/2 當n不被3整除時 分兩種case: (1) n除以3餘1：令m=(n-1)/3 此時n個硬幣分成m m m+1三堆 稱前兩堆 那麼情形數就是2m 2m 2m+2 所以必須要有2m+2≦3^(k-1) => 2(n-1)/3+2≦3^(k-1) => 2(n-1)/3≦3^(k-1)-2 => 2(n-1)≦3^k - 6 => n-1≦(3^k)/2 - 3 => n≦(3^k)/2 - 2 (2) n除以3餘2: 令m=(n-2)/3 這情形中分成m m+1 m+1三堆 稱後兩堆 和(1)一樣的情形 可以求得 n≦(3^k)/2 - 1 於是稱k次要解得出來的個數就是上面三個情形的綜合 進一步考慮 因為3^k總是奇數 所以其實上面的(3^k)/2可以換成(3^k - 1)/2 求得的n不變 而(3^k - 1)/2除以3總是餘1 所以 上面的三個情形中符合條件的數就是換過後的右式再減1 也就是 / n≦(3^k - 1)/2 - 1, 當n除以3餘0 | n≦(3^k - 1)/2 - 2, 當n除以3餘2 \ n≦(3^k - 1)/2 - 3, 當n除以3餘1 三個情形的聯集即為所有的情形 因此 秤k次要秤得出來的個數n最多是 (3^k - 1)/2 - 1 = (3^k - 3)/2 對小的k檢查一下: k=1 => n≦(3-3)/2 = 0 //這很合理 因為要能玩最少要3個硬幣 //而3個硬幣就必須要秤兩次 k=2 => n≦(9-3)/2 = 3 //eieio舉的例子 k=3 => n≦(27-3)/2 = 12 //所以原題13個就不行了 對更大k列表如下: k=4 => n≦39 k=5 => n≦120 k=6 => n≦363 k=7 => n≦1092 ... --- 如果只是要找出誰是偽幣 那可以分出的硬幣個數可以+1 主要是多了n除以3餘1中的1個情形 拿13個3次的情形來說明好了: 當ABCD=EFGH時 剩下的IJKLM中有一個是偽幣 雖然情形看起來有10種 比3^2=9多 但其實我們可以不必分出到底m是輕是重 於是情形就剩9種 (即: I偽輕 I偽重 J偽輕 J偽重 K偽輕 K偽重 L偽輕 L偽重 M偽) 這樣剩下的就可以秤二次分出來了 更多次的情形是類似的 --- 以上完全沒有考慮到往後分堆的策略問題 所以其實很不嚴謹 也許分到後面會有不可意料的事情發生也說不定 @@" 不過可以確定的是 這裡求出的這個值是個上界 更多絕對分不出來這樣 -- 'Oh, Harry, dont't you see?' Hermione breathed. 'If she could have done one thing to make absolutely sure that every single person in this school will read your interview, it was banning it!' ---'Harry Potter and the order of the phoenix', P513 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 210.70.172.164