九枚中找偏重幣:兩次稱量的完整策略

邏輯思維 · 建議年級 6

用三結果決策樹葉子數和完整分組策略判斷兩次稱量能保證區分的候選上限。

下載影片
展開影片文字稿
  1. 九枚硬币中八枚正常同重,一枚偏重。天平每次有左重、平衡、右重三种结果。
  2. 两次称量最多形成三乘三,也就是九个独立结果叶子,所以十枚候选不可能保证区分。
  3. 九枚先分成三、三、三。第一次称两组:左重、右重或平衡,都会把范围锁定到一组三枚。
  4. 第二次在锁定的三枚里称一枚对一枚;左重、右重、平衡分别定位三枚中的一枚。
  5. 这样两层各有三个分支,九条路径正好覆盖九枚硬币,所以九枚能够保证找出。
  6. 现在模拟第一次称量平衡:请指出偏重币在哪一组三枚,并安排第二次一对一称量。小宝贝到你了。
講解依據

邏輯思維

葉子上界與全分支構造,並用反向檢查確認。

看一個例子

9枚中8枚正常同重、1枚偏重。稱2次能否保證找出?若有10枚能否保證?

9枚能;先分3、3、3,再在鎖定的3枚中稱1對1。10枚不能保證。兩層各3分支完整覆蓋9條路徑;偏重方向已知。

立即試一題

兩次三結果稱量最多有幾個葉子?