Good Math Problems

The Supreme Court, Linear and Exponential Growth, and Racial Segregation

I just started reading Closed Chambers: The Rise, Fall, and Future of the Modern Supreme Court — and I came to an interesting case which could turn into a good problem dealing with exponential math.

A paraphrasing of the case

The case, originating in 1980, was filed by the U.S. Department of Justice and joined by the NAACP against the city of Yonkers, New York. The charge: violating the 1968 Fair Housing Act by purposely placing public housing in such a way as to perpetutation residential segregation. Finally, in 1985, the federal district court judge ruled in favor of the Department of Justice. However, with the ruling needed to come some sort of remedy — how could this wrong be righted?

The judge, Leonard Sand, ordered the city of Yonkers to build 200 public housing units spread throughout Yonkers, and to plan for subsidized housing in previously segregated neighborhoods. The city initially balked, but in January 1988, the city council formally agreed to the order. However, two weeks later, four of seven members of the city council decided to go back on their agreement, in defiance of the court.

Here’s where it gets interesting.

“Judge Sand first cajoled, then demanded, and finally threatened the city and its recalcitrant officials with contempt of course. As a last resort, Sand ruled that if the council did not adopt the necessary legislation by August 1, he would fine the city $100 a day, doubling every day until the legislation passed… In addition, he would fine each council member voting against the legislation $500 a day, with the possibility of incarceration after Day 10″ (page 40-41).

It wasn’t clear to me whether the fines would be cumulative or not (so if the fine after day 2 would be $200 or $200+$100), but from this New York Times article and others, I can say with a high degree of certainty that it was cumulative!

The fines were to start on August 2nd. However, they were suspended from August 9th to September 2th, while the case was waiting to be being heard by the appeals court and the supreme court.

The appeals court ruled that the exponentially increasing fine was excessive and unconstitutional. The ruling reads:

The City contends that the amount of the coercive fines imposed as a remedial sanction for civil contempt is excessive and a violation of the Due Process Clause of the Fifth Amendment and the Excessive Fines Clause of the Eighth Amendment. The fines start at $100 a day and double each day of continued noncompliance. As a result of doubling, the fine exceeds $100,000 for day 15, exceeds $1 million for day 21, and exceeds $1 billion for day 25.

Um… me thinks that even though it is a true statement that on day 15, the fine is more than $100,000, the justices probably meant day 11. Well, anyway, let’s continue:

The Court acted well within its discretion in starting the fine schedule at $100 a day. The Court also was entitled within reasonable limits to double the amount of the fine for each day of continued defiance. At that rate the cumulative fine after seven days, when we issued our stay, was $12,700. At some point, however, the doubling reaches unreasonable proportions. Under the current schedule the fine for day 25 is more than $1 billion; the fine for day 30 is more than $50 billion.

We believe that the doubling exceeds the bounds of the District Court’s discretion when the level of each day’s fine exceeds $1 million. The present schedule calls for a fine of more than $800,000 on day 14. We will therefore modify the contempt sanction against the City to provide that the fine shall be $1 million per day on day 15 and $1 million per day for every subsequent day of noncompliance.

So instead of having the fines double each day, after the doubling reached $1 million, each subsequent day, the fine would be another million bucks. The U.S. Supreme Court got the case in 1988 and decided not to grant a stay (meaning they didn’t want to put the Court of Appeals ruling on hold). In other words, the fines imposed by the Court of Appeals were constitutional and enforceable!

Even with the “reduced” fine, the city of Yonkers started to feel the pinch…

Mr. DeLuca [the city manager] has estimated that the city could pay fines through day 79, when the total would exceed the $66 million the city has in available resources… [NYT article].

On September 8, the New York Times ran an article about the drastic measures that Yonkers was about to be forced to take, since the contempt fines were nearing $1 million. By November 5th, the city would have to layoff 1,605 employees, leaving only 348 critical employees needed for minimal public safety and health! The article, rightly titled “‘Doomsday’ Layoffs Plan Adopted for Yonkers” continues:

