Tag Archives: math


Robert Kosara, a research scientist at data visualization software company Tableau, has been solving puzzles using the US’s nearly 4,2000 ZIP codes for years, writes Christopher Ingraham at The Washington Post. Kosara had a question:

What would it look like if you drew a single line through all Zip codes in the lower 48 in numeric order? Kosara wrote some code and let it rip, and what he ended up with was a map that clearly delineated state boundaries and gave a reasonable approximation of population density to boot. Since it looked as though it were created by scribbling in arbitrary regions of a U.S. map, he dubbed it the ZIPScribble map.

Kosara ran some calculations and discovered that if you started at the lowest-numbered Zip code (00544, Holtsville, NY) and walk through every Zip code in the continental U.S. in numeric order all the way up to the highest-numbered Zip code (99403, Clarkston, WA), the path you’d need to take would be roughly 1,155,268 miles long. Which naturally brought up a second question: What would be the shortest route you could take through all 37,000 of those zip codes?

This type of problem actually has a storied history in computer science. It’s known as the Traveling Salesman Problem: Say a salesman has a bunch of cities in his route — what’s the shortest trip he can take through all of them? This type of computation is used as a benchmark in computer science because it has a lot of applications, from route-finding to the creation of circuit boards, and because it gets complicated really, really quickly. For instance, a network of only 20 points contains roughly 1.2 quintillion(1,200,000,000,000,000,000) possible solutions, only one of which can be the shortest. That’s on the order of magnitude of the number of grains of sand on earth.

What, then, of a traveling salesman problem with more than 37,000 points?

Kosara took a crack at it. He called it the Traveling Presidential Candidate Problem, after a hypothetical presidential candidate who wanted to visit all 37,000 contiguous Zip codes to clinch the nomination.


If you want to share a candy bar fairly between two people, one of the people breaks the bar in half, the other chooses which piece they want. Everybody knows that, right?

But what if you’re dividing unequal things among more than two people? What if, for example, three people are sharing a three-bedroom apartment? The bedrooms are unequal sizes, one gets more natural light than the others, another has more closet space. How do the three roommates pick bedrooms and rents fairly, so that each roommate believes they got a fair deal?

To Divide the Rent, Start With a Triangle – Albert Sun, The New York Times

Those working on fair division like to joke that it traces back to Solomon and the baby. Steven Brams, a professor of political science at New York University and a pioneer of the field, says both the Bible and the Talmud have examples.

The procedures have been used to divide such things as Germany after World War II, deep-sea mining rights, and property after a divorce or death.

The solution is tricky to explain, and I’ll leave that to the Times article (above). But anybody can figure it out; you don’t have to be a math genius. And once you’ve figured it out, you can use it for anything, with the help of a simple Web tool.

I think Neal Stephenson used something like this in an early scene in Cryptonomicon. I don’t remember the specifics. I do remember that the elderly patriarch of a family of brilliant mathematicians dies, and his descendants divide up his furniture and stuff by laying it all out in a parking lot and then his descendants come by as individuals and move the objects they want to different parts of the parking lot. The location to which the object movies signifies how badly the person wants that particular thing. When nobody has moved everything for a while, then the descendants decide the negotiation is concluded and divide everything up.

Also, from Francis Su, who developed the algorithm described by the Times: “What is ‘Fair Division’?”

The theory of fair division is concerned with finding ways to divide an object among n people fairly. There are many possible notions of fairness. The notion that has interested me recently is finding envy-free divisions, i.e., one in which each person feels she received the best piece, in her own estimation.

Exact vs. Approximate Algorithms
Existence of such divisions has been known for some time. Of greater interest are algorithms for achieving such divisions. For instance, in dividing a desirable object, such as cakes, a 2-person algorithm has been known since antiquity, a 3-person algorithm since at least 1960, but an exact algorithm for achieving n-person envy-free cake divisions was not produced until Brams and Taylor’s solution in 1995…. Elisha Peterson and I have recently extended these techniques to provide an exact envy-free chore-division algorithm for n people. However, such methods tend to be quite complicated as n grows large.

By contrast, I have been interested in developing approximate envy-free schemes, in particular, through the use of arguments from combinatorial topology … Such methods will find envy-free divisions up to a specified tolerance for error (such as at the level of crumbs), and have the advantage of (1) being easily generalized for arbitrary numbers of players, (2) using the minimal number of cuts, (3) for a fixed number of players and a fixed error, having a bounded number of steps in which the algorithm halts.