UyHiP趣题：自然数划分中的幂关系

UyHiP上个月的题目(http://brand.site.co.il/riddles/200912q.html)：把所有大于 1 的自然数划分成两个集合，证明至少能在其中一个集合里找到互不相同的三个数 a 、 b 、 c 满足 a^b=c 。然后，试着给出一种划分，使得只有其中一个集合里存在这样的三元组。

Update: 后一个问题要求两个集合都是无限集。感谢网友 Triple.J 的提醒。

证明：如果集合 A 里只有有限个数，那就在集合 B 里选两个比集合 A 中的最大数还大的数 a 和 b ，显然 a^b 也在集合 B 里。类似的，若集合 B 里只有有限个数，我们立即可知 A 中存在满足 a^b=c 的三元组。因此，我们只需要讨论两个集合里都有无穷多个数的情况。

从集合 A 里选一个数 x ，从集合 B 里选一个数 y 。无妨假设 xy 在集合 A 中。在集合 A 中选一个比 xy 大的数 r 。由于集合 A 是无限大的，因此这样的数总存在。由于 r 比 xy 大，因此 x 、 y 、 xy 、 r 、 r^x 、 r^(xy) 这六个数两两不同。为了避免在同一集合里出现满足要求的三元组， r^x 和 r^(xy) 都必须在集合B里面，但这样的话， r^x 、 y 和 r^(xy) 就成了符合要求的三元组了。

后一个问题则出奇的简单：把所有素数放进一个集合，所有合数放进另一个集合。显然，一个素数不可能是另一个素数的整数次幂。

这个月的题目非常有意思，点击这里(http://brand.site.co.il/riddles/201001q.html)围观。