Entries

パズル「目盛りの消えた定規」について

 突然ですが問題です。

10cmの長さの定規を使い、1cmから10cmまでを1cm単位で測りたい場合、定規には最低幾つの目盛りがあれば良いか?

「そんなの(両端を含まずに)9個じゃね?」 甘い甘い。実はたった4個の目盛りだけで、1cmから10cmを全て表すことができます!
 何故かって? 下の画像を御覧ください。
目盛りの消えた定規1
 1図は普通の定規です(1つ1つのクシの間が1cmだと考えて下さい)。一方、2図はそれより随分クシの本数が少なくなってしまいました。これでちゃんと測れるのか、と思うでしょう。
 ところが2図でも、「A-B間」「A-C間」「D-G間」「C-G間」「B-G間」「A-G間」「D-K間」「C-K間」「B-K間」「A-K間」がそれぞれ1cmから10cmに対応しています。要するに、2図のような状態でも、キチンと定規として使うことが可能なのです!


 さてここで、この記事名の意味がなんとなくつかめてきたと思います。要するに、一般化すると、

長さNの定規に、長さ1単位の間隔で幾つか目盛りを付けて、長さ1からNまでを測りたい場合、定規には最低幾つの目盛りがあれば良いか?

という問題なのです。もちろん普通の定規のように(N-1)個の目盛りを振れば確実に測れますが、それだと何も面白くありませんので。
 ポイントとしてはまず、仮にM個の目盛りが振られていた場合、長さを取ることができる組み合わせ数は最大M(M+1)/2通りであることがあります。例えばN=100とすると、Mは最低でも14以上です。
 また、間隔がn空いていることを "n" と表記すると、左から順に「"1" が(p-1)個」「"p" がk個」「"q"が1個」と目盛りを振った時(ただし2≦p≦N、N=(k+1)*p+q-1、1≦q≦pとする)、

・長さ1~p-1の場合は、"1" を適当に組み合わせて(連続した間隔の合体で)作れる
・長さp~2p-1の場合は、"p" 1個と"1"を0~(p-1)個を組み合わせて作れる
・長さ2p~3p-1の場合は、"p" 2個と"1"を0~(p-1)個を組み合わせて作れる
 ……
・長さk*p~(k+1)*p-1の場合は、"p" k個と"1"を0~(p-1)個を組み合わせて作れる
・長さ(k+1)*p~(k+1)*p+q-1の場合は、"q" も利用することで組み合わせにより作ることができる。
 これは、1≦q≦pなので、"1" や "p" を上手く調節すれば可能であることにもある(証明略)。

