问一个数学竞赛题-我不会做

test · 发表于 2005-5-19 01:14:19

x是3位数的正整数。这里把x表示成abc. 令 f(x) = max(a,b,c) - min(a, b, c).

例如，f(125)=f(251)=f(152)=4, f(101)=f(110)=1.

求 f(100) + f(101) + .... + f(998) + f(999)

我不会写求和号。也就是说求 f(x) 从100到999的和。

乱弹 · 发表于 2005-5-19 05:23:27

f(abc)=(|a-b|+|b-c|+|c-a|)/2

test · 发表于 2005-5-19 17:43:12

谢谢乱弹，果然这里能人不少。我觉得最难得是求和。要是有人给个方法更好。我是这样想的：

For 100<=x<=999, if I can find all f(x) = k, I will be able to get the sum

I think I should find the following

A. number of 3 digit integers using digits 0, 1, 2, ...., k, where digit 0 and k must be used. Call it N0(k)

B. number of 3 digit integers using digits 1, 2, 3, ...., k-1, where digit 1 and k-1 must be used, if (k>1). Call it N1(k)

...

C. number of 3 digit integers using digits 9-k, 9-k+1, 9-k+2, ...., 9, where digit 9-k and 9 must be used, if (k!=9). This should be the same as N1(k)

For example, N0(1) = 3 (100, 110, 101), N1(1)=6 (121, 122, 112, 212, 211, 221)

then the solution is sum of k(N0(k)+(9-k)N1(k)) for k=0 to 9.

My question:

0. Is this analyse correct?

1. Is there a better way to do this?

2. The above A, B, C are all permutation problems, is there a general terms to get the solutions for N0(k) and N1(k) for k=0, 1, ..., 9? I tried, I couldn't get a good formula

My analyses may be wrong above. You are welcomed to point it out.

test · 发表于 2005-5-19 21:45:18

I made a mistake here

I wrote

B. number of 3 digit integers using digits 1, 2, 3, ...., k-1, where digit 1 and k-1 must be used, if (k>1). Call it N1(k)

This should be

B. number of 3 digit integers using digits 1, 2, 3, ...., k+1, where digit 1 and k+1 must be used, if (k<9). Call it N1(k)

I am still waitin....

乱弹 · 发表于 2005-5-20 01:44:58

Sorry, actually I did not try this problem carefully. I just guessed that the formula I wrote might be a point. With that, we remove the max and min operators and transform the problem into a combinatorial problem.

test · 发表于 2005-5-20 19:38:33

I thought this last night. I think we can solve it this way.

sum{x=100 to 999}f(x) =

= sum{a=1 to 9} sum {b=0 to 9} sum {c=0 to 9} (|a-b|+|b-c|+|c-a|)/2

This can break into 3 terms, for one term

sum{a=1 to 9} sum {b=0 to 9} sum {c=0 to 9} |a-b|/2

= 10 sum{a=1 to 9} sum {b=0 to 9} |a-b|/2

= 5 sum{a=1 to 9} (sum {b=0 to a}(a-b) + sum {b=a+1 to 9}(b-a))

= 5 sum{a=1 to 9} (a(a+1)/2 + (9-a)(10-a)/2)

= 5 sum{a=1 to 9} (a**2 - 18a +90)

We can do the same for the other 2 terms. With this, we don't care about permutations. Thanks again.

		自动登录	找回密码
密码			立即注册

动态微博

问一个数学竞赛题-我不会做

回复：问一个数学竞赛题-我不会做

回复：回复：问一个数学竞赛题-我不会做

Make a correction

回复：回复：回复：问一个数学竞赛题-我不会做

Thanks