４つの部屋


A B C D の４個の部屋があり、１から６６までの数をどれかの部屋へいれます。
同じ部屋に入った２つの数の和と一致する数はその部屋の入れることはできないとして
どのように４個の部屋に配分すればよいか、
６７の数ではこの条件に合う配分はないことを証明できるか。

解が存在しないことを証明するには可能性の低い枝も全て試行するので、大変な時間が
かかります。
まず部屋の番号が相対的に変わった場合、答えを計算する必要がないので、一部の数
１、２、３ の置く部屋を固定する。
部屋に最初に置く数は小さい順に制限してもよい。
テストの都合上両方をプログラムに追加した。
答えがないことを確認する場合、N=67でなくても、それより小さい数で解がないと
証明してもよい。それで時間短縮ができると思った。

証明結果のまとめ

部屋の固定
1,2,3,4		 可能な数不可能な数所要時間(s)リスト
0,0,1666727372ans67
0,1,0,1626344177ans67a
0,1,1,0??603041ans60
0,1,1,162663437ans66b
0,1,1,2??603253ans60
0,1,2,0??602872ans60
0,1,2,160614699ans61n
0,1,2,262662673ans66c
0,1,2,3??602019ans60
部屋の固定は1,2,3,4を配置できるすべての場合、ただし対象な配置は除く。
可能な数の意味はN=XXでmono67を実行し、解が存在したXXを示す。
不可能な数の意味はN=XXでmono67を実行し、解が存在しなかったXXを示す。
したがって、すべてのケースで不可能な数があれば証明されたことになる。

使用したフ゜ロク゛ラム


最終的には全て　Mono67 で実行できる。途中試行錯誤でMono67Eを一部使用(ans60)
mono67 は解が存在しないことを証明する目的、途中で部分実行機能追加
Mono67EはMono67で解が無い場合の速度の向上を目指したものであるが、
速度向上は失敗、ただし部分に分けて実行結果を得られるようにした点は役に立った。

考察


これらすべてのケースで６７の数では条件に合う配分がないことが証明できた。
途中でN=60からN=67まで指定を変えながら、証明したが、この指定を変えたことが
時間短縮になったかどうか疑問が残った。素直にN=67でMono67を実行すれば充分であった
とおもう。
分割して実行したのは、途中確認しながら実行できるので効果はあった。

骨折り損のくたびれ儲け


解が存在しないことを証明するには可能性の低い枝も全て試行するので、大変な時間が
かかります。
速度向上で、有りそうな枝を優先的にたどる方法も役にたちません。
Mono67Eは持ち回り情報（その局面の情報）をビット表現にし、long ４個　に
集約しました。（速度アッフ゜に貢献なし）
探索において別のルートで同じ状態になる場合、たとえば　部屋を　a b c d と表現した
として 1a 2a 2b 4a と配置した状態と、順序をかえて　2a 2b 1a 4a と配置した状態
は同じになるのに、プログラムでは重複に気づかずこの後を再度計算しているのでは
ないかと懸念して、long ４個　で重複を比較するようにした。
実際に、このプログラムは配置する順序は一定していないようですが、やってみた結果、
重複は見つかりませんでした。
よく考えると、配置する順序は一定ではないのですが、局面が決まると順序が一意に
決まるので重複は発生しないのです。
本当に「骨折り損」でした。

残された課題


ここで取り上げた、数を自由度の小さい順に配置する方法は、６７で解が存在しないの
証明時間の短縮に貢献しているか。
他に時間短縮の方法はないか