Jimmy the grasshopper is sitting on a corner square of a rectangular board, where . To describe the hops Jimmy can make, we label the squares of the board by pairs of positive integers , where and .
Jimmy can hop in both directions between squares and if either
How many squares of the board can Jimmy reach by hopping repeatedly?
Solution
Let , then the answer will be .
where the second coordinate is to be understood modulo . We use these symbols to denote sequences of moves. For example, means followed by three consecutive , followed by two consecutive . Note that we read this from right to left.
Lower Bound. We first show that Jimmy can reach at least squares. Starting at the corner square , the sequence lets Jimmy travel as follows: . This means that corresponds to the addition of . Hence, iterating we see that corresponds to the addition of to the column number and no change in the row number.
The congruence , has a solution if and only if . We can always pick a positive solution in its congruence class modulo . Therefore, Jimmy can reach squares in row 1, namely those in columns .
Through the sequence , Jimmy has visited each row exactly once before coming back to row 1. Considering the part of the sequence that starts and ends at row , the same argument as above shows that Jimmy is able to hop on squares on row as well. Hence, Jimmy can reach at least squares in total.
Suppose Jimmy starts at square with move , where are integers. Let and . Then Jimmy ends up on the square , where the second coordinate is to be taken modulo . If Jimmy ends up in row , we have , hence and and there exists an integer such that . The column number is then congruent to
Hence, Jimmy can only move from square to square if for some integer . Such a exists exactly when . As any two squares Jimmy reaches during his entire journey are connected by a sequence of moves, it follows that Jimmy can reach at most squares in each row. Hence, the maximum number of squares Jimmy can reach is .