橋渡り問題
真夜中のことです。4人の人が吊り橋を渡ろうとしています。
その橋を渡るのに各々1分、2分、5分、10分かかり、懐中電灯が一個だけあります。
この吊り橋には二人しか乗れません。
4人が吊り橋を渡りきるには最短何分かかる？
簡単な例
説明の為に、4人が最初にいる地点をA, 吊り橋を渡った先をBとします。
例えば、最初に2分の人と5分の人がAからBに行くと、5分かかります。
懐中電灯はBにあるので、Aにいる1分の人と10分の人が移動するには、
2分の人か5分の人がAに戻らなければいけません。
2分の人がBからAに戻るとすると、2分かかります。
次に1分の人と10分の人がAからBに行くと、10分かかります。
懐中電灯はBにあるので、5分の人がBからAに戻るとすると、5分かかります。
最後に2分の人と5分の人がAからBに行くと、5分かかり、全員がBにいることになります。
このパターンだと合計で \(5+2+10+5+5=27\)分 かかります。
この例よりも短く出来ると思いますが、最短何分に出来るでしょうか？
この下に解答があります。
解答
最短 17分
最短のパターンの１つは以下のように
1分の人と2分の人が渡る(2分)
1分の人が戻る(1分)
5分の人と10分の人が渡る(10分)
2分の人が戻る(2分)
1分の人と2分の人が渡る(2分)
で合計 17分
解けましたか？
結構有名なので、知っていた人もいるかもしれません。
今後はこの問題の一般化を考えてみたいと思います。
コメント