April 2000
In the first year the government collects a net of qrst/24.
In subsequent years it collects a net of 0.
In general, if after n years the only nonzero amounts were
at the n+1 positions 0, b1, b2, ..., bn, then the government's
net take during the first year is b1*b2*...*bn/n!.
Consider the polynomial f(x) whose coefficient f[i] of x^i is the
original net worth of the resident at position i;
here and throughout, "x^i" denotes exponentiation.
Each year the effect of the taxation is to multiply f(x) by (1-x), since the new value of the coefficient f[i] is the old value
of f[i] - f[i-1]. After four years, the new polynomial is
g(x)=f(x)*(1-x)^4. We are told that g(x) has only five nonzero
coefficients, including g[0]=1.
Let the nonzero coefficients be g[q]=b, g[r]=c, g[s]=d, g[t]=e.
Because g(x) is divisible by (1-x)^4, we know that g and its first
three derivatives all vanish at x=1: g(1)=g'(1)=g''(1)=g'''(1)=0.
The fourth derivative of g at 1 is equal to 24 times f(1),
and in turn f(1) is the sum of the coefficients of f,
that is, the total initial wealth of the residents.
After one year, the total wealth of the residents is
(f(x)*(1-x)) evaluated at x=1, that is, 0. The government essentially collects all the wealth in the first year.
So we have the linear equations (in b,c,d,e):
1 + b + c + d + e = 0
qb + rc + sd + te = 0
q(q-1)b + r(r-1)c + s(s-1)d + t(t-1)e = 0
q(q-1)(q-2)b + r(r-1)(r-2)c + s(s-1)(s-2)d + t(t-1)(t-2)e = 0
q(q-1)(q-2)(q-3)b + ... + t(t-1)(t-2)(t-3)e = 24*f(1).
Or, after subtracting constant multiples of some equations from
others, we get the simpler set of equations:
1 + 1*b + 1*c + 1*d + 1*e = 0
0 + q*b + r*c + s*d + t*e = 0
0 + q^2*b + r^2*c + s^2*d + t^2*e = 0
0 + q^3*b + r^3*c + s^3*d + t^3*e = 0
0 + q^4*b + r^4*c + s^4*d + t^4*e = 24*f(1).
The coefficients on the left-hand form a matrix M.
Applying M^(-1) to the vector (0,0,0,0,24*f(1))
we will recover 1 as well as the unknowns b,c,d,e.
We are interested in the upper right-hand entry of M^(-1)
(that is, its (1,5) entry).
By Cramer's rule, this is given by the ratio of two determinants:
in the numerator, the determinant of the upper right-hand 4x4
submatrix of M (up to sign),
| 1 | 1 | 1 | 1 |
| q | r | s | t |
| q^2 | r^2 | s^2 | t^2 |
| q^3 | r^3 | s^3 | t^3 |
and in the denominator, the determinant of M itself,
which is the same as the determinant of its lower right-hand 4x4
submatrix:
| q | r | s | t |
| q^2 | r^2 | s^2 | t^2 |
| q^3 | r^3 | s^3 | t^3 |
| q^4 | r^4 | s^4 | t^4 |
The latter differs from the former in that the first column has been multiplied by q, the second by r, and so on.
Putting it all together, we find
1 = (1/(q*r*s*t))(24*f(1)), or
f(1) = q*r*s*t/24 = the government's first-year profit.
Adapted from the 1986 Putnam Examination, problem A-6.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com