7
$\begingroup$

Suppose a land with a finite number of castles. Each castle is connected (via roads) with exactly 3 other castles.

One knight leaves from his castle and starts travelling. He moves in the following way. 1) When he begins from his home castle (first step) he randomly chooses a road to take. 2)For the second step he randomly chooses the left or right road, but can't go back. 3)Every other step is deterministic. If he came to this castle by taking the left road next he takes the right and vice versa and can never just go back.

Prove that he will eventually return to his original castle.

$\endgroup$
  • $\begingroup$ Can he visit castles multiple times? Does "every other step" mean all steps after the second, or every odd numbered step except 1, (3,5,7...n)? $\endgroup$ – CG. Jan 14 at 14:54
  • $\begingroup$ yes he can visit the same castle multiple times and it means every step after the second $\endgroup$ – Kostas Ferentinos Jan 14 at 15:05
6
$\begingroup$

First of all,

since there are only finitely many castles and finitely many roads, there will necessarily be a repetition where the knight arrives at castle C by road R1 and leaves it by road R2 on two occasions. (After which, clearly everything between those two occurrences will repeat for ever.)

And now the point is that

the process is reversible: if you know that the knight went ...-R1->C-R2->... then you can continue the path backwards as well as forwards

which means that

if he ends up on an endlessly repeating cycle then he must in fact have started on that cycle, because extending his route backwards can't leave it.

$\endgroup$
  • $\begingroup$ I don't see how the above reasoning proves that if the knight moves in a loop, this loop will contain the starting castle.I can imagine a loop being created later on in his trip that doesn't include the starting castle. $\endgroup$ – Kostas Ferentinos Jan 15 at 15:18
  • $\begingroup$ Then I'll edit it to try to make it clearer. $\endgroup$ – Gareth McCaughan Jan 15 at 15:19

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.