Assume you have a checker board with 7 rows and infinite columns. You can place checkers on only the first 2 rows initially (number these -1 and 0). Then you may jump other checkers up, down, right, and left but not diagonally. The goal is to get as high a row as possible. For example you can get to the second level with four checkers like this:
Level Setup Turn 1 Turn 2 Turn 3
------ ------- ------- ------- -------
2 ····· ····· ····· ···a·
1 ····· ···d· ···d· ·····
0 ·abc· ·ab·· ···a· ·····
-1 ···d· ····· ····· ·····
It turns out you need at least 2 checkers to get to level 1, 4 to get to level 2, 8 to get to level 3, and 20 to get to level 4.
Prove the least number of jumps it would take to get to level 5, and how you would do it.
Note: You may place the initial checkers anywhere you wish, as necessary.
It is impossible to get to level 5 using any number of checkers.
Consider a checkerboard with infinite rows and columns. Half of the checkerboard is filled so that a half infinite plane is filled.
* = empty space
X = filled space
$ = goal (empty)
row 5 * * * * $ * * * *
row 4 * * * * * * * * *
row 3 * * * * * * * * *
row 2 * * * * * * * * *
row 1 * * * * * * * * *
row 0 X X X X X X X X X
row -1 X X X X X X X X X
row -2 X X X X X X X X X
row -3 X X X X X X X X X
row -4 X X X X X X X X X
row -5 X X X X X X X X X
-
Each checker contributes some value to the goal. A checker which is closer contributes more than one that is farther away. A checker in row x is one magnitude more valuable than a checker in row x+1. A checker closer to the center column by one row is one magnitude more valuable that the further away checker. Applying this order of magnitude to the grid yeilds:
col#s-> -4 -3 -2 -1 0 1 2 3 4
row 5 * * * * (t^5) * * * *
row 4 * * * * (t^4) * * * *
row 3 * * * * (t^3) * * * *
row 2 * * * * (t^2) * * * *
row 1 * * * * (t) * * * *
row 0 t^-4 t^-3 t^-2 t^-1 1 t^-1 t^-2 t^-3 t^-4
row -1 t^-5 t^-4 t^-3 t^-2 t^-1 t^-2 t^-3 t^-4 t^-5
row -2 t^-6 t^-5 t^-4 t^-3 t^-2 t^-3 t^-4 t^-5 t^-6
row -3 t^-7 t^-6 t^-5 t^-4 t^-3 t^-4 t^-5 t^-6 t^-7
row -4 t^-8 t^-7 t^-6 t^-5 t^-4 t^-5 t^-6 t^-7 t^-8
row -5 t^-9 t^-8 t^-7 t^-6 t^-5 t^-6 t^-7 t^-8 t^-9
-
If reaching a specific level is possible, then the sum of the checkers in the initial configuration is equal to the value of the final checker's position.
For level one:
row 1 (t)
row 0 1
row -1 t^-1
-
1 + t^-1 = t. This implies t=(1+sqrt5)/2
For level two:
row 2 * * (t^2)
row 1 * * *
row 0 t^-2 t^-1 1
row -1 t^-1
-
1 + 2(t^-1) + t^-2 = t^2 agrees with t=(1+sqrt5)/2
For level 3:
row 3 * * (t^3) * *
row 2 * * * * *
row 1 * * * * *
row 0 t^-2 t^-1 1 t^-1 t^-2
row -1 t^-3 t^-2 t^-1
-
1 + 3(t^-1) + 3(t^-2) + t^-3 = t^3 agrees with t=(1+sqrt5)/2
For level 4:
row 4 * * * * (t^4) * *
row 3 * * * * * * *
row 2 * * * * * * *
row 1 * * * * * * *
row 0 t^-4 t^-3 t^-2 t^-1 1 t^-1 t^-2
row -1 t^-3 t^-2 t^-1 t^-2 t^-3
row -2 t^-5 t^-4 t^-3 t^-2 t^-3 t^-4
row -3 t^-4 t^-3
-
1 + 3(t^-1) + 5(t^-2) + 6(t^-3) + 4(t^-4) + t^-5 = t^4 agrees with t=(1+sqrt5)/2
For level 5:
Add up the entire half infinite plane of checkers. Each column is an infinite geometric series with ratio t^-1.
Column 0 = 1/(1 - t^-1)
Columns 1, -1 each equal (t^-1)/(1 - t^-1)
Columns n, -n each equal (t^-n)/(1 - t^-1)
The sum of the half infinite plane is the sum of the columns:
1/(1 - t^-1) + 2*(t^-1)/(1 - t^-1) + 2*(t^-2)/(1 - t^-1) + 2*(t^-3)/(1 - t^-1) + 2*(t^-4)/(1 - t^-1) + 2*(t^-5)/(1 - t^-1) + ...
Aside from the first term, this is geometric with a ratio of t^-1. Sum of half infinite plane = 1/(1 - t^-1) + (2*(t^-1)/(1 - t^-1))/(1 - t^-1) = (t^2 + t)/(t - 1)^2. Since t=(1+sqrt5)/2, the sum of the half infinite plane is (5*sqrt5 + 11)/2. But t^5 is also (5*sqrt5 + 11)/2. This means that no finite number of checkers can ever reach level 5.
Edited on October 16, 2003, 12:20 pm
Level 5 Solution
