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

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者LPH66 (ha(ruhi|yate)ism)時間17年前 (2007/06/01 10:13)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串13/15 (看更多)

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

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

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