录像带编号 IBM挑战2004年4月
一名电视迷用录像机录下了不计其数的电视节目。因为录像带太多了，他无暇在其上写上有意义的标记，只有用随录像带附送的数字贴来予以编号，编号由1开始。每盒录像带附送了10个数字贴，分别印上"0","1","2",…,"9"，他用了必要的数字贴后，余下的便存好以备为其它录像带编号之用。
例如为第1盒录像带编号时，他用了一个"1" 贴，其余的9个数字贴便存好。在为第10盒录像带编号时，他用了一个"1" 贴和一个"0"贴，存起8个数字贴。在为第11盒录像带编号时，他用了一个随盒的"1" 贴，及从以前存下的数字贴中取出一个"1" 贴，未用的贴则仍然存好。
现在的问题是：依这样的编号方法，到第几盒录像带时首次没有足够的数字贴供使用呢？
为免使这问题变成一条单纯的编程题，现要求考虑拓展到用B进制数字来编号的一般情况，这时随盒会有B个数字贴(对应于B进制中的数字)。请给出一般B及特殊值B=10的答案，答案请尽量是一个封闭公式(而不是一个和式或递归式)，最好附上证明。该封闭式答案只需对一般偶数B有效即可，因出题者也没有对一般奇数B有效的封闭式答案。
例如为第1盒录像带编号时，他用了一个"1" 贴，其余的9个数字贴便存好。在为第10盒录像带编号时，他用了一个"1" 贴和一个"0"贴，存起8个数字贴。在为第11盒录像带编号时，他用了一个随盒的"1" 贴，及从以前存下的数字贴中取出一个"1" 贴，未用的贴则仍然存好。
现在的问题是：依这样的编号方法，到第几盒录像带时首次没有足够的数字贴供使用呢？
为免使这问题变成一条单纯的编程题，现要求考虑拓展到用B进制数字来编号的一般情况，这时随盒会有B个数字贴(对应于B进制中的数字)。请给出一般B及特殊值B=10的答案，答案请尽量是一个封闭公式(而不是一个和式或递归式)，最好附上证明。该封闭式答案只需对一般偶数B有效即可，因出题者也没有对一般奇数B有效的封闭式答案。
- 上一篇：三个女儿的年龄分别是多少？
- 下一篇：这个不像体力活:D
回复列表
如果是十进制的话，我算的应该是199991。
我小时侯曾经看过一篇文章，它说1在自然数中出现的概率最大,为lg2,所以我就按照这个思路去想，得到着个数，不知对否。
我小时侯曾经看过一篇文章，它说1在自然数中出现的概率最大,为lg2,所以我就按照这个思路去想，得到着个数，不知对否。
下面是一些记号：
z表示B进制中最大的那个字符，比如10进制中z=9，2进制中z=1
x表示任意一个字符
f(n，x)表示在从1到n这n个数中字符x出现的个数
（稍后将证明，字符1最先被耗尽）
a^b表示a的b次方
所以问题可以表示为n<f(n,x)求解的问题
1、在任意前n个数中，字符1出现的次数总是大于等于其他字符出现的次数。
证明：把1，2，3，。。。排成一竖排，末位对齐
1
2
.
.
z
1 0
1 1
.
.
1 z
2 0
2 1
.
.
2 z
.
.
z 0
z 1
.
z z
1 0 0
1 0 1
.
.
从任意一个位置n处截断，取前n个数
看个位：是1,2,...z,0的循环，所以在任何一个地方截断，个位上1的个数总不会少于其他任何一个字符的个数
看第二位：是(1,1,1...1)，(2,2,...2),...(z,z,...z),(0,0,...0)的循环，所以从任何一个位置截断，此位上1的个数总不会少于其他任何一个字符的个数
看第三位：.....
这就证明了最先被耗尽的字符必定是1(耗尽这里指标签不够用)
2、字符1被耗尽时的数n必定是如1xxxxx (后面是m位任意字符)的形式，也就是最高位为1
证明：假设在1xxxxx(后面是m位任意字符)时字符1尚没有被耗尽，
（也就是一直到1zzzzz,1都还没有耗尽）
那么因为xxxxx<1xxxxx，所以从1到xxxxx这些数中1也没有耗尽，
即xxxxx>=f(xxxxx,1)
那么在200001到2xxxxx这xxxxx个数中，1的个数小于xxxxx，（抛开最高位不看，就很明显了）， 所以1仍然没有耗尽。因为200000中不含1，不用考虑。
所以1被耗尽时也不能是形如2xxxxx,3xxxxx,.....zxxxxx的形式
所以字符1被耗尽时的数n必定是如 1xxxxx (后面是m位任意字符）的形式
3、如果对于1xxxxx有1xxxxx<f(1xxxxx,1)，那么对于1zzzzz也有1zzzzz<f(1zzzzz,1)
证明：因为从1xxxxx往后一直到1zzzzz，每个数都至少带有一个1
下面我们就来求1zzzzz(后面是m位z),
从1到1zzzzz这些数可以分为两部分(1zzzzz=2*B^m-1)
1-zzzzz作为一部分，100000(m个0)到1zzzzz(B^m个数)作为一部分
1-zzzzz中有多少个1呢，根据排列组合，把某一位固定为1，
其他任何一位都有B种选择，所以共有B^(m-1)个1出现，
m位共有m*B^(m-1)个1，
同理10000到1zzzzz如果不看最高位也是m*B^(m-1)个1，
再加上最高位的B^m个1，所以f(1zzzzz,1)=2*m*B^(m-1)+B^m
所以也就是求满足不等式
2*B^m-1<2*m*B^(m-1)+B^m的最小的m
亦即 2*B^m<=2*m*B^(m-1)+B^m
不等式化简为m>=B/2，因为B为偶数，所以m=B/2
并且正好满足等号
这就是说从1到1zzzzz，1的个数正好比录像带的个数多1
那么从1zzzzz往前数，第一个含有两个1的数(即1zzzz1)就是要求的n
这个数就是
n=2*B^m-B+1=2*B^(B/2)-B+1
当B=2时，n=3，第三个数1,10,11时，1就不够用了
当B=10时，n=199991
z表示B进制中最大的那个字符，比如10进制中z=9，2进制中z=1
x表示任意一个字符
f(n，x)表示在从1到n这n个数中字符x出现的个数
（稍后将证明，字符1最先被耗尽）
a^b表示a的b次方
所以问题可以表示为n<f(n,x)求解的问题
1、在任意前n个数中，字符1出现的次数总是大于等于其他字符出现的次数。
证明：把1，2，3，。。。排成一竖排，末位对齐
1
2
.
.
z
1 0
1 1
.
.
1 z
2 0
2 1
.
.
2 z
.
.
z 0
z 1
.
z z
1 0 0
1 0 1
.
.
从任意一个位置n处截断，取前n个数
看个位：是1,2,...z,0的循环，所以在任何一个地方截断，个位上1的个数总不会少于其他任何一个字符的个数
看第二位：是(1,1,1...1)，(2,2,...2),...(z,z,...z),(0,0,...0)的循环，所以从任何一个位置截断，此位上1的个数总不会少于其他任何一个字符的个数
看第三位：.....
这就证明了最先被耗尽的字符必定是1(耗尽这里指标签不够用)
2、字符1被耗尽时的数n必定是如1xxxxx (后面是m位任意字符)的形式，也就是最高位为1
证明：假设在1xxxxx(后面是m位任意字符)时字符1尚没有被耗尽，
（也就是一直到1zzzzz,1都还没有耗尽）
那么因为xxxxx<1xxxxx，所以从1到xxxxx这些数中1也没有耗尽，
即xxxxx>=f(xxxxx,1)
那么在200001到2xxxxx这xxxxx个数中，1的个数小于xxxxx，（抛开最高位不看，就很明显了）， 所以1仍然没有耗尽。因为200000中不含1，不用考虑。
所以1被耗尽时也不能是形如2xxxxx,3xxxxx,.....zxxxxx的形式
所以字符1被耗尽时的数n必定是如 1xxxxx (后面是m位任意字符）的形式
3、如果对于1xxxxx有1xxxxx<f(1xxxxx,1)，那么对于1zzzzz也有1zzzzz<f(1zzzzz,1)
证明：因为从1xxxxx往后一直到1zzzzz，每个数都至少带有一个1
下面我们就来求1zzzzz(后面是m位z),
从1到1zzzzz这些数可以分为两部分(1zzzzz=2*B^m-1)
1-zzzzz作为一部分，100000(m个0)到1zzzzz(B^m个数)作为一部分
1-zzzzz中有多少个1呢，根据排列组合，把某一位固定为1，
其他任何一位都有B种选择，所以共有B^(m-1)个1出现，
m位共有m*B^(m-1)个1，
同理10000到1zzzzz如果不看最高位也是m*B^(m-1)个1，
再加上最高位的B^m个1，所以f(1zzzzz,1)=2*m*B^(m-1)+B^m
所以也就是求满足不等式
2*B^m-1<2*m*B^(m-1)+B^m的最小的m
亦即 2*B^m<=2*m*B^(m-1)+B^m
不等式化简为m>=B/2，因为B为偶数，所以m=B/2
并且正好满足等号
这就是说从1到1zzzzz，1的个数正好比录像带的个数多1
那么从1zzzzz往前数，第一个含有两个1的数(即1zzzz1)就是要求的n
这个数就是
n=2*B^m-B+1=2*B^(B/2)-B+1
当B=2时，n=3，第三个数1,10,11时，1就不够用了
当B=10时，n=199991
这个题目换一种说法就是：对于B进制数，在从1到n这n个数中，某个字符出现的个数大于n，问n最小是多少，以及这是哪一个字符。