According to the city schedule, ”all city services would be phased out after 12 weeks, on Thanksgiving Day, Nov. 24, 1988.” Under the state plan, the city would be operating under an emergency austerity program by Nov. 5, with the money saved available to ”retain a small work force” that would provide ”minimal public health and safety.”

Mr. DeLuca circulated a notice this evening to all employees, saying that they would be ”informed in writing as to your scheduled layoff date with as much notice as possible.” Employees would also be informed of their rights regarding unemployment insurance and options to continue benefit plans at their own cost.

”A final ‘Doomsday Plan’ will be in effect by Thursday morning,” Mr. DeLuca wrote. ”I regret to inform you this is not a rumor.”

Two days later, two of the four city council members who were defying the court order relented. The vote had switched, from 3-4 to 5-2. The first round of layoffs, scheduled in a matter of days, was averted.

Approval of the housing plan means an end to the fines that threatened to bankrupt the city, with the last assessment recorded on Thursday. The money already paid, $1.6 million in checks made out to the U.S. Treasury, will not be returned.

The case was not officially closed until May 2007 — twenty seven years after it began — when Judge Sand finally ruled that the court order had been followed through.

SOME MATH ANALYSIS

I made a graph of how much Yonkers owed the government each day starting on August 2nd until they agreed to the court order on September 9th:

However, you can’t quite tell what’s going on for the first 30 days, because the scale is so large… And in general, when you’re plotting three or more orders of magnitude, you should plot on a log scale. So…

Notice the new scale (see the numbers on the left increase by an order of magnitude). It allows you to see more information. Like what’s that really long straight segment in the middle? Well, remember the fines were put on hold from August 9th to September 2nd, so the amount of money owed by Yonkers was kept constant for those days. That sort of “detail” got lost in the first graph, because the scale was so large!

And the first third of the graph looks linear, while it looked totally flat on the original non-log-scale graph. Why linear? Well, because remember the fines were doubling for all of those days, and when you plot exponential growth on a log scale, you get a line! But be careful! It isn’t exactly a line… We aren’t plotting $100, $200, $400, $800, etc., which would be perfectly exponential data. We are plotting the cumulative totals, which are $100, $300, $700, $1500, etc. These numbers don’t form a perfect exponential growth, though they are super duper close to being perfectly exponential! So for all intents and purposes, we can call it exponential, and hence, the first third of the graph is pretty darn linear.  Since the last third of the graph still has the fines doubling and being added to the cumulative total, that section too is linear.

I also was really curious what would have happened if Yonkers didn’t pay up when they did… What if they let the fines accumulate until December 31st? Well, I also plotted that without and with a log scale…

Looking at the first graph, we see that starting around day 37, we get a linear increase. Recall that’s because the Court of Appeals ruled that after the fines reached $1 million/day, they would stay $1 million/day. So each subsequent day, the fine just grows by the constant amount of $1 million.

(On the second graph, the log scale graph, we see the data go from linear to constant to linear — just like in our graph of what the town actually owed — but then the graph starts “slowing down” right at the same time the first graph becomes linear. That curve is actually logarithmic. Can you see why?)

My last hypothetical is: what if the Court of Appeals and the Supreme Court didn’t find the doubling fine unconstitutional. What would that graph look like if extended to December 31st? Plotted on a log scale, we get:

On December 31st, Yonkers would have owed the federal government: $17,014,118,346,046,900,000,000,000,000,000,000,000,000.

And as of the writing of this post, the national debt is only about $9,500,000,000,000.

YIKES! Good for the paying off the national deficit, bad for Yonkers.

