1とnの間の自然数列で、そのうちのどの３つも等差数列にならないものを考える。

[Q]n=9のとき、この自然数列の長さはどのくらい大きくすることができるだろうか？

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

[A]1,2,4,8,9の5つ。

もし5を入れるなら4または6は省かなければならない

もし5を入れるなら3または7は省かなければならない

もし5を入れるなら2または8は省かなければならない

もし5を入れるなら1または9は省かなければならない→5を入れることはできない

→1,2,3のうちひとつ、7,8,9のうちひとつを省かなければならない→５を除くなら4と6を入れなければならない→しかし、このとき2と８を省かなければならない

→1,4,7のうちひとつを省かなければならない

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

1999年、ブルガンはサイズがCn(loglogn/logn)^1/2の集合はかならず等差数列を含むことを証明した。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