5
$\begingroup$

A pawn moves across $n\times n$ chesssboard so that in one move it can shift one square to the right, one square upward, or along a diagonal down and left. Can the pawn go through all the squares on the board, visiting each exactly once, and finish its trip on the square to the right of the initial one?

I understood this to mean that the following are the three valid moves V for the pawn P:

-------------
|   | V |   |
-------------
|   | P | V |
-------------
| V |   |
-------------

I proved this situation to be impossible in this way: let the pawn's moves - up, right, diagonal left - be represented by vectors on the 2D plane respectively: $\hat{A}=(0,1),~\hat{B}=(1,0),~\hat{C}=(-1,-1)$, then their linear combination $a\hat{A}+b\hat{B}+c\hat{C}=(1,0)$, which is the required net displacement for the pawn. Thus we see that $a=c$ and $b=c+1$. Thus the total number of moves is $a+b+c=3c+1$, which we know should be equal to $n^2-1$. Thus, $n^2=3c+2$ which we know is impossible for integral $c,n$.

However, our Prof wishes us to do this question via invariant properties instead. I tried to make the parity of the sum of the coordinates invariant. However, it changes to even on moving right or up, while remains same on moving diagonally. Hence, this property can't be invariant. I also tried to think of distances of point from origin, parity of difference of coordinates, ...without success.

What invariant property am I missing? (only hints please)

$\endgroup$
  • $\begingroup$ Did he clarify whether he meant invariant w.r.t. $n$ or w.r.t. the square? Your question suggests the latter, but are you guessing it did he clarify - just for clarity :-) $\endgroup$ – Devashish Kaushik Sep 23 '18 at 5:58
  • $\begingroup$ @DevashishKaushik He did not clarify :( I believe we need to prove that the given pawn moves don't lead to the required position for any $n\in Z\geq2$. $\endgroup$ – Gaurang Tandon Sep 23 '18 at 6:10
  • $\begingroup$ On a 4 by 4 one can tour starting at lower right and ending at upper right, i.e. start and end at opposite colors. So we can't rule out adjacent start and end via showing start and end same color. $\endgroup$ – coffeemath Sep 24 '18 at 7:58
1
$\begingroup$

Since the only way to move left or down is the diagonal (from where the pawn is to the square one to its left and one down) let the number of such moves be $k.$ Now suppose the pawn ends one to its right, there is no net up or down movement, mening the number of up moves is also $k.$ Since it also ends up one square to its right, there must be one more right move than left move, i.e $k+1,$ since there are $k$ left moves and need $k+1$ right moves to end up one to the right of start.

Hence the total number of moves is $3k+1.$ Now since it's an $n \times n$ square there are $n^2-1$ moves in the tour. (Note this is a path tour not a closed tour since we want to stop one square to the right of start.) Conclusion $3k+1=n^2-1$ or $n^2=3k+2.$ But no square is $2$ mod $3.$ So it cannot be done.

If we try for landing one square left of the start point, we can similarly conclude $n$ must be divisible by $3.$ I have no argument to rule that out, but after all that wasn't asked by the question. I suspect there are no such walks, even for $n$ a multiple of $3.$

$\endgroup$
  • $\begingroup$ Hi, thanks for your answer. However, I don't understand what invariant you have used in this solution? As I stated in the question, our prof expected us to solve this problem by using invariant method. Please clarify. Thanks! $\endgroup$ – Gaurang Tandon Sep 25 '18 at 5:52
  • $\begingroup$ @GaurangTandon -- Parity is basically mod 2 argument. My approach used a mod 3 argument. Did you get why number of moves is $3k+1$ and also $n^2-1$? If so it boils down to showing $n^2=3k+2$ is impossible. That can bee shown by trying the three possible cases $n=3t,n=3t+1,n=3t+2$ and squaring these, then by rearrangement showing each value of $n^2$ is either of form $3u$ or $3u+1.$ $\endgroup$ – coffeemath Sep 25 '18 at 9: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.