你在这里

UyHiP 趣题:几乎所有数都能分解成若干个 3x · 4y 之和

下面这个题目来自 2015 年 7 月的 Using your Head is Permitted 。假设集合 S 是由所有形如 3x · 4y 的数构成的,其中 x 和 y 都是非负整数。因而,集合 S 是一个无穷集合,其中最小的几个元素依次为 1, 3, 4, 9, 12, 16, 27, … 。如果某个正整数 n 能表示成集合 S 中的一个或多个不重复的数之和,我们就说 n 是集合 S 的一个子集和。例如, 23 就是 S 的一个子集和,因为 23 可以表示成 3 + 4 + 16 。然而, 6 就不是 S 的一个子集和。
求证:除了有限多个正整数以外,其他所有的正整数都是集合 S 的子集和。

 
 
 
 
 
 
 
 
 
首先我们证明,如果 n 是一个大于 9 的正整数,那么在集合 S 中一定存在一个小于 n 但大于 n / 2 的元素。不妨假设集合 S 中不小于 n 的最小元素是 t = 3a · 4b 。如果 b > 0 的话,那么 3a + 1 · 4b – 1 = (3 / 4) · t > t / 2 ≥ n / 2 就是一个满足要求的数;如果 b = 0 的话,考虑到 t ≥ n > 9 ,因此 a 肯定至少是 3 ,于是 3a – 3 · 4b + 2 = (16 / 27) · t > t / 2 ≥ n / 2 就是一个满足要求的数。
这说明,我们可以从任意一个大于 9 的正整数 n 里减去 S 中的某个介于 n 和 n / 2 的数,所得结果将会小于 n / 2 ;这个过程可以不断地继续下去,每次减去的数都不重复。最后,我们会得到某个小于等于 9 的数。由于 1 、 3 、 4 也都在 S 里(并且这三个数刚才没使用过),因而容易验证,任意一个小于等于 9 的数都可以继续被减到 0 或者 1 。
现在,把集合 S 里的所有数全都乘以 4 ,不妨把由此得到的新的集合记作 4S 。显然,集合 4S 里的数一定都在集合 S 里,并且根据刚才的结论,我们可以从任意一个形如 4n 的正整数出发,不断减去 4S 里的数,使得最后只剩下 0 或者 4 。由于 1 和 3 都不在 4S 里,因此这两个数刚才都没有用过。因而,如果最后剩下了一个 4 ,我们再从中减去 1 和 3 ,就能让它变成 0 了。这说明,一切形如 4n 的正整数都是集合 S 的子集和。
对于形如 4n + 1 的数,我们可以先在它的基础上减去 9 ;对于形如 4n + 2 的数,我们可以先在它的基础上减去 9 和 81 ;对于形如 4n + 3 的数,我们可以先在它的基础上减去 27 。这样一来,这些数也都变成 4 的整倍数了。我们就能像刚才那样,把它们拆成 S 中的元素之和,并且在此过程中不会再用到 9 、 81、 27 等数。这就证明了,所有大于等于 9 + 81 = 90 的正整数都是集合 S 的子集和。
利用计算机不难验证,不能成为子集和的数事实上只有五个,它们是 2 、 6 、 11 、 18 、 54 。