第1問

S=\{1,2,\ldots,10^6\}

の 101 要素部分集合を

A

とする。

S

内の数

t_1,t_2,\ldots,t_{100}

で、

A_j=\{x+t_j\mid x\in A\}

（

j=1,2,\ldots,100

）が互いに素となるものが存在することを証明せよ。

ステップ 2/3: 禁制候補を数える

ざっくり言うと

極大族なら、すべての候補は既存の移動か差によって禁じられる。

10^6\le |T|(101\cdot100+1)

詳しい解説

を互いに素な移動量の極大集合とする。の各候補はに属するか、あるいは（、相異なる）の形である。したがって。 $S$ $T$ $T$ $a,b\in A$ $t_i+b-a$ $t_i\in T$