19/08/13 19:47:49.71 HqlhG0Td.net
次は4回目の天秤使用になりますが、ここで、EとAを比べたとします。E>Aなら3通り、E<Aなら12通りに分岐しますが、
これでは、残り三回では並べ替えられません。同様にEとDの比較も、3通りと12通りに分岐し、不可能なのがわかります。
それでは、EとBでは？ E>Bとなると、ABCDでは2通り、ACBDでは3通り、ACDBでは4通りなので、合計9通り。
やはり、この比較も失敗であることがわかります。
で、EとCのみが残されます。 E>Cとなると、ABCDでは3通り、ACBDでは2通り、ACDBでは2通りなので、合計7通り。E<Cなら8通りと、
この比較なら、残り三回で可能なことがわかります。その他、Eを使わない方法も、5通りと10通りに分岐する等、不可能な事がわかります。
つまり、4回目の比較は、（ここでのネーミングでは）EとCにユニークに絞られています。このように、比較後の分岐状況を
検討しつつ、比較ルートを見いだしていけば、ゴールにたどり着けます。この後続の比較方法は省略しますが、いくつか補足しておきす。
三回目の比較は、対称性からもわかるように、「トップ」ではなく、「最軽量」を決める比較でも可能です。
が、これら以外の方法、例えば、心情的にEを登場させたくなるかもしれませんが、このような方法は全て失敗することが、
分岐数のカウントからわかります。
「ソート済みの2^k-1個の重り」に、一つの重りを加え、天秤をk回使用して、「ソート済み2^k個の重り」にするのは、
情報理論的に無駄がなく、いわば定石です。k=2の場合を上の図解で紹介した方法では多用しています。
この定石に従えば、４回目に続いて五回目もEが登場するのが自然です。しかし、もし、四回目の比較でE>Cならば、
EABCD、AEBCD、ABECD、EACBD、AECBD、EACDB、AECDB という7通りに絞られていますが、
AとEの比較という定石の他、BとCの比較という方法も存在していることを補足しておきます。