31-circle-cross-blue-pattern.jpg

Homepage

Math and Life

The Wounded Rook

Here we have Sgt. SeBastion, Queen’s rook of the A division, veteran of the back rank, and personal aid to the King.

InkedSgt.SeBastion_LI.jpg

SeBastion lost both legs in a bloody rook lift, and hasn’t been able to move more than a square since.1

He’s visiting his old starting square, a8, reliving the glory days. Being a sentimental war vet, he wants to touch every square exactly once, ending on his old pal’s starting position, h1 (the star).

Is this possible?

For the uninitiated, rooks move horizontally or vertically any number of squares. SeBastion, wounded as he is, can only move one square horizontally or vertically before stopping to rest.

To put the problem more succinctly: starting on the top corner of a chessboard, can you, with only single horizontal or vertical moves, touch each square exactly once and land on the opposite corner?


Setting aside contrived tales of battle-scarred chess pieces, consider another puzzle:

With two opposite corners of a chessboard occupied, is it possible to cover the entire board with jenga pieces, such that each jenga pieces takes up two squares?

Here is my attempt:

Jenga.jpg

I encourage you to give both these puzzles a try. They are quite a bit of fun. I will be presenting an answer to both, so don’t scroll down if you want to take a whack at it.


Stuck? Here’s a hint: Both puzzles take place on a chessboard.

Terrible hint, isn’t it?


Alright here’s the solution.

First, the second one.

2. A chessboard is arranged such that each white square is completely surrounded by black squares, and each black square is completely surrounded by white squares. This means that each jenga piece must occupy exactly one white and one black square.

Ok. So what?

A chessboard has an equal number of white and black squares, but when you take away opposite corners (which are always the same color), there are an uneven number of white and black squares.

If there are an uneven number of white and black squares, and each jenga piece must occupy exactly one of each, it is impossible to cover the entire board with jenga pieces!

1. Again, I am going to use the fact that each square is surrounded by squares of the opposite color.

SeBastion starts on a8, a white square. On his first move, whatever that move may be, his only options are black squares. His second move must be a move to a white square. His third move must be to a black square, and so on. Each move alternates between white and black squares. You can list them if you want:

  1. black
  2. white
  3. black
  4. white
  5. ….

Notice that after an odd number of moves, Sebastion will be on a black square, and after an even number of moves, he will be on a white square.

If he is to touch every square exactly once, it will take him 63 moves to get to the opposite corner (64 total squares - 1 square he is already on).

Wait a minute. 63 is odd, so his last move should land him on a black square. But the opposite corner is a white square. It’s impossible!


What’s interesting about these puzzles is that they actually have nothing to do with a chessboard. Had I presented them on a plain 8x8 grid, both would still be impossible, and both of my arguments would still hold. The chessboard was merely an artificial way for me to conceptualize the impossibility.

If a similar problem2 were presented to me on a plain grid, I would first try to tile it as if it were a chessboard to see if it could give me any insight to the problem. Even though I started with a plain grid, the tiling might help me to understand the problem better.

To put it more abstractly, I started with a problem, then used something that is not relevant to that problem to solve it.

This is more than just a cool trick to solving silly puzzles. This kind of technique is used in serious math3 all the time.

Take, for instance, the harmonic series:

1.PNG

For everyone who hasn’t had the pleasure of taking a calculus class, this means

2.PNG

...on and on forever.

What is this equal to? Or, to put it more correctly, does this series converge?

This is tricky. We’re adding an infinite number of numbers, so it would seem to equal4 infinity, but each term is getting smaller and smaller, so it would seem to converge.5

To solve this question, I’m going to do something analogous to tiling the plain grid: create another series out of thin air.

We start with the original series, call it a:

3.PNG

For our new sequence, b, follow these rules:

  1. Start with the first term in a.
  2. If it is a power of two (negative powers count), copy it down
  3. If it is not a power of two, round it down to the next smallest power of two, then copy it down.
  4. Go to the next term in a
  5. See step 2.

I won’t make you figure it out yourself:

4.PNG

Now, compare these two sequences.

5.PNG

Look at them term by term (I’ve lined them up nicely so you can compare). At each step, the term of b is either less than or equal to the corresponding term in a. This makes sense if you look back at my rules. I only ever copied the term or rounded it down. So b, as a whole, is less than a. This means that a is greater than b. Remember that.

Now take a second look at b. I’ll expand it a bit.

6.PNG

Group them by powers of two:

7.PNG

What is the value of each set of parenthesis? ½ right? This means we can rewrite b as

8.PNG

So we just keep on adding one half plus one half plus one half. This clearly diverges to infinity.

Do you remember what I told you to remember? Good. a is greater than b. b diverges to infinity, so a is greater than something that diverges to infinity. Think about that for a second. a is bigger than infinity, so a also diverges to infinity.

What’s amazing about this result is that I created b out of thin air. I just said “this is what b is,” and eventually arrived at an answer. Isn’t that just cool?

We often imagine mathematical proof as one statement being a logical consequence of another statement, which, in turn, is a logical consequence of another,6 but this example tells a different story: Sometimes mathematical discovery comes from a leap of creativity. Could you just come up with b like that? I certainly couldn’t. That special insight is what makes math like this interesting. It’s results like these that make me come back for more.


1Very nerdy side note: That signature on c6 is Joel Benjamin’s. Aside from being a championship chess player, he was also the “Official Grandmaster consultant” for Deep Blue, the first computer to ever beat a reigning world champion in chess. Yes, I have personally met the mind behind the dawn of the AI revolution.

2there are many of these problems. Here is one

3there are a bunch of mathematicians laughing at me for labeling the harmonic series as “serious.” oh well.

4“Diverge to," pedants.

5If that seems odd, consider what would happen if you add a half plus a forth plus an eighth, plus a sixteenth on and on. It doesn’t equal infinity.

6many proofs do work like this.