◆東京都 明 さんからの解答
【問題１】
できます。
(1,8)→(2,7)→(3,8)→(2,9)→(4,9)→
(5,8)→(4,7)→(3,10)→(3,6)
【問題２】
できません。
２段目までを赤にすると下記のようなパターンになります。
（○：赤 ×：青 とします。）
パターン1
○ ○ ○ × × × ○ × × ○ ○ ○ ○ ○ ○３段目を赤にするためには４段目の青を下ろさなければならず、 下ろしたときのパターンは下記のとおりです。
パターン2
○ ○ ○ × × × ○ ○ ○ ○ ○ × × × ○ ○ ○ × × ○ ○ ○ ○ ○ ○ ○ ○ ○すなわちパターン１の３段目、４段目の形が５段目、６段目に現れます。
この状態から３段目の３個の石を下ろすためには５段目の３個の石をおろさなければなりません。
これは３段目と同じ状況が５段目に発生することになり、以下同じことが繰り返されることになります。
以上により、少なくとも有限回の手順で、３段目のまでのすべての石を赤にすることはできないことが証明されました。
【おまけ１】
任意のｎ個を選んだとき、そのｎ個すべてを赤にすることができ、特定のｎ+1個を選んだとき、どのように操作しても少なくとも1つは赤にできないようなｎが存在するとします。
（ｎが1の時は明らかにどのような石でも赤にでき、またｎ+1が６の時は【問題２】によりすべてを赤にできないような石の配置があることから、1≦ｎ≦5のｎが存在します。）
以下すべてを赤にできないようなｎ+1個の配置（便宜上「不可配置」と呼びます。）を探すことを考えます。
（1）不可配置は１段目の石を含みます。
含まない配置は初期状態ではすべて赤です。
（2）不可配置は２段目の石の少なくとも１個を含みます。
２個とも含まない配置は１段目の石を下ろしたときすべて赤となります。
（3）不可配置は２段目の石２個共を含みます。
もし含まないとした場合、次のようなパターンが許されます。
○ ？ × ？ ？ ○ ？ ？ ？ ○ ？ ？ ？ ？ ○（×の位置が不可配置に含まれない石とします。）
すると、「？」で出来た集合は初期状態の石の集合と全く同じ条件です。
したがって任意のｎ個を選択しても、すべてを赤にすることができます。
これは（1）の石を含めｎ+1個となるにもかかわらず、すべてを赤にできることになり、不可配置の条件を満たせません。
以上により、１段目、２段目の合計３個の石は不可配置に必須です。
１段目、２段目の石を赤にすると【問題２】のパターン1となります。
（4）ここで不可配置は３段目の３個の石の少なくとも１個の石を含むことを証明します。
もし含まないとすると次のようなパターンが許されます。
○ ○ ○ × × × ○ ？ ？ ○ ○ ？ ？ ？ ○ ○ ？ ？ ？ ？ ○「？」で出来た集合は、頂点の「×」を除けば、初期状態の石の集合で１段目の石を下ろしたものと同じものです。
これは不可配置に必須の上記３個の石を含めｎ+2個となるにもかかわらずすべてを赤にできることになり、不可配置の条件を満たせません。
次に上記の不可配置に必要な４個の石を選択した場合、４個だけではすべてを赤にできることを確認します。
具体的には下記のとおりです。
（パターン2からの操作になっています。）
○ ○ ○ ○ × × × × ○ ○ ○ × × × ○ ○ ○ × × ○ ○ ○ ○ ○ × ○ × ○ × × ○ ○ × × × ○ ○ ○ × × ○ ○ ○ ○ ○ × × ○ ○ ○ × × ○ × × × ○ ○ ○ × × ○ ○上記以外の４個を選択した場合は上で議論したようにすべて赤とすることができます。
以上により４個の石を任意に選択しても、すべての石を赤とできることが証明できました。
【おまけ２】
【問題２】でパターン2から３段目の３個の石を下ろすことができないことを示しましたが、この議論は３段目の隣り合った２個の石を下ろす場合でも全く同様に適用できます。
このことから下記が不可配置となります。
（□が不可配置です。）
□ □ □ ○ □ □ ○ ○ ○ ○ □ □ □ □ □ ○ ○ ○ ○ ○またパターン2の３段目の両端２個の石を選ぶ場合、および３段目の１個の石と５，６段目５個の「×」の石から１個の計２個を選ぶ場合は、すべてを赤にすることが確かめられます。
【おまけ３】
パスカルの３角形と同じように、頂点に１を置き、石が選択されていればすぐ下の２つの石の位置に上の石の値を加えて行く操作を上から順におこないます。
すべての石が選択されていれば以下のとおりです。
１ １ １ １ ２ １ １ ３ ３ １選択されていない石は、それが０でない時、１を引いてすぐ下の２つの石の位置に加えます。
選択された石が下記の□のようであれば、その下のような数列となります。
□ □ □ □ ○ □ ○ ○ ○ ○ １ １ １ １ ２ １ １ ２ ２ １ ０ １ ２ １ ０ ０ ０ １ １ ０ ０ ０ ０ ０ ０ ０ ０ ０一連の操作後の結果は、この数列で０の部分と選択された石が赤となり、それ以外の石が青という配列になります。
下記不可配置の場合はその下の数列となります。
□ □ □ ○ □ □ ○ ○ ○ ○ １ １ １ １ ２ １ ０ ２ ３ １数列の中に３ができるような操作はできないことを示すことができます。
証明は【問題２】と同じような方法でできます。
すなわち３以上の値ができると、その隣のいずれかは２以上であり、以下の石がすべて選択されていない場合でも、３以上と２以上の値の並びが下方向へ無限に続くことになります。
これは有限回で操作を完了できないことを示します。
以上のことから、上記方法で上から順に数列を作り、すべて２以下の数列となれば、有限回で０となり、選択された石をすべて赤にできます。
（選択した石が無限にあれば有限回で０にならない場合がありますが、この場合でも上から順に石を下ろす操作を無限に続けることはできます。）
途中で３以上ができれば選択した石のいずれかが青として残ることになります。
◆愛知県 Y.M.Ojisan さんからの解答。
【問題１】
(1,8)→(2,7)→(3,8)→(2,9)→(4,7)→
(3,6)→(5,8)→(4,9)→(3,10)
【問題２】
不可能 おまけ３参照
【おまけ１】
(1)頂点が４個の中に入っていなければ既に成立
(2)頂点が４個の中に入り残り３個は３段目以下のときは１回の操作で成立
(3)頂点および２段目の２個が４個の中に入り、残り１個が図１の紫枠/青枠のもの以外では４回の操作で成立。
また紫枠のものどちらか一方は後一回で赤にすることができる。
紫枠のもの３個のいずれかは図２のように、３回の操作で青枠のものを移動させた後、赤にすることができる。
(4)頂点および２段目の１個が４個の中に入り、残り２個が図３の紫枠のもの以外では２回の操作で成立。
また紫枠のもの両方を赤にすることは、図１から図２へで行った操作（３回）で可能。
紫枠のものの一方だけでよい場合は次の図４になり、後一回の操作で青枠のものの一方を赤に変えることが可能。
以上(1)-(4)により任意の４個を赤にできることが示された。
【おまけ２】
ある。下図５の赤の配置
【おまけ３】
セルに通過する〇の数を書き込む。
これはパスカルの三角形に似ている。
ただし少し違うのは、先に進まない（青）ことにより最大１引いてもよいことである。
逆に先に進んで赤にする場合はパスカル三角そのものである。
すると、セル値＝２以上 と セル値＝１以上が隣接する場合は、解答が無いことを意味する。
∵ 図６に示すように２段目においても セル値＝１とセル値＝２が隣接し、これらから再び３段目においても同様であり、操作が終了できない状態になるからである。
問題２の場合を見てみると、３段目までは１を引くことができず、３段目に２と１の隣接が現れるので不可能であることが分かる。
おまけ２の場合を図８に示す。
隣接２−１の繰り返しに陥る。
まとめると、
|
空けるところはパスカルの三角形の計算、 そうでない所はパスカルの三角形の計算−１を順次行って行き、 値に２と１以上の隣接が現れたら不可能。 有限段で全部０に成ったら可能。 |
◆ 問題へもどる
◆ 今週の問題へ
数学の部屋へもどる