■数直線上の集合(その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個以上の点を配置することは不可能である)
===================================