回答編集履歴
1
数学的に厳密な証明になっていない箇所について、その旨及び直感的な説明を追記しました。
answer
CHANGED
|
@@ -12,9 +12,12 @@
|
|
|
12
12
|
|
|
13
13
|
なぜなら、「任意の色変え操作について、それと比較して同等またはより有利な（＝最終的な手数が増えない）入れ替え操作が存在する」ということが言えるからです。
|
|
14
14
|
|
|
15
|
-
具体的には、例えば、「ある赤い石（Xとする）を一つ選び、その石を白に変える」という操作を行う代わりに、「赤い石Xと、Xよりも左にある白い石Yを入れ替える」ことにしても、不利になる（最終的な手数が増える）ことは
|
|
16
|
-
（
|
|
15
|
+
具体的には、例えば、「ある赤い石（Xとする）を一つ選び、その石を白に変える」という操作を行う代わりに、「赤い石Xと、Xよりも左にある白い石Yを入れ替える」ことにしても、不利になる（最終的な手数が増える）ことはありません。
|
|
16
|
+
（この点について、私も厳密な証明はできないのですが、色変えの代わりに入れ替えを行うことにより、「赤い石X（の位置にある石）を白に変える」ことに加えて「左にある邪魔な（白い石はなるべく右にあったほうが最終形に近づくという意味で、左にある白い石は邪魔です）白い石Y（の位置にある石）を赤に変える」ことを同時に達成できるので、同等またはより有利になる、と考えると直感的には分かりやすいのではないかと思います。）
|
|
17
17
|
|
|
18
|
+
なお、白い石を赤に変える操作についても、上記と同様のことが言えます。
|
|
19
|
+
また、赤い石Xよりも左に白い石が一つもない状態であれば、そもそもそのようなXに対して操作を行う必要がないので、そのような場合を考える必要はありません。
|
|
20
|
+
|
|
18
21
|
以上を踏まえ、入れ替えの操作のみで、「赤い石は左側に、白い石は右側に集める」状態を達成する方法を考えます。
|
|
19
22
|
すると、操作の前後で赤い石及び白い石のそれぞれの総数は変わらないことになるので、「左から順に初期状態における赤い石の総数個だけ赤い石が並び、その右に初期状態における白い石の総数個だけ白い石が並んでいる」状態が最終形であることが分かります。
|
|
20
23
|
したがって、各手番ごとに「左から赤い石の総数個の範囲からはみ出している赤い石（Xとする）」を1つ選び、赤い石Xを「左から赤い石の総数個の範囲に存在する白い石」と入れ替える操作を行っていくのが最善となります。
|