パズルか数学か、それともアルゴリズムか（その１）
難しい（かも知れない）話、第２弾です。一応、前回の話よりは取っ付き易いと思います。
集合Ｘがあったとします。この集合には要素a_1,a_2,…,a_nという、ｎ個の要素が属しています。
ここで、集合Ｘに属する任意の２つの要素（A,Bとします）に対し
- ＡよりＢのほうが大きい
- ＡとＢは等しい
- ＢよりＡのほうが大きい
のうちどれかが必ず成立するものとします。
このとき、Ｘの要素を適切に並び替えることで、「全ての要素を大きい順に並び替えること*1」は可能でしょうか？
答えは…
可能とは限りません。反例を挙げますと…
- 集合Ｘの要素：「グー、チョキ、パー」
- 要素同士の大小は「じゃんけんにおける勝敗」で定める
このとき、集合Ｘの要素を「完璧に、強い順に」並べることが不可能であることは明らかでしょう。
なぜ不可能かということですが…本質的には上で述べたような「並べ替え」が「きれいに」行えるためには、「比較する」という操作が、次のような条件を満たしていないといけない、ということになります。すなわち
ＡよりＢが大きく、ＢよりＣが大きいならば、ＡよりＣが大きくなければならない。
この性質*2を「比較」に対する前提条件に組み込まないと、「きれいに並べ替える」ことはできません。
以上が前フリその１です。多分続きます。…多分。（汗）
