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

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

下面这个题目来自 2015 年 7 月的 Using your Head is Permitted 。假设集合 S 是由所有形如 3^x · 4^y 的数构成的，其中 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 = 3^a · 4^b 。如果 b > 0 的话，那么 3^{a + 1} · 4^{b – 1} = (3 / 4) · t > t / 2 ≥ n / 2 就是一个满足要求的数；如果 b = 0 的话，考虑到 t ≥ n > 9 ，因此 a 肯定至少是 3 ，于是 3^{a – 3} · 4^{b + 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 。