■差分基底(その6)

 目盛りのついていない長さ6の定規で,1から6まですべてはかれた理由を考えてみると,

[1]集合{1,3,6}の差分集合は{1,3−1,6−3}={1,2,3}である.

[2]t=w1・1+w2・2+w3・3,wiは0または1で,同時に0にはならない.

[3]以下の式より,1から6まですべてはかれることがわかる.

1=1,w=(1,0,0)

2=2,w=(0,1,0)

3=3,w=(0,0,1)

4=1+3,w=(1,0,1)

5=2+3,w=(0,1,1)

6=1+2+3,w=(1,1,1)

===================================

 一般に,

[Q]目盛りのついていない定規で,1からnまですべてはかれるようにするにはどうしたらいいか?

 n=41が可能な集合として,

  t={12,13,16,25,28,29,41}

がある.

===================================

 差分集合

  d={12,13−12,16−13,25−16,28−25,29−28,41−29}

={12,1,3,9,3,1,12}

={1,1,3,3,9,12,12}

 各1回まで使うことができるから

  {1,3,9,12}

の9を除き,2回使えると考えてよい.面倒くさがらずに計算すると

1=1

2=2・1

3=3

4=1+3

5=2・1+3

6=2・3

7=1+2・3

8=2・1+2・3

9=9

10=1+9

11=2・1+9

12=3+9

14=2・1+3+9

15=2・3+9

16=1+2・3+9

17=2・1+2・3+9

> ここまでは{1,1,3,3,9}で生成できた.

  17+1=12+6 30=2・12+6

  17+k=12+5+k 30+k=2・12+5+k

  29=12+17 41=2・12+17

 こうして,1から41まですべて生成することができる.

===================================