2013 USAMO Problems/Problem 2
For a positive integer plot equally spaced points around a circle. Label one of them , and place a marker at . One may move the marker forward in a clockwise direction to either the next point or the point after that. Hence there are a total of distinct moves available; two from each point. Let count the number of ways to advance around the circle exactly twice, beginning and ending at , without repeating a move. Prove that for all .
We label the points in clockwise order as , , , \dots, , where point is the same as point . We start and end at point , and we must cross over it, either by visiting it again, or else by making the move from point to point . We interpret each of these cases in terms of tiling. In each move, we either move one or two points clockwise, so we can think of each move as a or tile. If the point is visited in the middle, then the first cycle around the circle can be thought of as a tiling of a board, and the second cycle around the circle can also be thought of as a board. We place this second board directly below the first board. Therefore, in this first case, we wish to find the number of tilings of two boards, and to guarantee that no move is repeated, we cannot have two tiles of the same type lying directly atop each other in the board. Suppose there are such tilings. It can easily be computed that and as shown below. In the second case, where we pass by point by moving from point to point , we can similarly think about it in terms of tiling two rows of boards, but we remove the last square in the first row and the first square in the second row to make sure that we jump from point to point . Suppose that we can tile such boards in ways. It can be easily computed that and as shown below. Since these are the only two possible cases, we see that
For the sake of convenience in determining recurrence relations, we define another type of board with two boards where a specific corner is removed (without loss of generality, we place this in the lower left hand corner). Let be the number of ways to tile such a board without placeing two of the same type of tile atop each other. Once again, we compute that and as shown below. We can determine reccurence relations for , , and in terms of each other. For , note that a tiling can end in one of the three following ways such that the rest of the board can be tiled without restriction (the placed tiles are shaded). In the first, second, and third cases, we see that we can tile the rest of the board in , , and ways, respectively. Hence for , we see that For , note that a tiling can end in one of the three following ways such that the rest of the board can be tiled without restriction. In the first, second, and third cases, we see that we can tile the rest of the board in , , and ways, respectively. Hence for , we see that For , note that a tiling can end in one of the two following ways such that the rest of the board can be tiled without restriction.
In either case, we are left with a board with a corner removed, hence we can tile the rest of the board in ways in each case. Hence for , we see that Subtracting (3) from (2), we find that Therefore, if , then . Since and , we see that for all . Therefore, (2) can be rewritten as and (4) can be rewritten as Now by (1), we know that In particular, , so the statement is true for . Then by (7), and then substituting (5) and (6) (where these are valid for ), we find But then by (5), and then substituting and (by (6), and these are valid for ), we find We substitute this into (8), finding that for , Therefore, if , then . We already know that . Also, we can compute that Hence . So as , we find that . Then we can use (9) for to find by induction that for all .
We choose the tilings for the first and second pass around the circle simultaneously. As we tile both passes, our state is defined by whether or not we are in a continuation of a length 2 block on the first and second pass. We can't be in a continuation of a length 2 block on both passes, since that would mean we used the same move on the same block on both passes. Thus we have three states: (non-continuation, non-continuation), (non-continuation, continuation), and (continuation, non-continuation), where the elements of each tuple refer to the first and second pass respectively. Listing out the state transitions (while following the rule that we can't use the same move on both passes, and that a continuation must become a non-continuation), we get the transition matrix , where is the ones matrix, and is the identity. We have that . The first term represents the case where we end the first pass at point , and the second term represents the case where we jump over point when finishing the first pass. Thus it simply remains to compute . We have . Thus . Thus, , as desired.