Not many people have the ability to look at the few fundamental elements of a system (such as constructs of a new computer language) and extrapolate the long-term implications of their use. But rather than jump in and tackle the difficult question of understanding the expressive power and limits of computation, I’ll start by talking about a simpler problem. Don’t panic: it involves crayons and coloring!

This example is going to seem pretty easy on the surface, and you may be familiar with it already. It involves trying to find a way to color in maps so that no areas which share a border are going to be the same color. Here’s an example of a simple coloring with 5 crayons, and then finding a method for doing it with only 4 (taken from Wikipedia’s article on the subject):

Without prior knowledge, the average Joe can only guess at how many crayons he’d need to reliably fill in any map he is given. Just by trying a few cases, he might get an intuition that a small box of different colors will do the trick. But if Joe knew the Devil was going to be presenting him with an arbitrary map and getting his soul if he couldn’t color it properly, he’d probably buy Crayola’s biggest box…120 colors! (Plus, because he doesn’t know for sure that even THAT would be enough, he’d also probably try to round up the discontinued colors off of eBay!)

Yet there is salvation from this kind of paranoia. Early formalisms of the map-coloring-problem from mathematicians comforted us with proof that it *never* took more than 5 different colors…and that 3 will certainly not always be enough. After considerable debate and experimentation over the years, we ultimately found that we only need four unique colors for any map the Devil—or anyone else—makes.

(Note: Depending on your purposes, discovering it was 4 vs. 5 might be somewhat academic. I myself feel that the more crucial step was bringing in math to save us from needing to pack a potentially infinite number of crayons.)

Now…what if the “Devil’s Map” you must solve is instead an arbitrary selection from mankind’s constant creation of new ideas for software? That raises a lot of questions about what a programmer needs in their backpack to be confident they could correctly “color in” any program specification with a working implementation.

(more…)

I somehow tripped across this problem on something called “Monday Math Madness #4″. They mentioned a Rubik’s Cube as a prize, and since some of the stickers are coming off of mine I decided to go ahead and work out the solution. My answer was right, but there were many correct answers so I was not chosen to win the cube… or the Amazon gift certificate. Alas.

Daniel: Hey Quan, we just received a shipment of 25 Macbook Pros from Apple Inc.

Daniel: Don’t worry Quan. The optimal strategy will only take ______ iterations.

First test all laptop groups w/no overlap (5 iterations). Label each computer with its performance rank order in the test.

Remembering which group it came from, test the fastest laptops from each group (marked 1) against each other. This will be the sixth iteration. Label each computer in the group whose laptop won this test “A”, the group whose laptop came in second place “B”, etc.

So each computer should now have a letter and a number. These equations show us what we know so far about their relative speeds:

A1 < A2 < A3 < A4 < A5
B1 < B2 < B3 < B4 < B5
C1 < C2 < C3 < C4 < C5
D1 < D2 < D3 < D4 < D5
E1 < E2 < E3 < E4 < E5
…and…
A1 < B1 < C1 < D1 < E1

We are only looking for 3 laptops. Thus we can exclude all computers labeled D and E as well as those labeled 4 and 5, because there are always three computers guaranteed to be faster than them. So this reduces our consideration to:

A1 < A2 < A3
B1 < B2 < B3
C1 < C2 < C3
…and…
A1 < B1 < C1

By similar logic, we know that B3, C2, and C3 are not in the running…e.g. we cannot choose B3 because the transitive property tells us that B2, B1, and A1 are faster. Narrowing the field to potential winners for the top 3 places we now have:

A1 < A2 < A3
B1 < B2
C1
…and…
A1 < B1 < C1

It is certain that A1 will be chosen, because it is the fastest of the fast. That leaves only 5 candidates for second and third place. So test them all together for the seventh and final iteration [A2, A3, B1, B2, C1]. Take the two top winners from this test along with A1 and you are done.

That is 7 iterations.