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

                2015-09-06 13:24:25                <br />                        <br /> 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。

(转载)