http://slashdot.jp/~WindVoice/journal/475983

もう1ヶ月以上前のエントリだし、WindVoice氏らは今はもう普通に解く段階を終えて、プログラムだとかオーダだとかの話をしているのに、今更ながら普通に手計算で解いてみた。しかも、かなりアルゴリズムにしにくそうな方法で。

◆ 問(笑わない数学者[ISBN4-06-264614-5]P74～P75の問題)

五つのビリヤードの玉を、真珠のネックレスのように、リングにつなげてみるとしよう。玉には、それぞれナンバが書かれている。さて、この五つの玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも、二つでも、五つ全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバを足し合わせて、1から 21までのすべての数ができるようにしたい。さあ、どの玉のナンバの玉を、どのように並べて、ネックレスを作れば良いかな？

はじめに： WindVoice氏の考察を使用する。
自分で考えろよ！って話だが、解く前に読んでしまったので、使うことにする。

すなわち、
玉の取り方が違うなら、取った玉の和も違わなければならない(結果が重複していてはならない)
そのためには、使用する玉a,b,c,d,eはすべて、異なる自然数で、うち、1と2は確実に含まれている
また、すべての玉の和は21

ここからは、自力で考えた。
もし、a,b,c,d,eのうち、奇数が1つだけなら、そこからいくつの奇数が作り出せるか？
→数え上げて見たところ、11個だった。

奇数が2つなら？
すべての玉を足した時の和が偶数になるので、ありえない

奇数が3つなら？
3つが固まっている場合: 11個
2つが隣り合っていて、1つだけ、離れている場合: 10個

奇数が4つなら?
すべての玉を足した時の和が偶数になるので、ありえない

奇数が5つなら?
少なくとも2を含むという条件に反する

1～21までにある奇数は11個。
なので、奇数が1つだけか、奇数が3つ隣り合っている場合だけが解。

奇数が1つだけの場合：
1,2は既知なので、残りは偶数3つで合計が18になるもの。
4,6,8の組み合わせしかない。

{1, b, c, d, e} のb, c, d, eに2,4,6,8を入れていく。

3を作るために、1と2は隣り合っていなければならない。
{1, 2, c, d, e}
5を作るために、1と4は隣り合っていなければならない。
{1, 2, c, d, 4}
2+c != d+4
が成立するには、c=6, d=8が必要。
{1, 2, 6, 8, 4}
2+6=8ができてしまったが、8は単一で存在する。

よって、奇数1つでは条件を満たす解は得られない。

奇数3つが固まっている場合:
{A, B, C, 2, e}に数字を入れていく。ただし、大文字には奇数, 小文字には偶数が入る。

2と1が隣接する場合:
{A, B, 1, 2, e}
4を作るためには、B=3が必要。
しかし、1+2=3のため、3があってはならない。

2と1が隣接しない場合:
{1, B, C, 2, e} or {A, 1, C, 2, e}

{1, B, C, 2, e}を考える

4を作るために、B=3が必要
{1, 3, C, 2, e}
6を作るために、e=2またはe=4が必要
しかし、2があるためe=2は不可。1+3=4のため、e=4も不可。

{A, 1, C, 2, e}を考える。
4を作るために、A=3またはC=3が必要。
{3, 1, C, 2, e} or {A, 1, 3, 2, e}

楽そうな{A, 1, 3, 2, e}から考える。
7を作るためには、A=7が必要。
{7, 1, 3, 2, e}
合計が21より、e=8となるが、7+1=8で不可。

{3, 1, C, 2, e}を考える。
7を作るためには、C=7またはC=5が必要。

C=7の場合：
{3, 1, 7, 2, e}
合計が21より、e=8となるが、7+1=8で不可。

C=5の場合：
{3, 1, 5, 2, e}
合計が21より、e=10
{3, 1, 5, 2, 10}

確認したところ、これは条件を満たしている。

とまぁ、奇数／偶数を使ったら楽になるかなぁ、と思ったものの、
まぁ、楽だけどエレガントじゃないなぁ、って解法になってしまったのです。