アルゴリズムパズル（その 1）：おもりの並び替え

本連載ではこれまで 8 回にわたって、全探索・二分探索・貪欲法・動的計画法といったアルゴリズムを紹介しました。今回は少し趣向を変えて、アルゴリズムを使って解ける数理パズル的な問題を 1 つ紹介します。

プログラミングを知らない人でも楽しめるものになっているので、ぜひ、より効率良く問題を解く手順を自力で考えてみてください。

アルゴリズムパズルに挑戦!

机の上に 5 個のおもり A・B・C・D・E が置かれています。あなたは 1kg・2kg・3kg・4kg・5kg のおもりが 1 個ずつあることを知っていますが、それぞれのおもりの重さを知りません。「2 つのおもりを天秤に乗せ、重さを比較する」という操作をできるだけ少ない回数行うことで、全てのおもりの重さを特定してください。

比較回数に制限がなければ、重さを特定すること自体はそれほど難しくありません。しかし、一番少ない比較回数で重さを特定するには、どうしたらよいでしょうか。以降では、ヒントになる考え方を説明していきます。

10 回で必ず当てる方法

まずは一番分かりやすい「10回で当てる方法」について見ていきましょう。この場合、全てのおもりのペア（全部で 10 通りあります）について、天秤で重さを比較することを考えます。このとき、各おもりが 4 回ずつ比較され、以下のようになるため、全てのおもりの重さを特定することができます。

• 4 回中 0 回について「重い方」だった場合、そのおもりの重さは 1kg
• 4 回中 1 回について「重い方」だった場合、そのおもりの重さは 2kg
• 4 回中 2 回について「重い方」だった場合、そのおもりの重さは 3kg
• 4 回中 3 回について「重い方」だった場合、そのおもりの重さは 4kg
• 4 回中 4 回について「重い方」だった場合、そのおもりの重さは 5kg

下図はその具体例です。なお、同じような方法を使うと、n(n-1)/2 回の比較で n 個のおもりを軽い順に並べ替えることが可能です。