Christmas Streak 31/88: A Bit Farther

Tom is jumping around a 4 × 4 4\times4 grid of circles with the following conditions:

  • He starts from any of the 16 circles.
  • He always jumps in a straight line from one circle to any other circle.
  • Each subsequent jump is farther than the last.
  • He doesn't visit a circle already visited.

The maximum number of circles that he can step on is m , m, and the number of ways of doing so is r . r.

Find the value of m r . mr.


Note: The grid is fixed on the ground, so a method obtained by rotating another is considered different.


The answer is 240.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Andy Hayes
Nov 2, 2017

There are a total of 9 possible jumps, listed below in order of shortest to longest:

  • Length 1 1 : ( 1 , 0 ) (1,0)
  • Length 2 \sqrt{2} : ( 1 , 1 ) (1,1)
  • Length 2 2 : ( 2 , 0 ) (2,0)
  • Length 5 \sqrt{5} : ( 2 , 1 ) (2,1)
  • Length 2 2 2\sqrt{2} : ( 2 , 2 ) (2,2)
  • Length 3 3 : ( 3 , 0 ) (3,0)
  • Length 10 \sqrt{10} : ( 3 , 1 ) (3,1)
  • Length 13 \sqrt{13} : ( 3 , 2 ) (3,2)
  • Length 3 2 3\sqrt{2} : ( 3 , 3 ) (3,3)

It turns out they are all possible in sequence. I found it easier to work backwards from the longest possible jump to the shortest possible jump. The number of ways to jump this way is the same as what is asked in the problem.

The longest possible jump is from opposite corners. Since there are 4 corners, there are 4 choices for placing the start of the longest jump. Then, for each of these choices, there is only one circle to jump to.

Now there are 2 possible choices for the next longest jump (either circle adjacent to the 1 circle).

It may seem that there are now two choices for the next longest jump, but placing the 4 in the bottom left corner will not allow us to move exactly 3 spaces in the jump afterwards. Thus, there is only one choice for the next jump, and then only one choice for the jump afterwards.

For the next several jumps, there is only one possible location for each.

Now, there are 3 places the last jump can go to (any of the open circles adjacent to the 9 circle).

By rule of product, there are 4 × 2 × 3 = 24 4\times 2 \times 3 = 24 ways to jump this sequence. Thus, the answer is 10 × 24 = 240 . 10 \times 24 = \boxed{240}.

Moderator note:

This is related to "Distance Puzzles" which (as far as I'm aware) first surfaced in 2000 at the World Puzzle Championship. The idea is that by restricting which circles can be used on the grid, we can force a unique solution. The actual puzzle in the competition (written by Erich Friedman) is shown below.

Place the numbers 1 through 12 in the circles so that the distance between successive pairs (measured between centers of corresponding circles) is increasing.

Now that I see the answer, the question is poorly worded. The move (2,1) is not "diagonal". I would say "he can jump from any circle to any circle".

William Doran - 3 years, 7 months ago

Log in to reply

Yes, I found this ambiguous as well. If the allowed jumps are just along a row, a column, or along a diagonal that is at 45 degrees with respect to the grid, then I find that the max length is 7, and there are 96 ways to do it. Thus 7 * 96 = 672, for "m * r".

Rob Brott - 3 years, 7 months ago

Same solution! Good problem also.

Kelvin Hong - 3 years, 7 months ago

Got this solution too, a nice problem with a great solution :)

FrEshy Pisuttisarun - 3 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...