問題「5この重さの違うコインを重い順に並べるには、最低何回天秤を使えばいいか」
答は7回です。私には解けなかったので、以下にDD++さんが、掲示板に書いてくださった解を転載します。
まず、前提として、以下のことができることは既知とします。
既に重さの順番がわかっている3枚のコインと、
重さのわからない1枚のコインがある場合、
天秤を2回使うことでこの4枚の重さの順番を決定できる。
詳細手順は初級問題の4-5回目と同じ手順なのでそちらを参考に。
というか、真ん中と比較した後、一番重いor軽いのと比較するだけですね。
これは可能であるということを手順中で使いますので、
あらかじめ確認をしておいてください。
では本題の「5枚を7回で」の手順です。
1回目は、5枚のうち任意の2枚を選び、重さを比較します。
2回目は、残る3枚のうち任意の2枚を選び、重さを比較します。
3回目は、これまで2回の比較で重かったほうどうしを比較します。
ここで、コインに以下のような命名をします。
A : 3回目で重かった方
B : 1回目もしくは2回目でAと比較したもの
C : 3回目で軽かった方
D : 1回目もしくは2回目でCと比較したもの
E : まだ1回も天秤に載せていないもの
つまり、3回目までに A>C>D かつ A>B と判明している状態です。
A,C,D の3枚の重さの順番が既に判明しているので、
これに E を加えた4枚の重さの順番を、
4-5回目を使って、前提で述べた手順を用いて決定します。
これによってできた4枚の重さの順番からAを取り除くと、
C,D,E の3枚の重さの順番が判明していると考えることができます。
そこで、この C,D,E に B を加えた4枚の重さの順番を、
6-7回目を使って、再び前提で述べた手順を用いて決定します。
これで天秤の出番はおわり。
最後にできた4枚の順番に対し、5回目の後に抜いたAを元の場所に戻します。
戻すべき箇所にBがいなければ、そのまま戻して5枚の順序が出来上がります。
戻そうとした同じところにBがいた場合は、
1回目もしくは2回目で A>B と判明していますので、
Bのすぐ左に戻せば5枚の順序が出来上がります。
2^7=128パターン判別可能なのに対して120パターンの仕分けなので
無駄な8パターンが存在するはずですが、それは
5回目の後に E>A>C>D という順番になった上で、6回目で B>C だった場合、
7回目を待たずに全ての順番が決まってしまうパターン×1-3回目の自由度で2^3=8倍
のところにあります。
これ以外は全て7回目の結果が出るまで完全な順番はわかりません。