对正整数
n,记
In={1,2,⋯,n},
Pn={km∣m∈In,k∈In}.
(1) 求集合
P7 中元素的个数;
(2) 若
Pn 的子集
A 中任意两个元素之和不是整数的平方,则称
A 为“稀疏集”,求
n 的最大值,使
Pn 能分成两个不相交的稀疏集的并.
\begin{solution}
\begin{enumerate}
\item 将
k 写成
k=sr2,其中
s 为平方因子已经除尽后的平方自由数. 对
n=7,当
s=1 时
k=1,
4,所得不同的有理数为
{1,2,3,4,5,6,7}∪{21,23,25,27}
共有
11 个. 其余平方自由数为
2,
3,
5,
6,
7,每个数只能取
r=1,分别产生
7 个形如
sm 的数;不同的平方自由数对应的数不可能相等. 因此
∣P7∣=11+5×7=46
\item 每个
Pn 中的元素都可以唯一写成
qs,其中
q 是正有理数,
s 是平方自由正整数. 若
s>1,则该元素是无理数. 若两个元素的平方自由部分相同且大于
1,它们的和为正有理数倍的
s,仍是无理数. 若两个元素的平方自由部分分别为不同的
s,
t>1,假设它们的和为有理数
u,则
qs+rt=u. 移项并平方可得
2uqs=u2+q2s−r2t,从而
s 为有理数,矛盾. 若其中一个平方自由部分为
1,另一个大于
1,则和为有理数会使后者的
s 为有理数,同样矛盾. 因此,含有非有理数的两个不同元素之和不可能是整数,稀疏集划分的限制只来自
Pn 中的有理数.
先考察
P14. 其中有理数恰来自
k=1,
4,
9,约分后得到的有理数集合为
R14={1,2,…,14}∪{21,23,25,27,29,211,213}∪{31,32,34,35,37,38,310,311,313,314}
将其分为
A0={1,2,4,6,9,11,13}∪{21,23,29,211,213}∪{31,34,35,310,313},
和
B0={3,5,7,8,10,12,14}∪{25,27}∪{32,37,38,311,314}
把
P14 中除
R14 外的所有无理数任意放入第一组,便得到
A={x∈P14∣x∈/R14}∪A0,
B=B0.
为验证这两个集合确实稀疏,只需检查
R14 中两数之和为整数平方的情形. 由于两数之和不超过
28,只需检查平方
1,
4,
9,
16,
25. 和为
1 的相邻对只有
31+32;和为
4 的相邻对为
31+311、
21+27、
32+310、
1+3、
34+38、
23+25、
35+37;和为
9 的相邻对为
1+8、
2+7、
3+6、
4+5、
25+213、
27+211、
313+314;和为
16 的相邻对为
2+14、
3+13、
4+12、
5+11、
6+10、
7+9;和为
25 的相邻对为
11+14、
12+13. 这些相邻对均分别落在
A0 与
B0 中,所以
A、
B 都是稀疏集. 由此
n=14 可以实现.
另一方面,当
n⩾15 时,
Pn 中包含
1,
3,
6,
10,
15,且
1+3=4,
3+6=9,
6+10=16,
10+15=25,
15+1=16.
因此这五个元素构成一个长度为
5 的奇环. 若把
Pn 分成两个稀疏集,奇环上的相邻元素必须交替分入两个集合,绕环一周后首尾两个元素却会被迫分入同一集合,矛盾. 所以
n⩾15 时不能实现,故
n 的最大值为
14.
\end{enumerate}
\end{solution}