CEMC Banner

Problem of the Week
Problem E
The Long Way Home

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.

A rectangular grid of dots with line segments joining certain pairs of adjacent dots in the grid. A beach umbrella is placed at one corner of the grid and a house is placed at the opposite corner.

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.