Let $n \geq 2$ be an integer. A lead soldier is moving across the unit squares of a $n \times n$ grid, starting from the corner square. Before each move to the neighboring square, the lead soldier can (but doesn't need to) turn left or right. Determine the smallest number of turns, which it needs to do, to visit every square of the grid at least once. At the beginning the soldier's back is faced at the edge of the grid.
Problem
Source: Polish Math Olympiad 2023 2nd stage P2
Tags: combinatorics, grid
Hanser-Ling
26.02.2023 15:42
we can suppose that the soldier is at the top-right edge of the grid firstly, we can easily get an answer of (2n-2) by making the soldier turn right/ left at each end of the line(always go downwards),the turn right/left at the beginning of a new line,the soldier an go through every line of the grid with (2n-2)turns now we prove that there can't be less than( 2n-2） turns we mark each square that the soldier turns into red then prove: except the first line or the last line the soldier passes,there are no less than two red squares in each line, or else the total turn is more than（2n-2） if there don't exist a line that has less than two red squares the the total turns is obviously no less than(2n-2) if there is one,and it has one red square, then it is obviously the last line the soldier goes through(no more turns after the only red square) if there is one, and it has no red squares, then the only way for the soldier to pass the squares in this special line is vertically go pass one. note that each vertical pass only passes one square, and it takes at least two turns to turn the direction from a vertical one to a vertical one,so there is more than 2*(n-1)+1 turns(the original direction is horizontal),which is more than (2n-2). QED.