のようにして、長さ1~Nまで測ることができます。例えばN=100、p=√(N+1)≒10とすると、k=9、q=1とすれば、長さ1~100まで測れる(目盛りの数は結局19個) ことになります。
(参考:「目盛りの消えた定規」(http://d.hatena.ne.jp/tamura70/20100112/ruler))


 当然、目盛りの振り方を手作業で試行錯誤していてはキリがありません。定規の長さをlen、目盛りの数をnとして数式風に書くと(len-1)C(len-n-1)通り=(len-1)!/(len-n-1)!/n!通りあるので、lenが大きくなると調べる振り方の数は急激に増大します。例えば、(len,n)=(14,4)の場合715通りですが、(18,5)の場合6188通り、(24,6)の場合100947通りとなります。
 したがってコンピュータで探すことになるのですが、どちらにしても結局は虱潰しに探すので、数字が大きくなるに連れ、計算時間がどんどん延びていってしまうのは否めません。簡単な計算プログラムを組んでみました(C言語で)。
00: #include 
01: #include
02: void divset(int *, int, int);
03: int check (int *, int, int*, int);
04: void divmes(int *, int, int);
05: int main(){
06: int n = 2, len = 2, i, p;
07: int *div, *num;
08: div = (int *)malloc(sizeof(int) * n);
09: num = (int *)malloc(sizeof(int) * (len+1));
10: divset(div, n, len);
11: while(1){
12: if(check(div, n, num, len) == 1){
13: divmes(div, n, len);
14: len++;
15: divset(div, n, len);
16: free(num);
17: num = (int *)malloc(sizeof(int) * (len+1));
18: }else{
19: p = n - 1;
20: while(div[p] == 1)
21: p--;
22: if(p == 0){
23: free(div);
24: n++;
25: div = (int *)malloc(sizeof(int) * n);
26: divset(div, n, len);
27: }else{
28: div[p-1]++;
29: for (i = p; i < n - 1; i++)
30: div[i] = 1;
31: div[n-1] = len;
32: for (i = 0; i < n - 1; i++)
33: div[n-1] -= div[i];
34: }
35: }
36: }
37: return 0;
38: }
39: void divset(int div[], int n, int len){
40: int i;
41: for(i = 0; i < n - 1; i++)
42: div[i] = 1;
43: div[n-1] = len - n + 1;
44: return;
45: }
46: int check(int div[], int n, int num[], int len){
47: int flg = 1, i, j, sum;
48: for(i = 0; i < len + 1; i++)
49: num[i] = 0;
50: for(i = 0; i < n - 1; i++){
51: sum = div[i];
52: num[sum] = 1;
53: for(j = i + 1; j < n; j++){
54: sum += div[j];
55: num[sum] = 1;
56: }
57: }
58: num[div[n-1]] = 1;
59: for (i = 1; i < len + 1; i++) {
60: if (num[i] == 0) {
61: flg = 0;
62: break;
63: }
64: }
65: return flg;
66: }
67: void divmes(int div[], int n, int len){
68: int i;
69: printf("%d(%d)=%d", len, n, div[0]);
70: for (i = 1; i < n; i++)
71: printf("+%d",div[i]);
72: printf("\n");
73: return;
74: }

 内容としては、最初に「目盛り間の間隔が右端以外全て1」という定規を生成して、後はその定規が使えるかをcheck関数でチェックしながら「1つづつ」次へ次へとシフトしていくイメージです(divmes関数で結果表示)。例えばプログラム中の変数が「len=6,n=3」だったとすると、目盛り間の間隔が[1,1,4]→[1,2,3]→[1,3,2]→[1,4,1]→[2,1,3]→[2,2,2]→[2,3,1]→[3,1,2]→[3,2,1]→[4,1,1]となります。

 こんなんでもlen=30までは割と一瞬で解を表示してくれたりします。ただ、当然ですが、後々になっていくにつれ、計算量の壁が大きくのしかかってきます。一応、「左端が1の場合だけチェックすればいい」(端に "1" が無いと長さN-1が測れないし、左端と限定すれば対称なものを弾ける)という法則があり、また、「N'>Nならば、最低限必要な目盛り数nはn'≧n」というヒューリスティクスもありますので、それを利用すれば計算量を大きく減らせたりしますが、限度というものがあります。

 自分の環境(i5-3210M)でこれの改良版を走らせたところ、長さ68に12個の目盛りを追加したもの(標準出力では"68(13)=1+1+3+5+5+11+11+11+6+6+6+1+1"と表示されるもの)まで計算し終えるまでに3時間掛かりました。長さ69の場合どれほど時間が掛かったのかはお察し下さい

 続きは次回。
関連記事
スポンサーサイト
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/39-b29affa8

トラックバック

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

Appendix

プロフィール

YSR

Author:YSR
「YSR」「YSRKEN」「◆YSRKENkO6Y(~2013/08/25)」「◆YSRKEN.ceVZZ(2013/08/26~)」として活動しています。
プログラミングと艦これが趣味です。
プロフ画像はCrystalDiskInfoの水晶雫ちゃんです。
主な創作物についてはhttp://ysrken.blog.fc2.com/blog-entry-76.htmlをご覧ください。

カレンダー(月別)

10 ≪│2017/11│≫ 12
- - - 1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 - -

全記事表示リンク

全ての記事を表示する

QRコード

QR

総アクセス数

アクセス数

現在の閲覧者数: