MathLabs

第4题

给定一个由 19851985 个互不相同的正整数组成的集合 MM,其中没有一个数含有大于 2323 的素因子。证明 MM 中存在四个互不相同的元素,它们的乘积是某个整数的四次方。
第 2/4 步:配对相同向量得到平方数
通俗地说

第一次抽屉原理把奇偶标签相同的数配成对;每次碰撞恰好产生一个平方数乘积。

xy is a square whenever x,y have the same parity vectorxy\text{ is a square whenever }x,y\text{ have the same parity vector}
详细分析

两个数有相同奇偶向量时,相乘后每个素因子的指数都为偶数,所以乘积是平方数。由于 1985>3⋅29+11985>3\cdot2^9+1,反复使用抽屉原理可得到至少 29+12^9+1 个互不相交数对 {xj,yj}\{x_j,y_j\},满足 xjyj=sj2x_jy_j=s_j^2。数量阈值足够,因为 2(29+1)<3⋅29+12(2^9+1)<3\cdot2^9+1。