题目:
有一个十位的十进制数字. 它的从左往右数第第一位代表这个数字有几个1.第二位代表这个数字有几个2. 以此类推.第9位代表这个数字有几个9. 第10位代表这个数字有几个0.
问这个数字是几. 答案是:2100010006
那么,这个数字是如何被找到的?如何证明这是唯一的答案呢?
下面是我的解答.
解法1：
假设这个数字从左到右每一位分别是: a_1,a_2,a_3,a_4, ..., a_9, a_0. 即 a_i 代表有几个i.
那么显然有 a_1 + a_2 + a_3 + ... + a_9 +a_0 = 10 ,
且 a_1 +2*a_2 + ... 9*a_9 = 10
且 a_i >= 0 (i= 0,...9)
如以上面的例子:a_1=2, a_2=1, a_6=1, a_0=6. 2+1+1+6=10. 2*1 + 1*2 +1*6 = 10
显然, 最后一位a_0不可能是0. 因为它代表这个数字有0个0, 这与最后一位是0矛盾.
那么, 我们先从这个角度考虑: 把10写成几个自然数的和,有哪些可能性?
比如:
10 = 9+1
10 = 8+2
10 = 8+1+1
10 = 7+3
...
10 = 4+3+2+1
...
下面我要证明: a_1到a_9这9个数字中至少有6个是0. 即, a_0 >=6.
我们可以用反证法. 假如不是这样. 比如,假设a_0<=4, 那么a_1,a_2, ..., a_9 这9个数字当中就至少有5个非0的数字. 它们是不可能满足a_1 +2*a_2 + ... 9*a_9 = 10这个条件的.因为5个不同的个位数(大于等于1且小于等于9)相加必定大于10 . 4个数是有可能的,比如1+2+3+4=10. 但是呢,这样就意味着有5个0, 那么a_0=5.那么a_1 + a_2 + a_3 + ... + a_9 +a_0 = 15. 所以a_0 = 5也不行. 所以a_0 >=6.
由a_0 >=6以及a_1 + a_2 + a_3 + ... + a_9 +a_0 = 10可得 a_1 + a_2 + a_3 + ... + a_9 <= 4 . 几个正整数加起来小于等于4, 那么只有很少几种可能性:
1 (即 a_1, a_2,..., a_9之中只有一个数字是1, 其他都是0)
1+1 (即 a_1, a_2,..., a_9之中只有两个个数字是1, 其他都是0)
1+2 (即 a_1, a_2,..., a_9之中只有一个1和一个2, 其他都是0)
1+1+2 (即 a_1, a_2,..., a_9之中只有两个1和一个2, 其他都是0)
2+2 (即 a_1, a_2,..., a_9之中只有两个2, 其他都是0)
一共对应5个不同的数字. 于是很快可以验证出只有1+1+2可以满足条件.即a_1=2, a_2=1.
解法2：暴力枚举
组合数学有个经典问题叫partition int：给定一个自然数n，把它分解成几个比n更小的自然数的和，比如5=3+1+1。
假如n等于10，这个问题最多只有42个解。也就是说，原问题的解只能是这42个解中的一个。
把这42个解拿来挨个count一遍就行了。
--
修改:snnn FROM 61.172.164.*
FROM 61.172.164.*