■数直線上の集合(その13)

 (その12)を具体的に書いてみる.

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

[1]第1の点を,線分を1/1に分けた区間にはいるように打つ.=長さ1の線分のどこかにひとつ点を打つ.

[2]第2の点を,線分を1/2に分けた区間に2つの点がそれぞれはいるように打つ.すなわち,もう一つの点を,最初の点も含めて2つの点がそれぞれ自分の側の1/2の区間にはいるように点を打つことは簡単である.

[3]第3の点を,線分を1/3に分けた区間に3つの点がそれぞれはいるように打つ.これができるためにはすでに打ってある2つの点が線分の中央の1/3の区間にはいっていてはいけない.

[4]第4の点を,線分を1/4に分けた区間に4つの点がそれぞれはいるように打つ.

 このようなことを続けていくことができるだろうか? これに対する答えが,バーレカンプ・グラハムの定理(1970年)である.

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

[Q]任意のkに対し,a1,a2,・・・,akがそれぞれ異なった区間

  [(i−1)/k,i/k],i≦k

にあるという性質を満たすn個の整数a1,a2,・・・,an(0<a1<a2<・・・<an<1)が取れる最大のnは?

[A]17個(18個以上の点を配置することは不可能である)

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