## November 2004

<<October
**November**
December>>

**ANSWER:**

**Part 1:**

37359000

**Part 2:**

Let T_n be the sum of the remaining numbers on the worm-eaten paper; T_0 is defined to be 0.

d denotes a digit which may be any one of "0","1","2","3",...,"a".

e denotes a digit which may be any one of "0","1",...,"x-1".

f denotes a digit which may be any one of "x","x+1",...,"a".

[ffff] denotes a 4-digit number all of whose digits belong to

{"x","x+1",...,"a"}, etc.

c is the mean value of x,...,a, so that c = (b+x-1)/2.

S_n be the sum of all the n-digit numbers of the form [fff...f].

It is not difficult to see that S_n = (b-x)^n*c*(b^n-1)/(b-1).

S_0 is defined to be 0.

We write y=b-x to simplify the expression.

Thus S_n = y^n*c*(b^n-1)/(b-1).

We divide the n-digit numbers into n+1 classes according to the position of the leading e digit.

Class C_1: [edd...dd]

Class C_2: [fed...dd]

Class C_3: [ffe...dd]

...

Class C_(n-1): [fff...ed]

Class C_n: [fff...fe]

Class C_(n+1): [fff...ff]

There are y^(i-1)*x*b^(n-i) different numbers in Class C_i for i in

{1,...,n}. C_(n+1) has y^n different numbers.

After worm-eating, all the e digits are gone. The sum of numbers in C_i appearing on the worm-eaten paper is

x*b^(n-i)*S_(i-1) + y^(i-1)*x*T_(n-i)

for i in {1,...,n}.

The sum of numbers in C_(n+1) appearing on the worm-eaten paper is S_n.

Thus T_n = S_n + sum{i,1,n}{x*b^(n-i)*S_(i-1)} + sum{i,1,n}{y^(i-1)*x*T_(n-i)}

Let U_n = S_n + sum{i,1,n}{x*b^(n-i)*S_(i-1)} for n>0 and define U_0 = 0.

We have U_(n+1)-b*U_n = S_(n+1)+x*S_n-b*S_n = S_(n+1)-y*S_n

S_(n+1)-y*S_n

= y^(n+1)*c*(b^(n+1)-1)/(b-1) - y^(n+1)*c*(b^n-1)/(b-1)

= y^(n+1)*c*b^n

From the basic knowledge about difference equation,

U_n = c*b^(n-1)*(y^(n+1)-y)/(y-1).

Similarly

T_n = U_n + sum{i,1,n}{y^(i-1)*x*T_(n-i)}

= U_n + sum{i,0,n-1}{y^(n-1-i)*x*T_i}

T_(n+1)-y*T_n = U_(n+1)+x*T_n-y*U_n

T_(n+1)-b*T_n = U_(n+1)-y*U_n

Substitute U_n into this difference equation, we have

T_n = b^n*(G*y^n + H*n + K)

where G = c*(b-1)*y^2/(b*(y-1))^2, and the other two coefficients H and K are to be determined by T_0=0 and T_1=S_1=c*y.

To be explicit, T_n = b^n*(G*y^n + ((c*y/b)-(y-1)G)*n - G)

*If you have any problems you think we might enjoy, please send them in. All replies should be sent to:* webmster@us.ibm.com