目盛りの消えた定規

このエントリーをはてなブックマークに追加

下のようにいくつかの目盛が消えて,間に2つしか目盛が残っていない6cmの定規(ものさし)を考える.

     +-----------------------------+
     |                             |
     |    |              |         |
     +----+--------------+---------+
     0cm  1cm            4cm       6cm

この定規は,1cmから6cmまでを計ることができる.

  • 0cm と 1cm の間で,1cm
  • 4cm と 6cm の間で,2cm
  • 1cm と 4cm の間で,3cm
  • 0cm と 4cm の間で,4cm
  • 1cm と 6cm の間で,5cm
  • 0cm と 6cm の間で,6cm

目盛間の長さの列で表すことにすれば,この定規は 1,3,2 で表すことができる.

  • r cmの定規で,1cmからr cmまで計るには,最小でいくつの目盛りが必要となるだろうか?

この問題は,有名なゴロム定規(目盛り間の距離がすべて異なる)とは違い,目盛り間の距離に同じものが現れても良いが, 1からrまでのすべての距離が少なくとも一回は現れなければならない.

  • 2013-02-24追記: Wikipedia 等では Sparse Rulerと呼ばれているようだ.
  • 2013-03-04追記:マーチン・ガードナー著 "The Incredible Dr. Matrix"(邦訳: メイトリックス博士の驚異の数秘術),1977年6月出版の第6章にもメイトリックス博士の定規として記載されているようだ.
  • 2013-03-08追記: YSRさんのページへのリンクを追加した.

問題

与えられた正の整数 r に対して,以下の条件を満たす正の整数の列x1, x2, ..., xm のうち,m が最小になるものを求める.

  • r = x1 + x2 + ... + xm
  • 1 ≦ k ≦ r なる各整数 k について,k = xi + xi+1 + ... + xj となる1 ≦ i ≦ j ≦ m が存在する.

与えられた正の整数 r に対する m の最小値を M(r) で表すことにする.
また,与えられた r に対して,以下を満たす最小の頂点数のグラフを求める問題と考えることもできる.最小の頂点数は M(r)+1 となる.

  • 各頂点には,異なる非負整数がラベルとして割り当てられている.
  • r 個ある各辺には,1から r の異なる値がラベルとして割り当てられている.
  • 各辺のラベルは,隣接する頂点のラベルの差に一致している.

下限

m=M(r) とすると,計れる長さの組合せは m+1C2 = m(m+1)/2 通りである.定規の長さ r は,これを越えられないから,r ≦ m(m+1)/2 が成り立つ.これを解くと,以下の関係が成り立つことがわかる.

\lceil \sqrt{2r+1/4} - 1/2 \rceil \leq M(r)
上の関係式の左辺を M0(r) で表すことにする.M0(r) ≒ √(2r) である.

上限

以下のようなパターンを考える(ただし 2 ≦ p ≦ r).

1^{p-1}, p^k, q
このパターンは,r = (k+1)p+q-1, 1 ≦ q ≦ p を満たす時,解となっている.すなわち,rp で割った商が k+1,余りが q-1 である.また,この時 m=p+k である.
p = [√(r+1)] と置くと,以下の関係式が成り立つ.

M(r) \leq p + \lfloor r/p \rfloor - 1
上の関係式の右辺を M1(r) で表すことにする.M1(r) ≒ 2√(r) である.

M(r) の表