A timeline for the case’s initial unfolding was published in the NYT here:

  • Dec. 1, 1980: Justice Department sues Board of Education, City of Yonkers and Yonkers Community Development Agency, charging that the city racially discriminated in education and public housing.
  • Dec. 1, 1980: Justice Department sues Board of Education, City of Yonkers and Yonkers Community Development Agency, charging that the city racially discriminated in education and public housing.
  • Nov. 20, 1985: Judge Leonard B. Sand of Federal District Court in Manhattan rules that Yonkers’s housing and schools were intentionally segregated by race. A housing remedy order directs the city to build 200 units of public housing and to plan additional subsidized housing.
  • Jan. 28, 1988: City Council approves consent decree that sets timetable for building 200 units of public housing and commits city to an additional 800 subsidized units.
  • July 26: Court sets Aug. 1 deadline for Council to adopt zoning amendment needed to build the 800 units.
  • Aug. 1: Council rejects amendment in a 4-to-3 vote.
  • Aug. 2: Judge Sand finds city and the four Councilmen who voted against the amendment in contempt of court and imposes fines. The city’s fines start at $100 and double every day. The Councilmen are fined $500 a day.
  • Aug. 9: The fines are suspended by a Federal appeals panel while the contempt ruling is appealed.
  • Aug. 26: An appeals panel upholds contempt ruling and fines, but fines against the city are capped at $1 million a day. The fines remain suspended so the city can appeal to the United States Supreme Court. Sept. 1: The Supreme Court refuses to grant the city a further suspension of fines but does continue the stay of fines against the Councilmen so they can seek the High Court’s review of their contempt rulings.
  • Sept. 2: Judge Sand reinstates the fines against the city.
  • Sept. 5: Mayor Nicholas C. Wasicsko meets for 7 1/2 hours with the City Council in an effort to end the impasse, but no compromise is reached.
  • Sept. 6: The Westchester District Attorney decides not to prosecute the four Councilmen who voted against the plan.
  • Sept. 7: As contempt fines continue to build up, a state panel adopts a ”doomsday” plan to cut city services.
  • Sept. 8: Fines pass the $1 million mark. As Yonkers residents confront layoffs and cuts in city services, pressure grows on the Mayor and the City Council to resolve the crisis. A City Council meeting over a transfer of funds to finance the fines erupts into a shouting match.
  • Sept. 9: The City Council votes to accept the plan.

MIT, I’m disappointed in you

I love the MIT magazine Technology Review. This month’s issue had the following diagram in it, associated with an article about carbon footprints:

Anyone else see the problem? And anyone else see a teachable moment?

If you don’t see it, think about the data. You’re saying the World Average is 4 metric tons, the US Homeless Person is 8.5 metric tons, and US Resident is 20 metric tons. In any representation of the data, the US Homeless Person should be a bit less than twice the World Average. And the US Resident should be five times the world average.

Now look at the picture. Does that diagram represent that?

Put it another way: can you fit exactly five of the small circles in the largest circle?

(No.)

The diagram is misleading because you look at it and naturally compare areas. But unless you give it more than a glance, you won’t notice that the numbers (4.5, 8, 20) actually are the radii of the circles!

This could be the hook for a geometry or Algebra I class (on proportions, on circles, on data analysis). A teacher could then to parlay it to a discussion of how to “fix” the problem…

I see two easy solutions:

  1. Make a bar graph (boring solution)
  2. Make the same bubble graph, but make the radii \sqrt{4.5}, \sqrt{8}, and \sqrt{20} respectively (more fun solution)

In coming up with the second solution, students will think about areas, proportions, and visual representations of data. I can see students each approaching and solving the problem slightly differently, but still getting the same answer. In that sense, it allows for some grappling and struggle.

I still love the Technology Review. Not only is it full of good reads, but good ideas for lessons!

Look below the jump for a revised graph, which accurately represents the data…

(more…)

Electoral Math and Computer Science Rocks!

I wish I taught a computer science course so I could introduce this problem.

How many unique ways are there to acquire at least 270 electoral votes without any excess?

For example, one combination would be to win California, Connecticut, the District of Columbia, Hawaii, Illinois, Maine, Massachusetts, Michigan, Minnesota, New Hampshire, New Jersey, New York, Ohio, Oregon, Pennsylvania, Rhode Island, Vermont, Washington and Wisconsin. That would be equal to 272 electoral votes (not coincidentally, these are the John Kerry states plus Ohio).

Note that there are no excess electoral votes in this combination: if you remove one of the states with three electoral votes, the number falls to 269, which is below the 270-EV cut-off. So winning all of these states plus North Dakota would not qualify, since the candidate has superfluous electoral votes. On the other hand, replacing Vermont with North Dakota would make for a unique combination.

