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

如果要確定偽幣輕重,的確三次是不夠的
所以就要看題目如何定
之前在奇摩知識又找到另一個方法
找出偽幣.但不一定知道輕重

也是分成445
第一次同重>>同我的做法
第一次不同重
比較B1RR VS A1B2B3
這種方法似乎更簡單一些




現在應該是可以確定幾顆硬幣至少需要幾次才能找出偽幣弊並卻定輕或重
但是有沒有公式可以解
當n顆的時候該怎麼安排才能最快找出偽幣並分辨其輕重呢?


※ 引述《eieio (好多目標)》之銘言：
: ※ 引述《m06 (桂冠湯圓)》之銘言：
: : 推文提到
: : 推 rehearttw:有教授證明過了，依原題目，確實要四次。有計算公式 05/27 07:52
: : 很好奇證明是怎麼證的..
: : 前面有12個金幣的分別法
: : 感覺13個應該也可行耶..
: : 不知道有沒有教授的證明可以參考＠＠?
: 我好像看過那個證明，但有點抽象，用我的方法講講看。
: 首先要澄清題目。我現在要證的題目的要求，除了必須找出假硬幣，還必須知
: 道這個假硬幣是輕或重。像最近又討論起來的題目是只要找到假硬幣即可，在13
: 個金幣時正好會有差。
: 先考慮三個金幣的情況，先行編號後，只有六種可能：
: 1輕 1重 2輕 2重 3輕 3重
: 假設我們把 1 2 拿去秤，有三種結果，那它們對應到的可能就變成：
: A. 1 > 2 1重 or 2輕
: B. 1 < 2 1輕 or 2重
: C. 1 = 2 3輕 or 3重
: 注意到秤一次之後，原來的六種可能被劃分成三組二種可能，下一步就可以找
: 出假硬幣「並且」知道它是輕或重。例如剛剛得到 1<2 就拿 1 3 去秤：
: B a. 1 = 3 2重
: B b. 1 < 3 1輕
: 如果是四個金幣，有八種可能：1輕 1重 2輕 2重 3輕 3重 4輕 4重
: 同樣把 1 2 拿去秤，但這時對應到的就變成：
: A. 1 > 2 1重 or 2輕
: B. 1 < 2 1輕 or 2重
: C. 1 = 2 3輕 or 3重 or 4輕 or 4重
: 在 case C 裡面，有四種可能。但你不管如何安排下一次比較，都只有 > = <
: 三種結果，是不夠區分出四種可能的。至少會有兩種可能給你相同的結果。最好
: 的安排是拿 1 3 去秤，變成
: C a. 1 > 3 3輕
: C b. 1 < 3 3重
: C c. 1 = 3 4輕 或 4重 <= 這裡就失敗了
: 因此在只秤兩次的情況下，最多只能有三個金幣。
: 在只剩最後一次秤的機會的時候，最多只能有 3 個情況，不然一定會有一種
: 結果讓你失敗。同樣的道理，只剩最後兩次秤的機會時，最多只能有 9 個情況
: ，不然分下去後會有一堆有 4 個以上，而那堆就可能會失敗。
: 在 12 個金幣的問題裡，拿 1234 和 5678 去秤，會得到
: A. 1234 > 5678 1重 2重 3重 4重 5輕 6輕 7輕 8輕
: B. 1234 < 5678 1輕 2輕 3輕 4輕 5重 6重 7重 8重
: C. 1234 = 5678 9輕 9重 10輕 10重 11輕 11重 12輕 12重
: 剛剛好每組有 8 個可能，不超過 9 個。
: 若有 13 個金幣，那有 26 種可能，看似可以分成 9 9 8，但其實沒辦法，最
: 好的秤法仍然是拿 1234 和 5678 去秤：
: A. 1234 > 5678 1重 2重 3重 4重 5輕 6輕 7輕 8輕
: B. 1234 < 5678 1輕 2輕 3輕 4輕 5重 6重 7重 8重
: C. 1234 = 5678 9輕 9重 10輕 10重 11輕 11重 12輕 12重 13輕 13重
: 這樣 case C 裡面有 10 種可能，是沒辦法在秤兩次內找出是哪個情況的。所
: 以說，若要同時找出假硬幣「並且」知道是太輕或太重的話，13 個金幣需要秤
: 四次。

--