MathLabs

第1問

S={1,2,…,106}S=\{1,2,\ldots,10^6\} の 101 要素部分集合を AA とする。SS 内の数 t1,t2,…,t100t_1,t_2,\ldots,t_{100} で、Aj={x+tj∣x∈A}A_j=\{x+t_j\mid x\in A\}(j=1,2,…,100j=1,2,\ldots,100)が互いに素となるものが存在することを証明せよ。
ステップ 1/3: 交差の条件を特徴づける
ざっくり言うと

二つの移動が交わるのは、移動量の差が A の二要素の差になる場合だけである。

t=ti+b−at=t_i+b-a
詳しい解説

t−ti=a−bt-t_i=a-b と a,b∈Aa,b\in A が交わるなら、ti+b−at_i+b-a が存在して undefined、すなわち undefined となる。したがって既に選んだ移動量が禁じる値は undefined の形だけである。