Maths Olympiad Prep

Library / /451 of 462

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Ireland

Jimmy the grasshopper is sitting on a corner square of a rectangular 9×n9 \times n board, where n8n \ge 8. To describe the hops Jimmy can make, we label the squares of the board by pairs of positive integers (a,b)(a, b), where 1a91 \le a \le 9 and 1bn1 \le b \le n.
Jimmy can hop in both directions between squares (a,b)(a, b) and (a,b)(a', b') if either
bb+7(modn)anda=a+2,orbb+2(modn)anda=a+7. b' \equiv b + 7 \pmod{n} \quad \text{and} \quad a' = a + 2, \quad \text{or} \\ b' \equiv b + 2 \pmod{n} \quad \text{and} \quad a' = a + 7.
How many squares of the board can Jimmy reach by hopping repeatedly?

Solution

Let g=gcd(45,n)g = \gcd(45, n), then the answer will be 9n/g9n/g.

V=(2,7)i.e. hopping from (a,b) to (a+2,b+7)V1=(2,7)i.e. hopping from (a,b) to (a2,b7)H=(7,2)i.e. hopping from (a,b) to (a+7,b+2)H1=(7,2)i.e. hopping from (a,b) to (a7,b2), \begin{align*} V &= (2, 7) \quad \text{i.e. hopping from } (a, b) \text{ to } (a + 2, b + 7) \\ V^{-1} &= (-2, -7) \quad \text{i.e. hopping from } (a, b) \text{ to } (a - 2, b - 7) \\ H &= (7, 2) \quad \text{i.e. hopping from } (a, b) \text{ to } (a + 7, b + 2) \\ H^{-1} &= (-7, -2) \quad \text{i.e. hopping from } (a, b) \text{ to } (a - 7, b - 2), \end{align*}
where the second coordinate is to be understood modulo nn. We use these symbols to denote sequences of moves. For example, V2H3VV^2H^{-3}V means VV followed by three consecutive H1H^{-1}, followed by two consecutive VV. Note that we read this from right to left.

Lower Bound. We first show that Jimmy can reach at least 9n/g9n/g squares. Starting at the corner square (1,1)(1, 1), the sequence S=H1V3H1V4S = H^{-1}V^3H^{-1}V^4 lets Jimmy travel as follows: (1,1)(3,8)(5,15)(7,22)(9,29)(2,27)(4,34)(6,41)(8,48)(1,46)(1, 1) \mapsto (3, 8) \mapsto (5, 15) \mapsto (7, 22) \mapsto (9, 29) \mapsto (2, 27) \mapsto (4, 34) \mapsto (6, 41) \mapsto (8, 48) \mapsto (1, 46). This means that SS corresponds to the addition of (0,45)(0, 45). Hence, iterating SS we see that SkS^k corresponds to the addition of 45k(modn)45k \pmod n to the column number and no change in the row number.
The congruence b1+45k(modn)b \equiv 1 + 45k \pmod{n}, has a solution kk if and only if gb1g \mid b - 1. We can always pick a positive solution kk in its congruence class modulo nn. Therefore, Jimmy can reach n/gn/g squares in row 1, namely those in columns b=1+mg,0m<n/gb = 1 + mg, 0 \le m < n/g.
Through the sequence SS, Jimmy has visited each row exactly once before coming back to row 1. Considering the part of the sequence S2S^2 that starts and ends at row aa, the same argument as above shows that Jimmy is able to hop on n/gn/g squares on row aa as well. Hence, Jimmy can reach at least 9n/g9n/g squares in total.

Suppose Jimmy starts at square (a,b)(a, b) with move Vp1Hq1Vp2Hq2VprHqrV^{p_1}H^{q_1}V^{p_2}H^{q_2}\cdots V^{p_r}H^{q_r}, where pi,qip_i, q_i are integers. Let p=p1+p2++prp = p_1 + p_2 + \cdots + p_r and q=q1+q2++qrq = q_1 + q_2 + \cdots + q_r. Then Jimmy ends up on the square (a+2p+7q,b+7p+2q)(a + 2p + 7q, b + 7p + 2q), where the second coordinate is to be taken modulo nn. If Jimmy ends up in row aa, we have 2p+7q=02p + 7q = 0, hence 2q2 \mid q and 7p7 \mid p and there exists an integer kk such that p=7k,q=2kp = 7k, q = -2k. The column number is then congruent to
b+7p+2qb+77k22kb+45k(modn). b + 7p + 2q \equiv b + 7 \cdot 7 \cdot k - 2 \cdot 2 \cdot k \equiv b + 45k \pmod{n}.
Hence, Jimmy can only move from square (a,b)(a, b) to square (a,c)(a, c) if cb45k(modn)c - b \equiv 45k \pmod{n} for some integer kk. Such a kk exists exactly when gcbg \mid c - b. 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 n/gn/g squares in each row. Hence, the maximum number of squares Jimmy can reach is 9n/g9n/g.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.