■差分基底(その21)
[Q]目盛りのついていない長さLの定規に(両端以外に)目盛りをm−2個刻んで,長さ1からLまですべてはかれるようにするにはどうすればいいか?
では,長さを測る2つの目盛りの選び方が,m(m−1)/2あることから
L≦m(m−1)/2
===================================
[Q]目盛りのついていない長さ36の定規に(両端以外に)目盛りを8つ刻んで,長さ1から36まですべてはかれるようにするにはどうすればいいか?
[A]目盛り間隔の配置を{1,2,3,7,7,7,4,4,1},目盛りを{0,1,3,6,13,20,27,31,35,36}とする.
===================================
定規の場合に限らず,1からLまですべてはかれるようにするための必要条件はどうなっているのだろうか?
たとえば,1から6まですべてはかれる場合を考える.集合{1,3,6}の差分集合は{1,3−1,6−3}={1,2,3}である.
4=1+3
5=2+3
6=1+2+3
だから,1から6まですべてはかれるのである.
===================================