1.有n個金幣,其中有1個是假的,請問最少用天平秤幾次可以秤出假的金幣?(已知假幣比真幣重)
這種問題比較單純,要證明也是可以的,只是不知道如下證明夠不夠嚴謹:
物品用天平稱重會符合三一律,即大於,等於,小於
因為已經假幣較真幣重,故先把物品均分三堆,
若無法均等,也要分成兩堆等量,而第三堆和其他兩堆差一的數量
先取兩堆等量的來稱重,則會有左重,平衡,右重等三種結果
若左重,則左堆有問題
若平衡,則未取堆有問題
若右重,則右堆有問題
為了以最少次找出,必須避開矛盾現象,直接由有問題的那堆下手
重覆上述動作:均分三堆,取兩堆稱重,判別有問題堆
一直到找出有問題堆為唯一一個為止
而每稱一次會有三種結果(即左重,平衡,右重)
若重覆了T次(即稱了T次),則共有3^T個結果,即最多可判別3^T個硬幣
故若3^(T-1)<N≦3^T,則最少需稱T次才能找出假幣