0

Show that, in a chessboard it is possible to traverse to any given square from another given square using a knight.

This was asked in a high school math competition.

Rhea
  • 87
  • Are you already familiar with proving things? – Magma Aug 04 '19 at 15:03
  • 1
    for the $8\times 8$ case and also generalizations see https://en.wikipedia.org/wiki/Knight%27s_tour – Jonas Lenz Aug 04 '19 at 15:07
  • @JonasLenz How should I write that in my answer script? I don't see any comprehensible calculations involved. – Rhea Aug 04 '19 at 15:10
  • @Magma, somewhat. – Rhea Aug 04 '19 at 15:10
  • @JonasLenz I'm not sure if they're referring to an 8 cross 8 board since a picture associated with the question depicts a 5 cross 5 board. But since they mention a chessboard, 8 cross 8 could be taken into consideration and proceeded with. – Rhea Aug 04 '19 at 15:21
  • 1
    @JonasLenz The question is about proving that the knight's graph is connected, which is much easier than a knight's tour, so I don't know why you would bring those up. – bof Aug 04 '19 at 15:22
  • Yeah, noticed this also. – Jonas Lenz Aug 04 '19 at 15:26
  • 1
    If you can prove it for a $4\times4$ chessboard then you can use that to proveit for any larger board. (Consider overlapping $times4$ boards.) – bof Aug 04 '19 at 15:27

2 Answers2

1

There are no calculations necessary here, math is not all calculations. What you need to do is provide a proof (an irrefutable explanation) for why it's possible.

One possible proof (only works on an 8x8 board):

There is a knight's tour on the 8x8 board (a cycle of knight moves that reaches all squares):

[Insert knight's tour here]

To get from square A to square B, the knight can just start at A and follow the tour until he's at square B.

Another possible proof (using an intermediate step, but works on any board size 4x4 or greater and does not require knowing a knight's tour):

Claim: It is always possible for the knight to reach the top left square.

If the claim is true, then a square can go from square A to square B by navigating from square A to the top left square, then from that square to square B by moving backwards along the path from B to the top left square.

Proof that the claim is true:

The knight can always go up-up-left or up-up-right until he reaches the top two rows. Then, while staying within those top two rows, the knight can go left-left-up or left-left-down to reach the left two columns. Now the knight is in one of the four squares in the top left corner.

From those squares, it's easy to reach the top left square, using the paths shown in the following image:

enter image description here

Magma
  • 6,270
  • Is a diagram necessary? – Rhea Aug 04 '19 at 15:40
  • 1
    Either a diagram or a verbal specification of the knight's tour or the paths will be necessary, otherwise the proof is incomplete. I recommend a diagram, since it's easier to draw as well as easier to understand by the judges. – Magma Aug 04 '19 at 15:42
  • The second proof is great. I think this would be a much better post if you deleted the first "proof", because it seems silly, really just assuming we already know what we're trying to prove... – David C. Ullrich Aug 06 '19 at 16:59
  • @DavidC.Ullrich Since OP does not seem that familiar with proofs, my answer is not about just having a nice proof, it's about demonstrating by examples what a proof is, what belongs to a complete proof, and that one can approach a problem in several ways. – Magma Aug 06 '19 at 17:48
  • Otherwise I'd only have included the second proof as you suggested. – Magma Aug 06 '19 at 17:49
-1

I need to admit that I originally misread the question. I think the easiest way to prove the statement is to show that given any square and any adjacent square there exists a sequence of moves such that the knight moves from the first to the second.

My feeling is that is enough (via some symmetry arguments) that starting on $a1$ the square $a2$ can be reached. I admit that I haven't thought this in detail, but it should be sufficient. And this can be done via the route $a1-b3-c1-a2$.

Jonas Lenz
  • 1,389
  • Why the downvote? – Jonas Lenz Aug 04 '19 at 15:32
  • I didn't downvote, but the symmetry arguments must be thought carefully because, for instance, your move $a1\to a2$ needs a whole $3\times 3$ borad at your disposal (and moving $a1\to b2$ needs a $4\times 4$), so you end up having issues starting from the second-to-last and third-to-last rank and file. –  Aug 04 '19 at 15:39
  • I am pretty sure that it should be sufficient that any square is a corner of a $3 \times 3$ board or am I wrong? – Jonas Lenz Aug 04 '19 at 15:44
  • You need space in the direction you are moving towards. At least one extra rank/file. –  Aug 04 '19 at 15:48
  • That's more or less what I meant by symmetry. For any two adjacent (not diagonally) squares on a $4 \times 4$ board it is clear that there exists a $3\times 3$ board such that one is a corner and the other one is also on the board. – Jonas Lenz Aug 04 '19 at 15:53
  • I mean, try going $g5\to h5$ with that procedure and see what happens. Or $g7\to h8$. –  Aug 04 '19 at 16:01
  • Via rotation is the nothing else then going from $a1$ to $a2$. Note that if I don't "have enough space" in one direction, I might just go backwars as being on $4\times 4$ guarantees having enough space in some direction. – Jonas Lenz Aug 04 '19 at 16:15