emlx 的 find n 解答

Find the mininum integer n which satisfies the following property.
1) In a set including n positive but less than 1000 integers, there exists a pair of
numbers, a>b, such that every digit of a >= the corresponding digit of b.
For deion reason, you could write 89 as 089. For example:
a= 234, b=132 are ok, but a=234, b=5 is not.

应该是 a set including n positive integers。

小草MM问为什么是76，我只有一个不太满意的证明。

设有有一个集S，使得这样两个数a,b不存在，我们证明|S|<=75。设H(i)为S中百位为i的数，T(i)为S中十位为i的数。首先证明H(0)+T(9)<=11：设H(0)=i，则H(0)中有一个数各位数字分别小于等于09(10-i)。这时T(9)中最多只能有11-i个数（包括09(10-i)）。类似的可以证明

H(0)+T(9)<=11
H(1)+T(8)<=13
H(2)+T(7)<=15
H(3)+T(6)<=17
H(4)+T(5)<=19
H(5)+T(4)<=19
H(6)+T(3)<=17
H(7)+T(2)<=15
H(8)+T(1)<=13
H(9)+T(0)<=11

两边加起来就有2*|S|<=150

另一半是做一个有75个数的集：只要取所有三个位数加起来为14的数就行了。

所有跟帖： 

• Excellent! MM. -emlx- ♂ (0 bytes) () 12/22/2006 postreply 09:08:47

• DING -haha2000- ♂ (0 bytes) () 12/22/2006 postreply 09:42:55

• 应该是 a set including n positive integers, all less than 1000 -康MM- ♀ (0 bytes) () 12/22/2006 postreply 09:48:06

• 我说偶咋也看不懂捏。。呵呵 ：） -idiot94- ♂ (0 bytes) () 12/22/2006 postreply 09:49:16

• 不好意思, 是有些业余. -emlx- ♂ (58 bytes) () 12/22/2006 postreply 09:52:13

• 兄弟，别这么说，偶也不专业啊！：） -idiot94- ♂ (0 bytes) () 12/22/2006 postreply 09:53:04

• 师傅太厉害了，徒儿还没看明白 =( 等俺慢慢研究。。。 =) -露上草- ♀ (0 bytes) () 12/22/2006 postreply 13:22:33

• 这都不懂,看来你得降倍份了. 不是土而了. -emlx- ♂ (0 bytes) () 12/22/2006 postreply 13:46:32

• 555, 你是谁啊？@:@ -露上草- ♀ (0 bytes) () 12/22/2006 postreply 13:50:54

• 其实我更不懂， -emlx- ♂ (0 bytes) () 12/22/2006 postreply 18:41:46

• 此题答案不定，没有说这1000正整数是不同的。 -3271963- ♀ (0 bytes) () 12/22/2006 postreply 14:13:56