Friday, January 04, 2008

One Million Dollar Desecration Prize

For some reason my idea of a mathematically efficient packing of the stars in the American flag was not that popular. I think this is because people really want a flag where the importance of states is shown. Important states should have big stars and other loser states smaller ones.

So the problem becomes “how can you arrange these different sized circles most efficiently inside a rectangle”? This problem is NP-Hard (pdf). This mean there is no polynomial time algorithm that will put different sized circles into a rectangle and guarantee that arrangement to have the least amount of free space. If you find a way to solve this packing problem in polynomial time you win the 1 million dollar prize as this will show that P=NP

So if you can find an efficient way to desecrate the American flag you can win 1 million dollars. In my next post I will look at heuristic methods to desecrate the American flag using the number of people executed by the state since 1976 to decide the size of star the state gets on the flag.

No comments: