12
$\begingroup$

STATEMENT: A dolphin is a special chess piece that can move one square up, OR one square right, OR one square diagonally down and to the left. Can a dolphin, starting at the bottom-left square of a chessboard, visit each square exactly once?

QUESTION: How would one approach this type of problem. It seems that whatever way the dolphin moves the maximum moves always involve the dolphin to traverse an 6x8 square.

$\endgroup$
  • $\begingroup$ Yeah, my intuition and scratch work seems to suggest that it s impossible. But how would you give a formal proof of its impossibility? $\endgroup$ – Enigma Dec 7 '14 at 1:58
  • $\begingroup$ No, it was a question suggested by a professor. $\endgroup$ – Enigma Dec 7 '14 at 2:01
  • $\begingroup$ I have a path it can follow that hits all but one square, so the question becomes then how can we be sure that it can't hit all, $\endgroup$ – JMoravitz Dec 7 '14 at 2:08
  • $\begingroup$ I would hint at looking at this from a graph theory intuition. The related Knight's Tour asks the question if there is a Hamiltonian Circuit on the board based on using a Knight. So we use a Dolphin and seek to find a Hamiltonian Circuit. $\endgroup$ – ml0105 Dec 7 '14 at 2:53
19
$\begingroup$

Hint: Instead of the usual black/white pattern, color the square $(a,b)$ either green, blue, or yellow, according to the remainder of $a+b$ (mod $3$). Each color forms a diagonal stripe going from the upper left to the lower right, with the stripe pattern going green, blue, yellow, $\dots$ as you move up or to the right. Think about how this coloring relates to a Dolphin's movement, and what a tour of the board would look like in terms of these colors.

Addendum: For your viewing pleasure:

enter image description here

$\endgroup$
  • $\begingroup$ Very nice. To complete the proof then will also require noting that the starting square matters. If you were to start on one of the blue squares it is indeed possible to hit every space. $\endgroup$ – JMoravitz Dec 7 '14 at 2:28
  • $\begingroup$ @JMoravitz At least, the coloring argument would not preclude the existence of a tour. Have you found a Dolphin tour starting at, say, the lower right blue square? $\endgroup$ – Mike Earnest Dec 7 '14 at 2:32
  • $\begingroup$ Was working on something else entirely. Yes, in fact, there is a path starting from the lower right blue, assuming your definition is that it need not be a closed walk or need to "arrive at" the starting square (having begun there is good enough). Posted below. $\endgroup$ – JMoravitz Dec 7 '14 at 4:29
  • $\begingroup$ I still can't completely formulate the final argument. Using this coloring we see that for every diagonal movement it has to be superseded by a right movement and two up movements. This give us a 2-2-1 choice of colors. I also know that there is 20-21-22 groupings of distinct colors Green-Yellow-Blue. But what is the contradiction I am supposed to arrive at? $\endgroup$ – Enigma Dec 7 '14 at 4:47
  • 1
    $\begingroup$ @S.S See below for the punchline to the proof. In fact there are 21 green, 21 yellow, and 22 blue spaces. Regardless which move is chosen, you will move $g\to b$, from $b\to y$, and from $y\to g$. The contradiction is that having started on a green (or yellow) square, you will not have the ability to continue movement after having reached the 21st blue (or green resp.) you come to. $\endgroup$ – JMoravitz Dec 7 '14 at 4:53
10
$\begingroup$

In response to Mike Earnest's question regarding the existence of a Dolphin Tour from alternate starting points: If we started at a blue square, say for example the bottom right corner instead, dolphintour

The punchline of the proof is that there are in fact 21 yellow, 21 green, and 22 blue squares. Any sequence of moves will be (...,green,yellow,blue,...) repeated. Having started from a green square, after reaching the 21st blue, you will no longer have another green square to go to, and so you cannot continue until reaching the 22nd blue.

In a similar fashion, it is then impossible to reach every square having started at a yellow square either.

Having started at a blue however, as shown above, can be possible (depending on the square), and if is impossible for a specific starting square, would require a different argument.

another dolphin tour

$\endgroup$
  • $\begingroup$ Very nice :) I imagine this is the exceptional case, and most blue squares are not the starting point of tours. $\endgroup$ – Mike Earnest Dec 7 '14 at 8:01
  • 1
    $\begingroup$ After playing with it for a while, I have in fact found dolphin tours starting from each of the blues from the bottom two rows and haven't yet checked the others. I'm not yet convinced if any blues don't have a dolphin tour. $\endgroup$ – JMoravitz Dec 7 '14 at 12:49

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.