combinatoricsproblem solving
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 6×8 square.
Here’s a proof/sketch for sufficiently large n. I think $n \geq 4 * 5 + 3 = 23$ for operation (c). You may be able to apply the new scoring to the Lemma, so you then only need (c) to be nonnegative, in which case $2(n-2) - 8 \geq n - 1$, so $n \geq 11$. Also, in the new scoring, diagonals are a bonus, unless it's short, so you may be able to get $2(n-2) - 4 \geq n - 1$, or $n \geq 7$. This is my first post, so I hope it's clear.
The main idea is to look at the queens in each row/col/diagonal and to show that if the arrangement doesn’t satisfy certain properties, then we can locally improve the arrangement, by which I mean that we will find a different arrangement that is not worse. The second key idea is that sometimes, it’s hard to locally improve an arrangement. However, you can then overestimate the score (the score is the number of non-attacking moves) for each arrangement so that the best arrangement has the same score, but in a way that each non-maximal arrangement can now be improved.
There are 3 operations we can apply on a queen in a row/column/diagonal, which we call a slice.
(a) It is sandwiched between 2 queens (not necessarily directly) and we delete it.
(b) It is the last/first queen in that slice, we delete it and add it to its end of the slice.
(c) It is the only queen in that slice, and we delete it and put 2 queens on both ends of that slice.
These operations can be applied simultaneously on a single queen along different slices in the natural way.
Lemma. We can assume there is no row or column with only one queen (or else we can improve the arrangement).
Proof. If there is, then we apply operation (c) in that row or column and in every other slice containing the queen, we apply (a), (b), or (c) as appropriate. Note that (c) increases the score for a row/col by an order of n, i.e. from $n-1$ to $2(n-2)-8$. (a) increases by 2, and (b) can only worsen the score by at most 4 (+1 for that slice, and -5 since now queens can’t move into the edge where the queen was pushed to). Since n is sufficiently large, (c) outweighs (a) and (b), so the arrangement is non-worsened.
Proof of theorem. Suppose a diagonal has $k$ squares. Then, if $k = n$, which we call a long diagonal, or $k = 2$, a short diagonal, we score it normally. $k = 1$ is naturally scored 0. For $k = 3$, we ignore the middle of the diagonal when scoring (so having both ends is 2, one end is 2, and no ends is 0). Otherwise, let the number of queens on the ends of that diagonal be $0 \leq q \leq 2$. We score it as $2(k-2) - 2 + q$ instead. Note that the new score is always better or the same than the original score.
Now, suppose we have a queen not at the edge of the board. (a) always increases the score by 2. For (b), we have a few cases.
The slice is a row/col, and the end of the slice is not in a long or short diagonal. Then we get +1 along that slice, +2 from the added queen for the diagonals (unless one of them is the k = 3 diagonal, in which case we only get one diagonal, so +1), and at most -2 along the slice for the new queen, for a total of +1 (or + 0).
The slice is a row/col and the end of the slice is in a short diagonal and the queen is not on a long diagonal. Then we get +2 along the slice, +1 from the non-short diagonal, potentially -1 from the short diagonal, and -2 along the edge slice, for a total of +0.
The queen is on a long diagonal and the end is on a short diagonal. This is a special case where we look at the combination of some of the operations we apply on that queen. Label the corner D, the queen’s square as A, and the other two squares in the 2x2 defined by A and D as B and C. We now cover all the cases for A, B, C, and D. The ending state is B, C, and D are all occupied and A is unoccupied.
The slice is the long diagonal. We already covered when the queen is one away from the corner in case 3, so now the queen is 2 away. Either way, applying (a) or (b) increases by 2 along the slice, and decreases by at most 2 along the edge slices. So, the total is +0.
With all the cases (note that we didn't need to consider slices that were non-short/long diagonals), we see that we can apply the operations to any queen in the middle to push it to all the edges without worsening the score. But from the Lemma, there’s at least 2 in each row/col, so the whole border except for the corners have queens in them. From there, it is clear that filling in the corners improves the (new) score. So for n sufficiently large, the best is to have all queens along the border, for a total of $8(n-2)^2$ (which has the same score in both systems).
Yes, your reasoning is correct. As for a knight's tour from one corner to the other corner on the same edge, here's a very blurry image I found on the Internet. (The two large circles indicate start and finish.)
Best Answer
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: