Re: 十三枚硬幣 其中一枚不一樣重 - 拼圖

我試著利用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

--