Not only is an awesome math/computer science problem, but I have to say that I totally love the response that it generated in the comments. (Plus, Isabel Lugo’s solution is just so damn sleek.) Minus a minor spat in the comments, this is totally one heck of a sick blog post.

MMM7 Solutions

Interestingly, this week’s Monday Math Madness (7) question can be answered with a direct application of generating functions, which I recently used to derive the Fibonacci numbers a few weeks ago! (See here for Part I and here for Part II.)

Let me be clear. You don’t actually have to make a generating function out of this, like I do below. I recognize that it adds one more “layer of complication” that isn’t really needed. I did it because it helps me keep my terms straight. Plus I wanted to connect it to the Fibonacci posts that I did easily. You can easily do it without.

The short answer:

Create a function g(x) by letting each of the terms in the sum being a coefficient. Eventually, we want to find g(1).

Let’s begin the extended answer!

g(x)=(\frac{3}{5})^0F_0+(\frac{3}{5})^1F_1x^1+(\frac{3}{5})^2F_2x^2+...
\frac{3}{5}xg(x)=(\frac{3}{5})^1F_0x^1+(\frac{3}{5})^2F_1x^2+(\frac{3}{5})^3F_2x^3+...

Note that g(1) is exactly the sum we want to find! Add the two together and combine like terms to get:

g(x)+\frac{3}{5}xg(x)=(\frac{3}{5})^0F_0+(\frac{3}{5})^1(F_0+F_1)x^1+(\frac{3}{5})^2(F_1+F_2)x^2+...

Remembering the Fibonacci recurrence relation (e.g. F_1+F_2=F_3 and such), and using it to simplify the coefficients above, we get:

g(x)+\frac{3}{5}xg(x)=(\frac{3}{5})^0F_0+(\frac{3}{5})^1F_2x^1+(\frac{3}{5})^2F_3x^2+...

We want to get “g(x)” on the right hand side (RHS), and we see that multiplying the RHS by \frac{3}{5}x will help. Because at least then we’ll have the same number for the exponents and the Fibonacci number!
\frac{3}{5}xg(x)+(\frac{3}{5})^2x^2g(x)=(\frac{3}{5})^1F_0x^1+(\frac{3}{5})^2F_2x^2+(\frac{3}{5})^3F_3x^3+...
Noting that F_0=F_1, we see that the RHS is really g(x)-F_0. (It has all the terms in g(x) except for F_0.)
Finally, we get \frac{3}{5}xg(x)+(\frac{3}{5})^2x^2g(x)=g(x)-F_0.
Rearranging this equation, we get g(x)=\frac{-F_0}{\frac{3}{5}x+(\frac{3}{5})^2x^2-1}
Now for the easiest part… plugging 1 in for x, we get g(1)=25. Since g(1) was the infinite sum we were trying to find, we are done!

There are two things to note.

  1. Because our method of solution wasn’t really dependent on the 3/5 at all, we can solve the problem for any other fraction (well… technically… it has to be within the radius of convergence…).
  2. It might seem unintuitive that the original infinite sum will converge. Because you’d think that either the (3/5)^n would decay at a different rate than F_n increases. But it turns out that they both grow exponentially! (You can see that by looking at my previous post on the Fibonacci numbers and how to come up with a general equation for the nth term!). And so having one decay exponentially fast and the other grow exponentially fast end up “cancelingl” each other out. Which is a wishy-washy explanation as to why we can get such a beautiful convergence!

Matrices, Social Networking, and Algebra II

At the tail end of the fourth quarter, my students and I grew tired, weak, and weary from trigonometry overload, so we did a short one week lesson on matrices and systems of equations. I taught them how to add, subtract, and multiply matrices — by hand, and on their calculators. Then, I decided I wanted to bring some “real world” stuff to them.

