Sending Scouts Into The Desert

The problem I have this time is a bit of a weird one, I mostly only show it because it has an amazing solution and proof. I first found this puzzle at Cut The Knot, which is something of a math puzzle page.

Consider an infinite 2-dimensional checkerboard. The upper half of the board is called the "desert" and the lower half of the board is called the "base", and there is a line across the middle that divides the two (just to be clear, there are no squares between the desert and the base, every square is either in the desert or the base).

You will be playing a one player game on this board. First you set up as many checkers anywhere you want in the base (each square may only be occupied by one checker). Then you begin making your moves. A move consists of a checker jumping another single checker that is orthogonally adjacent to it and landing on the space on the other side (which was unoccupied before). The checker that is jumped over gets removed.

The goal is to get one of your pieces as far into the desert as possible. Find how many pieces it takes to get N spaces into the desert.

That may have been a bit awkward to read, however there is a nice applet at Cut The Knot that will allow you to play this game. That page also has the solution to this problem, so don't scroll too far down unless you are ready to see the solution. The solution that is there is quite well written though, and when I post the solution to this next time I'm basically just going to be following his derivation.