9
$\begingroup$

Starting on a square of the checkerboard, "The Flea" is trained to jump to the center of another square. Then it keeps jumping (center to center) from square to square all around the board. It is observed that its jumps are always longer than the previous jump and it never jumps again to any previous squares. How many jumps can the Flea make?

$\endgroup$
9
$\begingroup$

[Edit: I've completely rewritten my answer. The earlier version relied a lot on a computer program. I'm now trying to find a solution by hand, especially after commenters have pointed out errors and improvements. Of course, I cannot unlearn what I found out with the help ofthe program.]

The maximum number of possible jumps is ...

... 32. One possible solution is shown in the spoiler blocks at the bottom of the post.

Sconibulus has explained the upper limit of 33 jumps and helpfully provided a list of moves.

It's easy to start off with a few moves, but it's in the end where fitting long moves to both the confines of the board and unvisited tiles will cause trouble. So this problem is solved best by starting from the end with the long moves.

Let's try to get a path of 33 jumps. Obviously, the first jump has to be across the whole board. The next steps are also more or less prescribed until we get the following board:

  0   2  --  --  --  --  -- --

4 -- -- -- -- -- -- --

-- -- -- -- -- -- -- --

-- -- -- -- -- -- -- --

-- -- -- -- -- -- -- --

-- -- -- -- -- -- -- 5

-- -- -- -- -- -- -- --

-- -- -- -- -- -- 3 1

(Zero is the starting point and any other number means after so many jumps.)

The next jump should be 5×6, but that will land us on the tile visited after move 2.

From other answers (and also from my previous, computer-aided version of the answer) we know that there are paths that go up to about thirty jumps. Let's assume that we can find a path that is one jump short of the upper limit.

We have to remove one possible jump from Sconibulus's list. By starting at the end, we have many 7-by-something and 6-by somehing to fit early, which means that we are likely to see early on if we canfind a valid path or not.

Omitting 7×7 yields the same problem as above: We revisit a tile. Omitting 7×6 and 7×5 will not leave us in a position to fit the 6×6 jump.

Omitting the 6×6 jump will let us proceed further, however. In fact, we can construct a valid path with pencil and paper after the long moves have been placed in a more or less obvious manner. We also need a rubber for backtracking, but the paths that must be backtracked are short. A path that I've found this way¹ is this one:

 32  30  28  --  23  --  11  --

-- 21 -- -- -- 7 -- 25

-- -- 12 14 -- -- -- --

26 -- 0 10 -- 16 -- --

-- 5 1 8 6 -- -- 9

-- 3 -- 2 -- -- 20 --

17 -- -- 4 -- -- 18 27

19 15 13 24 22 -- 29 31

The monotony of the jump distances can be verified:

   #         pos        diff      d²
---- -------- -------- ----
1 4 2
2 5 3 1 1 2
3 5 1 0 -2 4
4 6 3 1 2 5
5 4 1 -2 -2 8
6 4 4 0 3 9
7 1 5 -3 1 10
8 4 3 3 -2 13
9 4 7 0 4 16
10 3 3 -1 -4 17
11 0 6 -3 3 18
12 2 2 2 -4 20
13 7 2 5 0 25
14 2 3 -5 1 26
15 7 1 5 -2 29
16 3 5 -4 4 32
17 6 0 3 -5 34
18 6 6 0 6 36
19 7 0 1 -6 37
20 5 6 -2 6 40
21 1 1 -4 -5 41
22 7 4 6 3 45
23 0 4 -7 0 49
24 7 3 7 -1 50
25 1 7 -6 4 52
26 3 0 2 -7 53
27 6 7 3 7 58
28 0 2 -6 -5 61
29 7 6 7 4 65
30 0 1 -7 -5 74
31 7 7 7 6 85
32 0 0 -7 -7 98

There are many other possible paths. After reaching the fours and threes, it is easy to find moves on the board. After the path is completed, only just over a half of the tiles have been visited.

I think the most important thing is to see that the path should be constructed with the long jumps first.

________
¹ Tecnically, it was the pencil tool in MS Paint where the undo command took the place of the rubber.

$\endgroup$
  • $\begingroup$ Why do you rule out 6x6? I don't have a complete solution, but the four last jumps could be: ... [7,6] [1,0] [6,7] [0,0] [7,7] (where [7,6] -> [1,0] is the 6x6 jump). $\endgroup$ – Sphinxxx Oct 18 '16 at 7:43
  • $\begingroup$ I haven't ruled it out, my program did. :) There may well be other 32-jumps solutions that skip other jumps. $\endgroup$ – M Oehm Oct 18 '16 at 7:51
  • $\begingroup$ I may be wrong on this, but I think in the first solution you provided you can actually go up to 33. You can put 31 right above 29, 32 right below 30 and 33 in the top right corner. Correct me if I'm wrong. $\endgroup$ – Marius Oct 18 '16 at 8:44
  • $\begingroup$ @Marius: Okay, there are several errors here: The code did not print its final position, which would be 31 right above 29 for a 6×6 jump. That was fixed later. Your solution is good, but it is one that skips the 6×6 jump. Why does it go up to 33? That's a representation error, which took me a bit to realise: There are only 32 jumps between 1and 33. Will fix this in my lunch break. $\endgroup$ – M Oehm Oct 18 '16 at 9:34
  • $\begingroup$ There's also a flaw in the reaoning why 6×6 doesn't work: The block shows later, after that 6×6 jump has been made. @Sphinxxx: is correct, but the jump before that must be 7×4, which can land us only on [0, 2]. The jump before that is 6×5, which will take us to the already visited [6, 7]. $\endgroup$ – M Oehm Oct 18 '16 at 9:52
