笑わない数学者 [Book]
笑わない数学者 森博嗣 講談社ノベルスたく丸の学校では、長期休暇に大量の宿題が出る。この夏休みもどっさりと宿題が出て、サッカーや秋の行事の準備も合わせて忙しい日々だ。数学は問題集2冊を全部やって来いという内容で、どんなことをやっているのかと覗いてみると円順列や数珠順列の問題が出ていた。数珠順列といえば、直接の関係はないが、次のパズルを思い出した。
さて、では、もう一つ問題を出そう。五つのビリヤードの玉を、真珠のネックレスのように、リングにつなげてみるとしよう。玉には、それぞれナンバーが書いてあるな。さて、この五つの玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも二つでも、五つ全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバーを足し合わせて、1から21までのすべての数ができるようにしたい。さあ、どのナンバーの玉をどのように並べて、ネックレスを作れば良いかな?これは、森博嗣の推理小説、「笑わない数学者」の中に出てくるパズルだ。でも小説の中では解答が出てこないんだな。初めて読んだとき、気になったおやじは少し考えたものの解法を思いつかず、プログラムを書いてパソコンに解かせてしまった。今回、思い出したついでにこのパズルを少し考えて見た。
まず、条件に添った玉の取り方が何通りあるかを考えてみる。1個取るのは5通り。4個取るのは、1個取る場合に残った4つを取るのと同じだから5通りある。2個取るのは並んだ2つを取るのだからこれも5通り。3個は2個の裏返しで、やはり5通り。5個取るのは全部取ることだから1通り。足し合わせると、5×4+1=21通りとなる。21通りの取り方で21種類の数字を作らなければならないということは、取った玉の数字の合計は必ずバラバラでなければならないということだ。ある数字になる玉の取り方はただ一通りしかなく、全部の玉の合計は21であるということも言える。
次に必ず含まれる玉がないかを考えると、「1」と「2」の玉は必ず必要だと分かる。この2つの数字は異なる数字の和として表すことが出来ないからだ。これらをまとめてみる。
- 「1」と「2」の玉を含んでいる
- 5つの玉の合計は21になる
- ある数になる玉の取り出し方は1通りしかない
- 1,2,3,4,11
- 1,2,3,5,10
- 1,2,3,6,9
- 1,2,3,7,8
- 1,2,4,5,9
- 1,2,4,6,8
- 1,2,5,6,7
まず一つ目の組み合わせ、1,2,3,4,11を考えて見る。図1のA～Eに数字を入れて検証することになる。まず「1」をどこに入れるかだが、これはAに決め打ちでよい。他の位置に入れた場合は、ぐるっと回して「1」の玉が一番上に来るようにすればAに置いたのと同じになるからだ。次に「2」だが、これは「1」の両隣、すなわちBとEの位置に置くことができない。この2つの玉の合計が3になり、「3」の玉一つを取り出したときと同じ値になり、条件3.に反するからだ。このため、「2」の位置は、CかDだが、CとDは裏返せば同じ位置になるので、Cに決めても構わない。
同じようにして「3」は、「4」の玉があることを考えると「1」の両隣におくことができないため、Dに決まる。これで3つの場所が決まった（図2）。後は「4」をBに置いたケースとEに置いたケースの2通りを検証すればよい。しかし、「4」をBに置いてもEにおいても、5が二通り（1-4と2-3）出来てしまい、上の条件3.に反する。以上からこの組み合わせでは、条件を満たす並べ方ができないことがわかった。
その次の組み合わせ、1,2,3,5,10を考えてみよう。「1」をA、「2」をCに置くのは上と一緒だ。「3」は「5」の玉があることを思えば、「2」の両隣に置くことができないので、Eに決まる。「5」はBにもDにも置けるが、Dに置くと6を作ることができないので、Bに置く（図3）。これで、検証してみると、見事に1から21までの数字を作れることがわかる。これが答えだ。ちなみに検証は1から10まで作れることがわかればよい（理由は省略）。他にも答えがないかは、この作業を続ける必要があるが、面倒なのでやっていない。プログラムにやらせてみたところ、この解答の1通りだけだった。このパズルは玉が5個だが、プログラムを使って11個まで調べてみた。ビリヤードだから15個まで調べたかったのだが、10個を超えると順列を作るのに時間がかかるのだ。。
| 玉の数 | 数字 | 並び順 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1～3 | 1-2 |
| 3 | 1～7 | 1-2-4 |
| 4 | 1～13 | 1-2-6-4 1-3-2-7 |
| 5 | 1～21 | 1-3-10-2-5 |
| 6 | 1～31 | 1-2-5-4-6-13 1-2-7-4-12-5 1-3-2-7-8-10 1-3-6-2-5-14 1-7-3-2-4-14 |
| 7 | 1～43 | なし |
| 8 | 1～57 | なし |
| 9 | 1～73 | なし |
| 10 | 1～91 | なし |
| 11 | 1～111 | なし |
| n | 1～n(n-1)+1 | － |
使ったプログラムは以下。使う玉の数を1から初めて15まで求めようとするが、10を過ぎると時間がかかり、途中でキャンセルした。答えは数珠順列で考えなければならないのだが、円順列でやったため、裏返すと同じになるものもリストアップされてしまう。
/*-------------------------------------------------------------*/ /* Title: MATHEMATICAL GOODBYE 2009/8/7 */ /*-------------------------------------------------------------*/ #include "stdio.h" #define MAXNUM 15*14+2 // Prototypes void make_combination( int position, int value ); void make_permutation( int position ); void check_sum(); void print_answer(); // set Global static int num; static int permulist[MAXNUM]; static int checklist[MAXNUM]; // Main int main( int argc, char* argv[] ) { for ( num = 1; num <= 15; num++ ) { printf("\n\n-- Number of Balls = %d --\n", num); permulist[num-1] = 1; // We must include 1. if ( num > 1) { permulist[num-2] = 2; // We must include 2, too. } make_combination( num-3, 15 ); } return 0; } // Make combination of balls void make_combination( int position, int value ) { int i; if ( position < 0 ) { make_permutation( num-1 ); return; } for ( i = value; i > position+2; i-- ) { permulist[position] = i; make_combination( position-1, i-1 ); } } // Create Circular Permutation void make_permutation( int position ) { int i, j, k; if ( position < 2 ) { check_sum(); return; } j = position - 1; for ( i = position-1; i >= 0; i-- ) { k = permulist[j]; permulist[j] = permulist[i]; permulist[i] = k; make_permutation( j ); permulist[i] = permulist[j]; permulist[j] = k; } } // Check it void check_sum() { int i, j, k, maxsum, sum; for ( i = 0; i < MAXNUM; i++ ) { checklist[i] = 0; } maxsum = num*( num-1 )+1; sum = 0; for ( i = 0; i < num; i++ ) { sum += permulist[i]; } if ( sum != maxsum ) { return; } checklist[sum] = 1; for ( i = 0; i < num; i++ ) { sum = 0; for ( j = 0; j < num-1; j++ ) { k = ( i+j ) % num; sum += permulist[k]; if ( checklist[sum] != 0 ) { return; } checklist[sum] = 1; } } print_answer(); return; } // Print right circular permutation void print_answer() { int i; for ( i = 0; i < num-1; i++) { printf("%d - ", permulist[i]); } printf("%d\n", permulist[num-1]); return; }
