MathLabs

第4問

19851985 個の相異なる正整数からなる集合 MM があり、そのどの数も 2323 より大きい素因子を持たないとする。MM には、積がある整数の 4 乗となる相異なる四元が存在することを証明せよ。
ステップ 1/4: 各数を九つの素因子指数で符号化する
前のステップ次のステップ
ざっくり言うと

素因子指数の正確な大きさを忘れ、偶か奇かだけを残す。すると各整数は512個の偶奇の箱の一つに入る。

2,3,5,7,11,13,17,19,23(9 primes)2,3,5,7,11,13,17,19,23\quad(9\text{ primes})
詳しい解説

各 x∈Mx\in M は一意的に x=2a13a25a37a411a513a617a719a823a9x=2^{a_1}3^{a_2}5^{a_3}7^{a_4}11^{a_5}13^{a_6}17^{a_7}19^{a_8}23^{a_9} と書ける。指数の偶奇ベクトル (a1,…,a9)(mod2)(a_1,\dots,a_9)\pmod2 だけを記録する。可能なベクトルは 29=5122^9=512 個である。