質問

３＾ｋ＋１個の連続した整数から、（２＾ｋ）＋２個を選らぶ。
この時、どのように（２＾ｋ）＋２個の整数を選んでも、
その中には必ず等差数列をなす三数が存在することを示しなさい。

例：ｋ＝１の時は例えば、（０、１、２、３）の中から４つの整数を
選ぶ方法は全てを選ぶ一通りしかない。０、１、２は等差数列を成す
ので、この時、命題は正しい。

ｋ＝２の時は、６つの数がとれない事が、場合分けによって分かる。
５つは、（０、１、３、４、９）とか（０、１、３、７、８）などの
方法でとれる事が分かる。

★希望★完全解答★

お便り２００５／１２／８
from=けんさん

しばらくこの問題を考えましたが、なかなか解法が見つかりませんでした。
等差数列の３項・・・2b=a+cぐらいしかわからず。。。
何で3^k+1個なのか。。。。

そこでもう少し具体的にやってみました。

まず問題にもあるようにk=2のとき
等差数列にならないように選んでいくと
０，１，３，４，９（他にもありますが）
k=3のときは
0，1，３，４，９，10，12，13，27,28・・・

ここからかなりの時間を考えました。

これらの数を「３進法」で表してみると
k=2のとき　０，１，１０，１１，１００
k=3のとき　０，１，１０，１１，１００，１０１，１１０，１１１，
　　　　　１０００，１００１・・・
これは！！できたのではないでしょうか！？

あとは証明。
3進法で０と１だけで表せる数の集合をAとして
この集合の異なる３つの要素をa,b,c　(a＜b＜c)　とする。
この3数において2b=a+c　が成り立たないことを示します（背理法）
2b=a+cが成り立つと仮定する。
まず２ｂは各位の数が０と２だけで表されることになります。
a+b　は各位繰り上がることはなく、aもcも各位０と１だけなので、
２ｂと等しくなるにはa=c以外にありえない。
（そうでないとどこかの位が１になるはず）
よって「異なる3数」という仮定に反することになる。
これで「集合Aに属する数は等差数列をなさない」と言えると思います。

（０から）３＾ｋ＋１の連続した数を３進法で表したとき
等差数列をなさない数、即ち各位０か１のみで表せるのは（２＾ｋ）＋１個が限界。

ちょっと無理があるかと思いますが、どうでしょう。
「３進法」は当たってるように思うのですが。
ご参考になれば幸いです。

お便り２００５／１２／１２
from=ＴＫ

けんさん、返答ありがとうございます。
僕も、それは考えたのですが、三進法で１と０のみを用いてあらわせる数の
集合が、最も多くの項を含む集合となることの証明が出来ません。
もちろん、集合Aに何か一つ新しい要素を加えると等差数列ができてしまう
ことは容易に示せるのですが。
どうでしょうか？

お便り２００６／８／１６
from=たなか

（１）
質問者の
「ｋ＝２の時は、６つの数がとれない事が、場合分けによって分かる。」というのが
気になります。
そもそも、問題が誤っているということでは、ありませんか？
そうすると、証明できませんよね。

（２）
「ｋ＝２の時は、『６つの数がとれない』事が、場合分けによって分かる。」とあり
ますが、６つの数を取ったとき、３つの等差数列がある、ということですよ。
　また、「５つは、（０、１、３、４、９）とか（０、１、３、７、８）などの
方法でとれる事が分かる。」。とありますが、このなかに等差数列の３つの数は、
ありませんよ

（３）
１０個のうち６つの数を、（０、１、３、７、９、１０）と選ぶと、等差数列をなす
３つの数は、ありません。
やはり、設問自身が、誤っているのです。

お便り２００６／８／１７
from=UnderBird

たなかさんへ
　私もこの問題に以前取り組み、できそうでできず、未だすっきりしていません。
はじめ説明の意味もよくわからず悩んだこともありました。
さて、(2)でどの3数も等差数列でないという文は、10個の数から6つ取り出すと
そのうちの3数が等差を成すということに対して、5つまではどの3数も等差数列と
ならない数を選べるが、（6つ目は無理だ）という意味の文と理解しました。
また、(3)については10個の数から6個選ぶので0から10を使うと11個用いているので
条件を満たしていません。
3進数のアイデアや同じかもしれませんがmod 3で考える方法をやってみましたが
うまくいきません。
背理法かもしれませんし、皆さんでこの問題は考えていきたいですね。

お便り２００６／８／１７
from=たなか

　解答を誤りました。再度、再質問に戻してください。

お便り２００７／１０／２２
from=cqzypx

k=3に反例があります：(0 1 4 6 10 15 17 18 22 23)。