Puzzleup 2021 成績出爐 - 拼圖

第9題的難點就在構造, 目標是8次
以下是我的方法,
但因為真的太複雜,
我也不確定有沒有地方邏輯錯誤,
如果有錯, 還請版友指證, 謝謝

將60個硬幣分成5組,
A1組：9個,
A2組：9個,
B1組：9個,
B2組：9個,
C組：24個
附注, A組 = A1+A2, B組 = B1+B2

第一步：秤A1+A2 vs B1+B2
如果平衡, 表示以下2種情形之一
1個假的在A 且 1個假的在B
2個假的都在C
去第二步
如果不平衡, 表示以下2種情形之一
2個假的都在A或都在B
1個假的在A或B,1個假的在C
去第三步

第二步：秤A1 vs A2
如果平衡, 表示: A,B是真, 2個假的都在C
知36個真幣, 要在C組(24個)硬幣中找2個假的, 且不知假的是輕是重
=>見情況一, 要秤6次
總共 1+1+6 (第一步+第二步+情況一) = 8次
如果不平衡, 表示: C是真, 1個假的在A 且 1個假的在B
知24個真幣, 要在B組(18個)硬幣中找1個假的, 且不知假的是輕是重
=>見情況二, 要秤4次
找到B組的假幣後, (知其是輕是重),
搭配第二步的結果, 可知另一個假的在A1還是A2, 命名為F
要在F組(9個)硬幣中找1個假的, 且已知假的是輕是重
=>見情況三, 要秤2次
總共 1+1+4+2 (第一步+第二步+情況二+情況三) = 8次

第三步：秤A1+B1 vs A2+B2
如果平衡, 表示: C是真, 1個假的在A1+B1 且 1個假的在A2+B2
知24個真幣, 要在A2+B2(18個)硬幣找1個假的, 且不知假的是輕是重
=>見情況二, 要秤4次
找到A2+B2的假幣後, (知其是輕是重),
搭配第一步的結果, 可知另一個假的在A1還是B1, 命名為F
要在F組(9個)硬幣找1個假的, 且已知假的是輕是重
=>見情況三, 要秤2次
總共 1+1+4+2 (第一步+第三步+情況二+情況三) = 8次
如果不平衡, 考慮以下2種情形
如果第一步,第三步天平傾向同邊,
表示假的在A1或B2 (數量未知), C可能有1個假的, B1,A2 是真的
將A1,B2中重的命名為FH, 輕的命名為FL, B1,A2命名為T1,T2,
並將C組分成2組, 各12個, 命名為C1, C2
如果第一步,第三步天平傾向不同邊,
表示假的在B1或A2 (數量未知), C可能有1個假的, A1,B2 是真的
將B1,A2中重的命名為FH, 輕的命名為FL, A1,B2命名為T1,T2,
並將C組分成2組,各12個, 命名為C1, C2
去第四步

第四步：秤C1 vs C2
如果平衡, 表示: C是真, 2個假的都在FH 或 2個假的都在FL
將FH分成2組, 3個硬幣, 6個硬幣, 命名FH3, FH6
將FL分成2組, 3個硬幣, 6個硬幣, 命名FL3, FL6
去第五步
如果不平衡, 表示: 1個假的在C1或C2, 另1個假的在FH或FL
將C1,C2中重的分成2組, 9個硬幣, 3個硬幣, 命名CH9, CH3
將C1,C2中輕的分成2組, 9個硬幣, 3個硬幣, 命名CL9, CL3
(注意, 假的只可能同在FH,CH 或 同在FL,CL內)
去第八步

第五步：秤FH3+FL3 vs 任6個真幣(從T1或T2拿)
如果平衡, 表示: 2個假的都在FH6 或 2個假的都在FL6
去第六步
如果不平衡, 由結果可知假的是重是輕
若是重的, 則FH3至少1個假幣, FH6可能有1個假的
改命名FH3為F3, FH6為F6
若是輕的, 則FL3至少1個假幣, FL6可能有1個假的
改命名FL3為F3, FL6為F6
去第七步

