MathLabs

第4题

给定一个由 19851985 个互不相同的正整数组成的集合 MM，其中没有一个数含有大于 2323 的素因子。证明 MM 中存在四个互不相同的元素，它们的乘积是某个整数的四次方。
第 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 个可能向量。