All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
Leapfrog (Posted on 2003-06-24) Difficulty: 4 of 5
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.

No Solution Yet Submitted by DJ    
Rating: 4.2727 (11 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Level 5 Solution | Comment 15 of 18 |
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
  Posted by Brian Smith on 2003-10-16 12:18:26
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information