第六步：秤FH6 vs 任6個真幣(從T1或T2拿)
如果平衡, 表示: 2個假的都在FL6
要在FL6(6個)硬幣找2個假的, 且已知假的是輕是重
=>見情況四, 要秤3次
總共 1+1+1+1+1+3 (第一,三,四,五,六步+情況四) = 8次
如果不平衡, 表示: 2個假的都在FH6
要在FH6(6個)硬幣找2個假的, 且已知假的是輕是重
=>見情況四, 要秤3次
總共 1+1+1+1+1+3 (第一,三,四,五,六步+情況四) = 8次

第七步：F6 分成3, 3秤 (F6x vs F6y)
(注意, 由第五步來時已知假的是輕是重)
如果平衡, 表示: 2個假的都在F3
要在F3(3個)硬幣找2個假的, 且已知假的是輕是重
=>見情況五, 要秤1次
總共 1+1+1+1+1+1 (第一,三,四,五,七步+情況五) = 6次
如果不平衡, 表示: 1個假的在F3, 1個假的在F6
再由天平偏向可知是 F6x 還是 F6y 有假幣
要在F3(3個)硬幣找1個假的, 且已知假的是輕是重
=>見情況六, 要秤1次
要在F6x或F6y(3個)硬幣找1個假的, 且已知假的是輕是重
=>見情況六, 要秤1次
總共 1+1+1+1+1+1*2 (第一,三,四,五,七步+情況六*2) = 7次

第八步：秤CH9+CL9 vs T1+T2
如果平衡, 表示: 1個假的在CH3或CL3, 另1個假的在FH或FL
去第九步
如果不平衡, 由結果可知假的是重是輕
若是重的, 1個假的在CH9, 1個假的在FH
若是輕的, 1個假的在CL9, 1個假的在FL
無論那種情形, 都是以下執行2次：
要在9個硬幣中找1個假的, 已知假的是輕是重
=>見情況三, 要秤2次
總共 1+1+1+1+2*2 (第一,三,四,八步+情況三*2) = 8次

第九步：秤CH3 vs 任3個真幣(從T1或T2拿)
如果平衡, 表示: 1個假的在CL3, 另1個假的在FL
如果不平衡, 表示: 1個假的在CH3, 另1個假的在FH
無論那種情形, 都是執行以下兩件事
要在3個硬幣(CL3或CH3)中找1個假的, 已知假的是輕是重
=>見情況六, 要秤1次
要在9個硬幣(FL或FH)中找1個假的, 已知假的是輕是重
=>見情況三, 要秤2次
總共 1+1+1+1+1+1+2 (第一,三,四,八,九步+情況六+情況三) = 8次



情況一，知36個真幣, 要在24個硬幣中找2個假的, 且不知假的是輕是重
此情況篇幅有點長, 在此先省略, 版友可以試著構造
如果版友有需要, 我再找時間寫上來

情況二，知24個真幣, 要在18個硬幣中找1個假的, 且不知假的是輕是重
從18個硬幣分成9,9兩組 分別和9個真幣秤
必有一組平衡,一組不平衡
從不平衡的那組可知假的是輕是重
接著要在9個硬幣找1個假的, 且已知假的是輕是重
=>見情況三, 要秤2次
共需秤4次

情況三，要在9個硬幣中找1個假的, 已知假的是輕是重
選任6個硬幣, 3,3 放天平左右秤
如果平衡, 則沒上秤的3個有1個假幣
如果不平衡, 由已知的條件知道此時重端(或輕端)的3個硬幣中有1個假的
依情況六再秤一次, 便可知假幣
共需秤2次

情況四，要在6個硬幣中找2個假的, 已知假的是輕是重
6個硬幣, 3,3 放天平左右秤
如果平衡, 則兩端各有一個假的
再依情況六, 分別找出兩端的假幣
共需秤3次
如果不平衡, 由已知的條件知道此時重端(或輕端)的3個硬幣中有2個假的
再依情況五, 找出該端的2個假幣
共需秤2次
總結共需秤3次

情況五，要在3個硬幣中找2個假的, 已知假的是輕是重
選任2個硬幣放天平左右秤
如果平衡, 則秤上的2個都是假的
如果不平衡, 由已知的條件知道此時重的(或輕的)是假幣, 沒上秤的也是假的
共需秤1次

情況六，要在3個硬幣中找1個假的, 已知假的是輕是重
選任2個硬幣放天平左右秤
如果平衡, 則沒上秤的是假的
如果不平衡, 由已知的條件知道此時重的(或輕的)是假幣
共需秤1次

--