rM0(r)M1(r)M(r)解の例
22221,1
32221,2
43331,1,2
53331,1,3
63431,3,2
74441,1,1,4
84441,1,3,3
94541,1,4,3
104551,1,1,3,4
115551,1,1,4,4
125651,1,1,5,4
135651,1,4,4,3
145661,1,1,1,5,5
155661,1,1,1,6,5
166761,1,1,5,4,4
176761,1,1,5,5,4
186771,1,1,1,1,7,6
196771,1,1,1,5,5,5
206871,1,1,1,6,5,5
216871,1,1,1,6,6,5
227871,1,1,5,5,5,4
237871,1,9,4,3,3,2
247881,1,1,1,1,7,6,6
257981,1,1,1,1,7,7,6
267981,1,1,1,6,5,6,5
277981,1,1,1,6,6,6,5
287981,1,11,5,3,3,3,1
298981,1,12,4,3,3,3,2
3081091,1,1,1,1,7,5,7,6
3181091,1,1,1,1,7,6,7,6
3281091,1,1,1,1,7,7,7,6
3381091,1,1,1,6,6,6,6,5
3481091,1,1,12,5,4,4,3,3
3581091,1,15,4,3,3,3,3,2
3681191,2,3,7,7,7,4,4,1
37911101,1,1,1,1,1,8,8,8,7
38911101,1,1,1,1,7,7,6,7,6
39911101,1,1,1,1,7,7,7,7,6
40911101,1,1,1,6,7,7,5,6,5
41911101,1,1,12,6,4,5,4,4,3
42912101,1,1,16,5,4,4,4,3,3
43912101,2,3,7,7,7,7,4,4,1
44912111,1,1,1,1,1,8,8,7,8,7
45912111,1,1,1,1,1,8,8,8,8,7
461012111,1,1,1,1,7,7,7,7,7,6
471012111,1,1,1,1,7,8,8,6,7,6
481012111,1,1,18,5,5,2,4,3,4,4
491013111,1,1,21,5,1,4,4,4,4,3
501013111,1,1,20,5,4,4,4,4,3,3
511013121,1,1,1,1,1,1,9,9,9,9,8
521013121,1,1,1,1,1,8,8,7,8,8,7
531013121,1,1,1,1,1,8,8,8,8,8,7
541013121,1,1,1,1,1,8,9,9,7,8,7
551013121,1,1,1,1,7,8,8,8,6,7,6
561114121,1,1,5,11,1,11,11,4,6,3,1
571114121,1,1,25,5,1,4,4,4,4,4,3
581114121,1,1,24,5,4,4,4,4,4,3,3
591114131,1,1,1,1,1,1,9,9,8,9,9,8
601114131,1,1,1,1,1,1,9,9,9,9,9,8
611114131,1,1,1,1,1,1,9,10,10,8,9,8
621114131,1,1,1,1,1,8,9,8,9,7,8,7
631114131,1,1,1,1,1,8,9,9,9,7,8,7
641115131,1,1,1,25,1,6,5,5,5,5,4,4
651115131,1,1,1,26,6,1,5,5,5,5,4,4
661115131,1,1,28,5,4,4,4,4,4,4,3,3
671215131,1,5,7,2,10,10,10,10,3,4,1,3
681215131,1,6,7,1,10,10,10,10,3,4,2,3
691215141,1,1,1,1,1,1,9,9,9,9,9,9,8
701215141,1,1,1,1,1,1,9,10,9,10,8,9,8
711215141,1,1,1,1,1,1,9,10,10,10,8,9,8
721216141,1,1,1,1,1,8,9,9,9,9,7,8,7
731216141,1,1,1,1,21,8,7,6,6,6,5,5,4
741216141,1,1,1,30,1,6,5,5,5,5,5,4,4
751216141,1,1,1,27,6,6,6,2,5,4,5,5,5
761216141,1,4,2,9,9,9,9,9,9,3,7,3,1
771216141,1,5,7,2,10,10,10,10,10,3,4,1,3
781216141,1,6,7,1,10,10,10,10,10,3,4,2,3
791316141,1,3,5,5,11,11,11,11,6,6,6,1,1
801316151,1,1,1,1,1,8,9,9,8,9,9,7,8,7
811317151,1,1,1,1,1,1,9,10,10,10,10,8,9,8
821317151,1,1,1,1,16,14,9,6,7,5,6,4,4,6
831317151,1,1,1,1,27,5,8,7,3,6,5,5,6,6
841317151,1,1,1,1,29,3,8,7,6,6,6,5,5,4
851317151,1,1,1,1,27,8,7,6,6,6,6,5,5,4
861317151,1,7,4,1,7,23,7,4,4,2,16,3,3,3
871317151,1,5,7,2,10,10,10,10,10,10,3,4,1,3
881317151,1,6,7,1,10,10,10,10,10,10,3,4,2,3
891317151,1,3,5,5,5,11,11,11,11,11,6,6,1,1
901318151,1,3,5,5,11,11,11,11,11,6,6,6,1,1
911318161,1,1,1,1,1,1,9,10,10,10,10,10,8,9,8
921418161,1,1,1,1,1,12,12,10,10,9,7,7,8,6,5
931418161,1,1,1,1,1,16,11,10,8,7,9,7,7,6,6
941418161,1,1,1,1,36,9,7,6,6,5,6,4,5,3,2
951418161,1,1,1,1,26,8,9,7,7,6,6,6,4,6,5
961418161,1,1,1,1,35,3,8,7,6,6,6,6,5,5,4
971418161,1,1,1,1,33,8,7,6,6,6,6,6,5,5,4
981418161,1,6,7,1,10,10,10,10,10,10,10,3,4,2,3
991418161,1,3,5,5,5,5,11,16,6,11,16,6,6,1,1
1001419161,1,3,5,5,5,11,11,11,11,11,11,6,6,1,1

  • 2013-02-26追記: r = 91 の解
  • 2013-02-27追記: r = 92 の解
  • 2013-03-01追記: r = 93 の解
  • 2013-03-03追記: r = 94 の解
  • 2013-03-04追記: r = 95 の解
  • 2013-03-06追記: r = 96 の解
  • 2013-03-08追記: r = 97 の解
  • 2013-03-13追記: r = 98 の解
  • 2013-03-20追記: r = 99 の解
  • 2013-03-28追記: r = 100 の解

