Emilia is playing a board game where each player needs to move their game piece along the black roads from the beach in the bottom-left corner to the house in the top-right corner. The black dots represent intersections where roads meet.
In each turn a player is allowed to move their piece along a road until it reaches an intersection. Then it’s another player’s turn.
After Emilia finished the game, she realized that at every intersection she had turned either left or right; she never continued straight along the direction she came from in her previous turn. As well, she never went along the same part of a road more than once.
What is the fewest number of turns Emilia could have had during the game?
This problem was inspired by a past Beaver Computing Challenge (BCC) problem.
To get from the beach in the bottom-left corner to the house in the top-right corner, Emilia must have passed through at least one of the four numbered roads shown.
We will find the length of the shortest route through each of the four roads from the beach to the house, and then determine the shortest route overall. The length of this route will then be equal to the fewest number of turns Emilia could have had during the game, because in each turn she moved along the road until she reached the next intersection.
Some details, for the sake of brevity, will be omitted from the solution and left for the solver to consider further. In the solution, turns will be described in terms of north, south, east, and west, where north points to the top of the page.
Shortest Route Through Road \(\bf 1\):
If Emilia traveled through road \(1\), then for the fewest number of turns, she could not have traveled on the roads marked with an \(X\) in the diagram shown, because she never went straight through an intersection. Similarly, the roads that she must have traveled on are marked with a \(\checkmark\). The route shown on the diagram is the shortest route. This route has a length of \(15\).
In the part of the route between the beach and road \(1\), the shortest route has a length of \(4\) and goes north - east - north - west. It would also be possible to extend this route by going north - east - south - east - north - west - north - west, but this route is clearly longer. There is no shorter route starting from the beach that goes east first and passes through road \(1\). In traveling from road \(1\) to the house, the shortest route is shown and has a length of \(10\). At some points along this route, alternate choices can be made but these choices lead to invalid situations or lengthen the route. The solver may wish to confirm this.
Shortest Route Through Road \(\bf 2\):
If Emilia traveled through road \(2\), then for the fewest number of turns, she could not have traveled on the roads marked with an \(X\) in the diagram shown, because she never went straight through an intersection. Similarly the roads that she must have traveled on are marked with a \(\checkmark\). The route shown on the diagram is the shortest route. This route has a length of \(13\).
In the part of the route from the beach to road \(2\), the shortest route has a length of \(9\). In traveling from road \(2\) to the house, the shortest route has a length of \(3\). At some points along the route shown through road \(2\), alternate choices can be made but these choices either lead to invalid situations or lengthen the route. The solver may wish to confirm this.
Shortest Route Through Road \(\bf 3\):
If Emilia traveled through road \(3\), then for the fewest number of turns, she could not have traveled on the roads marked with an \(X\) in the diagram shown, because she never went straight through an intersection. Similarly the roads that she must have traveled on are marked with a \(\checkmark\). The route shown on the diagram is the shortest route. This route has a length of \(17\).
In the part of the route from the beach to road \(3\), the shortest route has a length of \(13\). In traveling from road \(3\) to the house, the shortest route has a length of \(3\). At some points along the route from the beach to road \(3\) and also from road \(3\) to the house, alternate choices can be made but these choices either lead to invalid situations or lengthen the route. The solver may wish to confirm this.
Shortest Route Through Road \(\bf 4\):
If Emilia traveled through road \(4\), then for the fewest number of turns, she could not have traveled on the road marked with an \(X\) in the diagram shown, because she never went straight through an intersection. Similarly the roads that she must have traveled on are marked with a \(\checkmark\). The route shown on the diagram is the shortest route. This route has a length of \(15\).
In the part of the route from the beach to road \(4\), the shortest route has a length of \(12\). In traveling from road \(4\) to the house, the shortest route has a length of \(2\). At some points along the route from the beach to the house through road \(4\), alternate choices can be made but these choices either lead to invalid situations, lengthen the route, or have the same length. The solver may wish to confirm this.
After examining the four possible cases, the shortest route has a length of \(13\) and passes through road \(2\). Thus, the fewest number of turns Emilia could have had during the game is \(13\).