So I decided to do a lesson on matrices and food webs [click here to view the assignment]. I pretty much stole it wholesale from some website or another (my motto: beg, borrow, and steal!), made a few changes, and let them go at it. And even though I don’t know how interested all of them were with the assignment, I was actually extraordinarily pleased at how well they did on it and how engaged they were in the classroom [1]. They talked, debated, and came to some pretty solid conclusions. My role in the classroom was relegated to going around and asking them questions like “so you answered the fourth question… can you tell me what the 2 in that matrix represents?”

You know, just to make sure they were getting it.

And they were.

One of my favorite moments was when a group asked me “do you add or multiply the matrices?” and I asked them “what do you think?” and then they got to arguing about it for 3 minutes before they came to the right conclusion.

Literally five minutes after finishing this activity in my first class, I realized that all the social networking sites (MySpace, Facebook, and the like) can be analyzed in the same way as food webs. Hello six degrees of separation!

So at the beginning of my next class where we were going to do food webs, I first drew a bi-directional network on the whiteboard with three teachers and one student. The student I chose is one who I felt I could poke fun at because he pokes fun at me. Of course I made up funny relationships between all my characters. So, for example, I said that the student liked teacher A, but teacher A didn’t like the student one bit — she told me that she thinks he is too rambunctious. And so forth. It was a tiny, fun little network, with all these fun little stories behind each relationship, and we made a tiny, fun little matrix from it. Then we moved on to the food web activity.

After class, I thought: why not do this whole social network thing next year? So last night I made up a fake set of relationships among teachers at my school and then created a network:

It’s pretty funny actually. I have one husband who likes his wife, but the wife doesn’t like her husband, and other strange relationships. And to accompany it, I made a draft of a worksheet to use next year [click here for draft]. And you know what: I think it’s pretty good. [2]

Besides food networks, and friend networks, I had two more ideas:

  1. Actually make a small celebrity network using IMDB, connecting them only if they’ve been in the same movie. A la Kevin Bacon. Then using that matrix to calculate the degrees of separation.
  2. Have students pick an airline and a bunch of cities it serves. Look at all the flights of an airline on a particular day — and make a matrix representing the number of flights that are made between all cities that one day. Some cities won’t have direct flights between each other — but that’s when you use the square of the matrix, to find which cities are accessible to one-another via one stop over. And you can take the cube of the matrix to find out which cities are accessible via two stop overs. And so forth.
Actually, I really like the second idea for some sort of take-home student project, where we also learn and use some basic Excel. Hmmmm….
And you were wondering what my last post was all about! Ah, gentle reader, I would not leave you hanging for too long.
[1] What was interesting to me about this assignment was although I saw them all working and thinking and grappling, showing true engagement unlike other times when I’ve failed, they didn’t show a true *interest* in the topic. Which makes me question the whole equality that teachers and administrators often believe in implicitly: student interest = student engagement.
[2] Although I might make two changes: (a) not make the network bi-directional (if person A is friends with person B, then person B is friends with person A), and (b) focus more on how to figure out how many degrees of separation someone is from someone else.

Answer to my generalized MMM6 question

So I posed the more generalized question to  Monday Math Madness 6, which read:

Start with 500 gallons of mayonaise.
1) Mix in 3 gallons of mayonaise and 7 gallons of ketchup. Stir until completely mixed.
2) Remove 10 gallons of the mixture.
3) Repeat steps 1 and 2 until the mixture is approximately 40% mayonaise and 60% ketchup (200 gallons mayo, 300 gallons ketchup).

How many iterations will it take to do this? 

My solution below the fold.

(more…)

Monday Math Madness 6 Solutions

Here is my proposed solution to MMM6. (Questions, for the uninitiated or forgetful, are here.)

I actually found these problems to be on the easier side (solved both parts in less than 30 minutes), but I tend to be hasty when I work things out, and overconfident in my thinking, so chances are I’m not right on both counts. So here’s throwing caution to the wind and hoping that I got it right.

(Also, if you liked the problem, don’t forget to look for my generalized problem. Solution to be posted soon.)

Part I Solution:

