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: ponder@il.ibm.com