5
$\begingroup$

I can get

29 jumps

using this board where the numbers indicate the turn the flea is there

+----+----+----+---+----+----+----+----+
|    |    |    |   |    |    | 27 | 29 |
+----+----+----+---+----+----+----+----+
|    |    |    |   |    |    | 19 | 25 |
+----+----+----+---+----+----+----+----+
|    |    |  8 |   | 12 | 10 |    | 23 |
+----+----+----+---+----+----+----+----+
| 20 |    | 14 | 0 |    |    |    | 21 |
+----+----+----+---+----+----+----+----+
| 22 |    |    | 1 |    |  6 |    |    |
+----+----+----+---+----+----+----+----+
| 24 | 18 |  5 |   |  2 |  4 |    |    |
+----+----+----+---+----+----+----+----+
|    | 16 |  7 | 9 |    |    |    | 15 |
+----+----+----+---+----+----+----+----+
| 28 | 26 |    |   |  3 | 11 | 13 | 17 |
+----+----+----+---+----+----+----+----+

and here is the table of distances the flea goes.

+------+-------+---------+------+
| Jump | Coord | change  | dist |
+------+-------+---------+------+
|    0 | (4,4) |         |      |
|    1 | (5,4) | (1,0)   | 1.00 |
|    2 | (6,5) | (1,1)   | 1.41 |
|    3 | (8,5) | (2,0)   | 2.00 |
|    4 | (6,6) | (-2,1)  | 2.24 |
|    5 | (6,3) | (0,-3)  | 3.00 |
|    6 | (5,6) | (-1,3)  | 3.16 |
|    7 | (7,3) | (2,-3)  | 3.61 |
|    8 | (3,3) | (-4,0)  | 4.00 |
|    9 | (7,4) | (4,1)   | 4.12 |
|   10 | (3,6) | (-4,2)  | 4.47 |
|   11 | (8,6) | (5,0)   | 5.00 |
|   12 | (3,5) | (-5,-1) | 5.10 |
|   13 | (8,7) | (5,2)   | 5.39 |
|   14 | (4,3) | (-4,-4) | 5.66 |
|   15 | (7,8) | (3,5)   | 5.83 |
|   16 | (7,2) | (0,-6)  | 6.00 |
|   17 | (8,8) | (1,6)   | 6.08 |
|   18 | (6,2) | (-2,-6) | 6.32 |
|   19 | (2,7) | (-4,5)  | 6.40 |
|   20 | (4,1) | (2,-6)  | 6.32 |
|   21 | (4,8) | (0,7)   | 7.00 |
|   22 | (5,1) | (1,-7)  | 7.07 |
|   23 | (3,8) | (-2,7)  | 7.28 |
|   24 | (6,1) | (3,-7)  | 7.62 |
|   25 | (2,8) | (-4,7)  | 8.06 |
|   26 | (8,2) | (6,-6)  | 8.49 |
|   27 | (1,7) | (-7,5)  | 8.60 |
|   28 | (8,1) | (7,-6)  | 9.22 |
|   29 | (1,8) | (-7,7)  | 9.90 |
+------+-------+---------+------+

There are 4 combinations that were skipped with change in coordinates of

  • (6,5) doesn't fit
  • (6,4) doesn't fit
  • (5,5) same length as (7,1)
  • (4,3) same length as (5,0)
$\endgroup$
  • $\begingroup$ You can find the maximum eventually $\endgroup$ – TSLF Oct 15 '16 at 21:29
  • 4
    $\begingroup$ From 19 to 20 your distance decreases (according to your chart). $\endgroup$ – GentlePurpleRain Oct 17 '16 at 14:34
5
$\begingroup$

There's an upper bound of

33 distinct distance vectors from (1,0) to (7,7)
1x0, 1x1, 2x0, 2x1, 2x2, 3x0, 3x1, 3x2, 4x0, 4x1, 3x3, 4x2, 4x3=5x0, 5x1, 5x2, 4x4, 5x3,
6x0, 6x1, 5x4, 6x2, 6x3, 7x0, 5x5=7x1, 6x4, 7x2, 7x3, 6x5, 7x4, 6x6, 7x5, 7x6, 7x7

I appear to have found a path that hits

30 jumps, but I fear I may have made a mistake somewhere
(3,3), (4,3), (3,4), (5,3), (3,5), (6,4), (3,2), (3,6), (4,2), (7,5), (3,7), (6,3), (2,6), (3,1), (5,6), (1,2),
(4,7), (4,1), (5,7), (1,3), (7,1), (1,4), (8,4), (1,3), (8,5), (1,7), (6,1), (2,8), (8,2), (1,8), (8,1)

$\endgroup$
  • 1
    $\begingroup$ (3,4) to (5,3) and (5,3) to (3,2) are the same length. As are (8,8) to (1,6) and (1,6) to (8,4) $\endgroup$ – gtwebb Oct 14 '16 at 20:26
  • $\begingroup$ Maybe you selected the wrong turn between 2 lengths of same distance? $\endgroup$ – TSLF Oct 15 '16 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.