Ponder This Challenge - April 2000 - Revamp the tax code

Ponder This Challenge:

We have decided to revamp the tax code in a major way. All residents will line up, left to right, with Sam standing at the far left at position 0 and the rest of us in positions 1, 2, 3, etc. On January 1 of each year, each resident will observe the net worth of the person on his left. On April 15, this resident pays that much in tax out of his own pocket. (So if Jack is at position 20 and Amanda at position 19, on April 15 Jack will pay the amount that Amanda had on January 1.)

"But what if I don't have that much money?"

Just run a deficit. Does that bother you?

"But what if my neighbor is running a deficit on January 1?"

If your neighbor was running a ten dollar deficit on January 1,
then on April 15 you give the government a ten dollar deficit.
That's the same as if the government pays you ten dollars.

Sam: "I don't have a neighbor, since I'm at position 0."

That's okay, Sam, you alone don't have to pay taxes.
Just pretend your non-existent neighbor has zero net worth.

"What if people change places, drop out, come into the system...?"

None of that is allowed. Furthermore, no money ever changes hands except for payment of taxes. Okay, no further questions.

"Wait, wait. Why are we doing a US-centric April 15 tax day, if IBM is an international company?"

I said no further questions.

Sam starts out with one dollar, and the rest of you start with
varying amounts. Some of you will start with no money, in particular
the four people on the far right-hand end of the line will be broke.
Some of you might even start with deficits.

...

Four years pass. At the end of those four years, Sam still has his
one dollar, and the only other people with nonzero net worth are
at positions q, r, s and t, with q < r < s < t. Here q,r,s,t are unknown integers, not assumed to be consecutive, and the answer to the problem will involve only the values q,r,s,t.

How much did the government collect in the first year (net)? (That is, collections minus payouts.)

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

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

Solution

• Click here to view the solution

  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

Solvers

• Joseph DeVincentis (4.4.2000 @ 4:55 PM EDT)
• Jimmy Hu (4.4.2000 @ 8:25 PM EDT)
• Dave Biggar (4.4.2000 @ 11:04 PM EDT)
• Peter Berghmans (4.5.2000 @ 5:40 PM EDT)
• Vidya Sagar (4.7.2000 @ 9:01 AM EDT)
• Amos Guler (4/10 at 2:56 PM EDT)
• David MacMahon (4/10 at 7:02 PM EDT)
• Mihai Cioc (4/12 at 2:02 PM EDT)
• Jessica Lang Jones (4/13 at 4:16 AM EDT)
• Tim Edmonds (4/17 at 5:41 AM EDT)
• Frankie Dintino (4/17 at 11:15 PM EDT)
• Tao Lin (4/18 at 11:50 PM EDT)