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

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者rehearttw (易懷)時間17年前 (2007/06/01 10:11)推噓0(0推 0噓 0→)

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

※ 引述《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 個金幣需要秤 : 四次。推這個想法！我當初在想公式解的時候，曾經利用到三進位就是不論如何安排，每次的結果都會有 > = < 三種三次就會有 3^3 = 27 種但是不可能有三次為 ( > > > )、( = = = )、( < < < ) 三種（尚待證明）所以只有 24 種結果而 12 枚硬幣的結果，有 1 重、1 輕、2 重、2 輕、...、12 輕等 24 種剛好可以設計 1 對 1 公式表但若是 13 枚硬幣，則會有 26 種答案，三次是不足的下面附錄當初我的 12 枚公式解： ---------------------------------- 公式解：將金幣編號成 1 2 3 4 5 6 7 8 9 10 11 12 依照下面三次分法秤： (1) 1 3 5 7 對 2 4 6 8 (2) 1 6 8 11 對 2 7 9 10 (3) 2 3 8 12 對 5 6 9 11 三次結果分別依 < = > 紀錄，對照下面公式表 <<< 不可能 <<= 1輕 <<> 2重 <=< 3輕 <== 4重 <=> 5輕 <>< 6重 <>= 7輕 <>> 8重 =<< 9重 =<= 10重 =<> 11輕 ==< 12輕 === 不可能 ==> 12重 =>< 11重 =>= 10輕 =>> 9輕 ><< 8輕 ><= 7重 ><> 6輕 >=< 5重 >== 4輕 >=> 3重 >>< 2輕 >>= 1重 >>> 不可能這是根據三進位對照及作部分調正而來。 -- rehearttw 許老師（Reheart-易懷），愛生公式，愛胡思亂想自 1980 年摸魔術方塊，1981 年學基本公式，2006 年學 CFOP 個人魔術方塊網頁 http://rubiks.tw/~reheart/Rubiks-cube.htm 縮網址：http://rubiks.tw/Yhec （95/4/7更新、95/6/28改版、95/12/12換址）益智玩具：http://rubiks.tw/~reheart/puzzle.htm 縮網址 http://rubiks.tw/EjKQ 請多多指教！ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 203.71.236.141

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

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