プログラム

#include <stdio.h>
#include <stdlib.h>
#include <setjmp.h>

#define MAX_LEN	(100)
#define	YES	(1)
#define	NO	(0)

void measure(int, int);
void solve(int, int);
void show(void);

jmp_buf jmpbuf;
int count = 0;
int len;
int part;
int mark[MAX_LEN+1];

int main(int argc, char *argv[]) {
    int n, m;

    for (n = 2; n <= MAX_LEN; n++) {
	for (m = 2; m <= n; m++) {
	    measure(n, m);
	    if (count > 0) {
		break;
	    }
	}
    }
    return 0;
}


void measure(int n, int m) {
    int i;

    count = 0;
    len = n;
    part = m;
    for (i = 0; i <= len; i++)
	mark[i] = NO;
    mark[0] = YES;
    mark[len] = YES;
    mark[1] = YES;
    if (setjmp(jmpbuf)) {
	return;
    }
    solve(len, m-2);
}

void solve(int k, int m) {
    int i;

    if (k <= 0 && m == 0) {
	count++;
	show();
	longjmp(jmpbuf, 1);
	return;
    }
    for (i = 0; i <= len-k; i++) {
	if (mark[i] && mark[i+k]) {
	    solve(k-1, m);
	    return;
	}
    }
    if (m >= 1) {
	for (i = 0; i <= len; i++) {
	    if (mark[i])
		continue;
	    if ((i-k >= 0 && mark[i-k]) || (i+k <= len && mark[i+k])) {
		mark[i] = YES;
		m--;
		solve(k-1, m);
		m++;
		mark[i] = NO;
	    }
	}
    }
    if (m >= 2) {
	for (i = 0; i <= len-k; i++) {
	    if (mark[i] || mark[i+k])
		continue;
	    mark[i] = YES;
	    mark[i+k] = YES;
	    m -= 2;
	    solve(k-1, m);
	    m += 2;
	    mark[i] = NO;
	    mark[i+k] = NO;
	}
    }
}

void show() {
    int i, j;
    char *delim;

    printf("%d(%d)", len, part);
    j = 0;
    delim = "=";
    for (i = 1; i <= len; i++) {
	if (mark[i]) {
	    printf("%s%d", delim, i-j);
	    j = i;
	    delim = "+";
	}
    }
    printf("\n");
    fflush(stdout);
}