MathLabs

第5問

10510^5 以下の相異なる正整数を 19831983 個選び、その中のどの三つも等差数列の連続する三項にならないようにできるか。理由を示せ。
ステップ 2/4: 等差数列を排除する
2aj=ai+ak⇒ai=ak2a_j=a_i+a_k\Rightarrow a_i=a_k
詳しい解説

i<j<ki<j<k かつ 2aj=ai+ak2a_j=a_i+a_k と仮定する。各 ana_n は三進表示で数字 0,10,1 だけを持つので、33 進法では 2aj2a_j は繰り上がりなしで数字 0,20,2 だけからなる。また、各加数の数字が 0,10,1 だけなので、ai+aka_i+a_k にも繰り上がりは生じない。各桁で、2aj2a_j の数字が 00 なら両方の加数は 00、数字が 22 なら両方は 11 でなければならない。したがって ai=aka_i=a_k となり、単射性に反する。