SCHOOL OF COMPUTER SCIENCE

Puzzle 17- The Wandering Toad

  Solution

Label each edge that Tamara walks as (e, d, t) where d is the direction along the edge that Tamara walks, e is the edge and t is the turn the toad made to reach the edge (either left or right).

Observe that if Tamara executes (e, d, t) on step k > 1 then the triple (e', d'.t') that she executes on step k -1 is determined. t' is the opposite of t. There are two edges incident with start of edge e under direction d and only one is consistent with t'. And then d' is also now determined. Since there are only a finite number of such triples, Tamara must eventually repeat one of the triples, assuming that she doesn’t stop unless she reaches home. This must be the first triple, since otherwise the prior one will also have been repeated. Acknowledgement Mike Schuresko and Brian Thompson provided correct solutions.

< back to the main puzzle page