I created a matrix X_0=[500 \hspace{12pt} 0] which represented the [mayonaise, ketchup] initially. I also created a matrix Y=[0 \hspace{12pt} 10] which represented how much [mayonaise, ketchup] I was adding at each iteration. I let k=500/510 which is our “normalization” factor. (You’ll see…)

After the first iteration, we have X_1=k(X_0+Y) which turns out to be X_1=[490.196 \hspace{12pt} 8.804]. You see now what the k does? It makes sure that we have 500 gallons total in the vat.

After the second iteration, we have X_2=k(k(X_0+Y)+Y) which simplifies to X_2=k^2X_0+(k^2+k)Y.

After the third iteration, we have X_3=k(k(k(X_0+Y)+Y)+Y) which simplifies to X_3=k^3 X_0+(k^3+k^2+k)Y.

And you can see the pattern. After the nth iteration, we will have

X_n=k^n X_0+(k^n+k^{n-1}+...+k^2+k)Y.

Now we’re almost done, believe it or not. We can use k^nX_0=k^n[500 \hspace{12pt} 0] to find out how much mayo is in the vat. (Note that since Y=[0 \hspace{12pt} 10], the (k^n+k^{n-1}+...+k^2+k)Y doesn’t contribute to the mayo.)

We want to find when the mayo is around 250. The mayo after the nth iteration is 500k^n. So we have to solve the equation:

250=500k^n

A simple manipulation (taking the log of both sides) yields n\approx 35.

Of course a simpler way to think about this is to say that you start out with 500 gallons of mayo. After n iterations, you’ll have (500/510)^n 500 gallons of mayo. That brings you to the very last step, which is quickly solvable.

But even though that’s the simpler way to do it, it isn’t the way I started thinking about it. I freely admit that I don’t always find the simplest solution… but it certainly helps when doing generalizations!

What happens if we have add 3 gallons of mayo and 7 gallons of ketchup each time… How many iterations until we get a mixture of 200 gallons of mayo and 300 gallons of ketchup?

My sort-of-involved method works for that! I dare you to try it. You get about 98 iterations. It’s only very slightly tricky, so I’ll write up the solution to that problem in a future post.

Part II Solution

Let’s take the 17 lbs of beef (“it’s what’s for dinner!”).

Let’s have (single,double) represent the number of single and double burgers that Nortrom can eat. We know that these combinations are (1,8), (3,7), (5,6), (7,5), (9,4), (11,3), (13,2), (15,1), (17,0). Let’s see how many different ways that Nortrom can eat one of these combinations of single and double burgers.

Well, let’s look at (7,5). This is 7 single burgers and 5 double burgers. How many ways are there of ordering them? Clearly there are \binom{12}{7} ways.

Let’s me be clear about this. If Nortrom eats 7 single burgers and 5 double burgers, Nortrom will be eating 12 burgers. We just have to find the number of different ways he can do this. Nortrom, before eating them, placed them down in order of eating them — in 12 slots. Nortrom puts his first burger in slot 1, Nortrom puts his second burger in slot 2, Nortrom puts his third burger in slot 3, etc. Nortrom has to put single burgers in 7 of the 12 slots. (The rest will be filled with double burgers.) The number of ways to do that is \binom{12}{7}. [1]

So then we have, using our combination of single and double burgers listed above: X=\binom{9}{1}+\binom{10}{3}+\binom{11}{5}+\binom{12}{7}+\binom{13}{9}+\binom{14}{11}+\binom{15}{13}+\binom{16}{15}+\binom{17}{17}=2584.

Let’s do exactly the same thing for our 25 lbs of beef!

The combinations are (1,12), (3,11), (5,10), (7,9), (9,8), (11,7), (13,6), (15,5), (17,4), (19,3), (21,2), (23,1), (25,0).

This leads to a similar conclusion:

Y=\binom{13}{1}+\binom{14}{3}+\binom{15}{5}+\binom{16}{7}+...+\binom{24}{23}+\binom{25}{25}=121,393.

Huzzah!

[1] As a quick aside, note that \binom{12}{7}=\binom{12}{5}. This is because if you have 12 slots and you have to put double burgers in 5 of the slots, then the rest must be filled with single burgers.