Table of Contents
题目
在1到30之间，最多能选出多少个数，使得任意两个数的乘积都不是完全平方数？
如果改成下面两个条件，答案又分别是多少？
- 任何一个数都不能整除另一个数。
- 任意两个数都没有大于1的公因子。
分析
这三问可以用同一个套路来做：把1到30尽量分成若干组，使得同一组里的任意两个数都不可能同时被选入所求子集。这样每组至多只能取一个数，所以这就给出了一个上界。接着，如果我们又能构造出一个合法子集，恰好从每组取出一个数，那么这个上界就能达到，于是最大值也就确定了。
没有两个数的乘积是完全平方数
每个数都可以写成\(n=sa^2\)，其中\(s\)是平方自由数，也就是把\(n\)里所有偶数次幂的质因子都去掉后剩下的“平方自由部分”。比如：\(27=3*3^2\)。
若两个数分别是\(s_1a^2\)和\(s_2b^2\)，那么它们的乘积是完全平方数，当且仅当\(s_1=s_2\)。
所以，可以按平方自由部分把1到30分组；同一组里的数，两两乘积都是完全平方数，因此每组至多只能选一个数。
反过来，任取所有不超过30的平方自由数本身，就一定满足条件，因此最大个数就是不超过30的平方自由数个数。
在1到30中，不是平方自由数的只有4的倍数、9的倍数、25的倍数：
\[ \left\lfloor\frac{30}{4}\right\rfloor+ \left\lfloor\frac{30}{9}\right\rfloor+ \left\lfloor\frac{30}{25}\right\rfloor =7+3+1=11\]
所以平方自由数共有\(30-11=19\)个。
例如可以取：\(\{1,2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30\}\)。
因此第一问答案是\(19\)。
没有一个数整除另一个数
把1到30中的每个数唯一地写成“奇数\(\times2\)的幂”的形式。于是它们被分成15条链：
\[ 1,2,4,8,16; \quad 3,6,12,24; \quad 5,10,20; \quad \dots \quad ; 29\]
每条链中的任意两个数都存在整除关系，所以每条链至多选一个数。而这样的链一共有15条，因为1到30之间恰好有15个奇数。 所以最多只能选15个数。
这个上界可以达到，例如直接取\(\{16,17,18,\dots,30\}\)一共15个数。因为其中最小的是16，而\(2\times16=32>30\)，所以其中任何一个数都不可能是另一个数的倍数。
因此第二问答案是\(15\)。
任意两个数都没有大于1的公因子
这就是说所选的数两两互素。
把2到30按“最小质因子”分组。于是得到10组，对应于10个不超过30的质数：\(2,3,5,7,11,13,17,19,23,29\)。
例如：
- \(\{2,4,6,8,10,12,14,16,18,20,22,24,26,28,30\}\)。这一组里的数最小质因子都是2；
- \(\{3,9,15,21,27\}\)。这一组里的数最小质因子都是3；
- \(\{5,25\}\)。这一组里的数最小质因子都是5；
- 其余还有单独的组\(\{7\},\{11\},\{13\},\{17\},\{19\},\{23\},\{29\}\)。
同一组里的任意两个数都含有这个公共最小质因子，所以不可能同时被选中。因此在2到30里，每组至多只能选一个数。
一共有10组，因此大于1的数最多只能选10个。再把1也选进去，因为1和任何数都互素，所以总数最多为\(10+1=11\)。这个上界同样可以达到，例如从每组各取一个质数，再加上1：\(\{1,2,3,5,7,11,13,17,19,23,29\}\)。
因此第三问答案是\(11\)。
最终答案： 三问分别是\(19\)、\(15\)、\(11\)。