Sciolism Rocks

Google recently announced its Google Treasure Hunt contest, which they describe as a contest to track “problem-solving skills in computer science, networking, and low-level UNIX trivia.” As all self-respecting French Lit majors should do, I signed up, natch. Two minutes later, I was presented with my first problem. I now take you on a three-part journey that shows where my mind goes when presented with a challenge like this.

To begin, the problem as presented:

Fascinating. For those who say “who cares,” well, I understand. Which brings me to my first strategy:

Personalize the problem

A clip-art robot moving (rightward and downward only) to a finish star doesn’t exactly make me want to start counting squares. So, I’ll change the problem a little and give myself a little motivation.

Now there’s motivation for me to figure this thing out. Amanda is my American Idol. But even though there are now stakes, the problem is still difficult. So I…

Solve a different problem

The 32×44 grid is daunting. I mean, this thing would be cake if the problem were, say, 2×2:

From my start point, there’s only one way to move to each blue square, since I can only move downward or to the right. I’ll mark that by putting big 1’s on each of those squares.

So now it should be reasonably obvious that there are two ways to move onto Amanda’s square: right then down, or down then right. Let’s mark that with a 2.

So there are two ways to go with a 2×2 puzzle. Let’s increase the difficulty a little, to a 3×3. I’ve filled in the info we know so far. Remember: I can only move down or to the right.

The two unlabeled white squares are easy. Since they are either directly below me or directly to my right, there’s only one way to get to them. Labeled:

For the blue square just above Amanda, there are three ways to get there:

And similarly for the blue square to her left. To wit :

If there are three ways to get just above or just to the left of Amanda, and remembering that I can only move down or right, then there are six ways to reach the final square.

Okay, I’m bored with this already, so on to the next strategy:

Look for Patterns

Who else has noticed that you can get the sum of any square by adding the numbers above it and to its left?

The squares along the edges don’t get any more complicated. A 4×4 grid appears thusly:

And the remaining squares can get filled in by the pattern we noticed.

Maybe this pattern of numbers looks familiar to you. Perhaps if I rotate the image 45°, desaturate the checkerboard a little, and keep our pattern going, you’ll recognize it.

This pattern, commonly known as Pascal’s Triangle has actually been known for a long, long time. The example shown here was published in 1303 by Zhu Shijie (1260-1320), in his Si Yuan Yu Jian. It was called Yanghui Triangle by the Chinese, after the mathematician Yang Hui. (Click to enlarge)

This gives us the following information.

Number
of Points		Regions
   2			   2
   3			   4
   4			   8
   5			   _
   6			   _
   7			   _ <-This is the number I want

Next time, I’ll give you the answer to the circle problem. And show you that it and the Amanda problem have a very curious thing in common.

---

Let’s not spoil it for everyone by posting the answers to either problem in the comments. I’m happy to talk about them through email if you want to make a guess.