Problem A1, Putnam Exam 2021

Original Statement:

A grasshopper starts at the origin in the coordinate plane and makes a sequence of hops.  Each hop has length 5, and after each hop the grasshopper is at a point whose coordinates are both integers:  thus, there are 12 possible locations for the grasshopper after the first hop.  What is the smallest number of hops needed for the grasshopper to reach the point (2021,2021)?

Solution:

STEP/OBSERVATION 1:  It is possible for the grasshopper to reach the point (2021, 2021) in 578 hops because 

(2021 , 2021) = 288 (4,3) + 288 (3,4) + (5,0) + (0,5).

STEP 2:  Claim:  It is not possible for the grasshopper to reach the point (2021, 2021) in fewer than 578 hops.  (Therefore, the smallest number of hops needed is 578, and this is the answer to the problem.)

Proof of the Claim:  Assume the grasshopper can reach the point (2021, 2021) in some number of hops n with n < 578.  After each hop the grasshopper will be at some point (x, y), and we can think of x and y as functions of the number of hops the grasshopper has taken up to that point.  Thus, the 12 possible locations for the grasshopper mentioned in the problem are possible values of (x(1), y(1)), after two hops the grasshopper will be at (x(2), y(2)), and so on.  Let us consider the projection p(j) onto the line y = x of the grasshopper’s position (x(j), y(j)) after the j-th hop.  That is, 

p(j) = [ (x(j), y(j)) . (1/sqrt(2), 1/sqrt(2)) ] (1/sqrt(2), 1/sqrt(2))

and the distance d(j) of the projection point p(j) to the origin (0,0).  Notice that 

d(j) = [ x(j) + y(j) ]/sqrt(2) 

and by the triangle inequality 

d(j+1)  ≤ d(j) + dist( p(j), p(j+1) ).

On the other hand,

p(j+1) - p(j) = [ (x(j+1) - x(j), y(j+1) - y(j) ) . (1/sqrt(2), 1/sqrt(2)) ] (1/sqrt(2), 1/sqrt(2)).  

This is the projection of the difference (x(j+1), y(j+1)) - (x(j), y(j)) onto the line y = x.  Since (x(j+1), y(j+1)) - (x(j), y(j)) is one of the 12 possible locations of the grasshopper after the first hop, namely, (±5, 0), (4, ±3), (3, ±4), (0, ±5), (14, ±3), and (-3, ±4), we can check the lengths of the projections of these points.  They are either 5/sqrt(2), 1/sqrt(2), or 7/sqrt(2).  
Taking the largest possible value we find 

dist( p(j), p(j+1) ) ⩽ 7/sqrt(2), 

so 

d(j+1)  ≤ d(j) + 7/sqrt(2)

and by induction  d(j) ⩽ 7j/sqrt(2).  Since n ⩽ 577, this means in particular, 

d(n) ⩽ 7n/sqrt(2) ⩽ 7 ( 577)/sqrt(2) = 4039/sqrt(2).

But we have assumed (x(n), y(n)) = (2021, 2021), so d(n) = 4042/sqrt(2).  Since 4039 < 4042 we have a contradiction, meaning of course that it is not possible for the grasshopper to reach the point (2021, 2021) in n < 578 hops.

Follow Up

I'm sort of tired of talking about “hops,” so I’m going to talk about “moves” instead.  If you would like some cutesy imagery to go along with “moves,” you can think of a primitive board game vaguely resembling “go” and played on a coordinate plane by one player.  The player starts with a stone at the origin and can make successive “moves” of length 5 with the result of the move being restricted to the integer lattice.  After the first move the possible resulting positions are shown in blue below along with the circle of radius 5.

moves={{5,0},{4,3},{3,4},{0,5},{-3,4},{-4,3},{-5,0},{-4,-3},{-3,-4},{0,-5},{3,-4},{4,-3}};
firstmoveright=Table[moves[[j]]+{5,0},{j,1,12}];
Show[ListPlot[moves,PlotStyle->{Blue,AbsolutePointSize[6]},AspectRatio->Automatic],ParametricPlot[5 {Cos[t],Sin[t]},{t,0,2 Pi},PlotStyle->Blue],ListPlot[firstmoveright,PlotStyle->{Red,AbsolutePointSize[6]},AspectRatio->Automatic],ParametricPlot[5 {Cos[t],Sin[t]}+{5,0},{t,0,2 Pi},PlotStyle->Red],Plot[x,{x,0,5},PlotStyle->Green],PlotRange->All]

A question one can then ask, obviously, is what is the fewest number of moves required to reach a specified point and specifically a specified point on the part of the line y = x in the first quadrant (a segment of which is shown in green).  The basic form of the argument above (STEP 1:  You can reach a particular point p in k moves.  STEP 2:  You cannot reach p in any number n < k moves.) applies readily to many more points p other than (2021, 2021).  In fact, I guess that basic argument will apply to any integer lattice point p if you can find the correct k and complete the proof of the claim in the second step.  

For example, all of the twelve points that are possible to reach after a first move can be treated by the argument with k = 1.  You can reach these points in one move, but you can’t do it in zero moves.  Of course, none of those points are on the line y = x.

If I want to make a distinction between a move and a point, I’ll use curly brackets to denote a move like {4,3} or {5,0} and round brackets to denote a point, especially what I’ll call a resultant point like (5, 5) or (2021, 2021) which (perhaps) results from a sequence of moves.  

There are 73 points that can be reached in two moves.  These are as follows:

If the first move is {5,0}, then you get the 12 points in red above, namely 

(0, 0)    = {5,0} + {-5,0},
(1, -3)  = {5,0} + {-4,-3},
(2, -4)  = {5,0} + {-3,-4},
(5,-5)   = {5,0} + {0,-5},
(8, -4)  = {5,0} + {3,-4},
(9, -3)   = {5,0} + {4,-3},
(10, 0) = {5,0} + {5,0}, 
(9, 3)   = {5,0} + {4,3},
(8, 4)   = {5,0} + {3,4},
(5, 5)     = {5,0} + {0,5},
(2, 4)  = {5,0} + {-3,4},
(1, 3)  = {5,0} + {-4,3}.  

It is interesting that two of them are on the line y = x.  These are (0, 0) and (5, 5).  For the first one the STEP 1/STEP 2 argument works with k = 0.  You can’t get to the origin with any fewer moves than that, though you can get there with two moves.  None of the first move points (nor the zero-move point), however, are among the other twelve points.  In particular, the STEP 1/STEP 2 argument works with k = 2 moves.  In particular: 

The minimum number of moves required to get to (5, 5) is k = 2 moves.  Incidentally, those two moves have to be {5,0} + {0,5} or {0,5} + {5,0}.   

Continuing our list of the two-move points, if the first move is {4,3}, then you get the 12 points (10 of which are new)

(0, 0)    = {4,3} + {-4,-3},
(1, -1)  = {4,3} + {-3,-4},
(4, -2)   = {4,3} + {0,-5},
(7, -1)  = {4,3} + {3,-4},
(8, 0)   = {4,3} + {4,-3},
(9, 3) = {4,3} + {5,0}, 
(8, 6)   = {4,3} + {4,3},
(7, 7)   = {4,3} + {3,4},
(4, 8)     = {4,3} + {0,5},
(1, 7)  = {4,3} + {-3,4},
(0, 6)  = {4,3} + {-4,3},
(-1,3)  = {4,3} + {-5,0}.

firstmoveneone=Table[moves[[j]]+{4,3},{j,1,12}];
firstmovenetwo=Table[moves[[j]]+{3,4},{j,1,12}];
Show[ListPlot[moves,PlotStyle->{Blue,AbsolutePointSize[6]},AspectRatio->Automatic],ParametricPlot[5 {Cos[t],Sin[t]},{t,0,2 Pi},PlotStyle->Blue],ListPlot[firstmoveright,PlotStyle->{Red,AbsolutePointSize[6]},AspectRatio->Automatic],ParametricPlot[5 {Cos[t],Sin[t]}+{5,0},{t,0,2 Pi},PlotStyle->Red],Plot[x,{x,0,8},PlotStyle->Green],ListPlot[firstmoveneone,PlotStyle->{Red,AbsolutePointSize[6]},AspectRatio->Automatic],ParametricPlot[5 {Cos[t],Sin[t]}+{4,3},{t,0,2 Pi},PlotStyle->Red],PlotRange->All]

The repeated ones are (0, 0) and (9, 3) indicating there are distinct sequences of two moves to get to these points:  
(0,0) = {5,0} + {-5,0} = {4,3} + {-4,-3} and 
(9,3) = {5,0} + {4,3} = {4,3} + {5,3}.  

Again, the STEP 1/STEP 2 argument works for all of the new points, and notably, 

The minimum number of moves required to get to (7, 7) is k = 2 moves.

The remaining 73-22 = 51 two-move points are all obtained by taking one of the 22 points above, negating one or both of the coordinates, switching the coordinates, or both.  Furthermore, every point obtained in this way is a two-move point.

Exercise:  Give a clear and concise proof of this assertion, i.e., that there are exactly 73 two-move points.

As a consequence we can consider points in the closed first quadrant to organize all 73 two-move points.  

Summary:  (0, 0)                                 ( one point )
                       (8, 0)                                 ( four points (±8, 0), (0, ±8) )
                       (10, 0)                              ( four points )
                       (9, 3)                                 ( eight points (±9, 3), (±9,-3),  (3, ±9), (-3, ±9) )
                       (8, 4)                                 ( eight points )
                       (8, 6)                                 ( eight points )
                       (1, 1)                                 ( four points )
                       (5, 5)                                 ( four points )
                       (7, 7)                                 ( four points )
                       (2, 4)                                 ( eight points ) 
                       (1, 3)                                 ( eight points )
                       (1, 7)                                 ( eight points )
                       (0, 6)                                 ( four points )
                       
     That’s  6 (8) + 6 (4) + 1 = 48 + 24 + 1 = 73.  With this summary list there is one more diagonal destination point of interest to which the STEP 1/STEP 2 argument applies:
     
     The minimum number of moves required to get to (1, 1) = {-3,4} + {4,-3} is k = 2 moves.
     
     The resultant (1, 1) is interesting also because it tells us that by repeating those two moves one can reach every resultant point (n, n) in 2n moves.  In particular, every point 
     (n, n) in the positive half-diagonal of the plane can be reached, and this gives an upper bound on the associated minimum number of required moves.  Let us denote the minimum number moves required to reach (n, n) by k(n).   We know 
     
     k(n) ⩽ 2n.
     
     The resultant (0, 0) can be reached in two moves in exactly 12 ways.  (Just as an aside.)

Diagonal Pairs

The two-move resultants (1, 1), (5, 5), and (7, 7) are useful to consider as (pairs of) moves by themselves.  Thus, we will write the move {1,1} = {-3,4} + {4,-3} and remember that this kind of diagonal pair move counts for two moves.  I’m now going to start a list of diagonal resultants that can be reached by particular sequences of diagonal pair moves.  I will record the number of moves which can be taken as a conjectured value of the minimum number of required moves.  I will also indicate if this is known.  First let me state a conjecture.  

Conjecture 1:  The minimum number of required moves to reach the resultant point (n, n) with n > 0 is even, and the minimum can be achieved using only diagonal pairs.  

It seems the next interesting point to which the STEP 1/STEP 2 argument may/might be applied is (2, 2).  

(1, 1) = {1,1}                                                                           ( 2 moves is the minimum )
(2, 2) = 2 {1,1}                                                                        ( 4 moves )
(3, 3) = 3{1,1} = {5,5} + 2 {-1,-1}                                       ( 6 moves )
(4, 4) = {5,5} + {-1,-1}                                                           ( 4 moves )
(5, 5) = {5,5}                                                                            ( 2 moves is the minimum )
(6, 6) = {7,7} + {-1,-1} = {5,5} + {1,1}                                ( 4 moves )
(7, 7) = {7,7}                                                                            ( 2 moves is the minimum )

Conjecture 2 (Exercise):  If (n, n) = (7j, 7j) for some j > 0, then k(n) = 2j.
Conjecture 2a:  The cases (n, n) = (7j, 7j) for some j > 0, represent the only cases in which the minimum can only be attained by using exclusively {7,7} diagonal pair moves.  

(8, 8) = {7,7} + {1,1}                                                              ( 4 moves )

Conjecture 3:  If (n, n) = (7j+1, 7j+1) for some j > 0, then k(n) = 2j+2.

(9, 9) = {7,7} + 2 {1,1} = 2 {5,5} + {-1,-1}                         ( 6 moves )

Conjecture 4:  If (n, n) = (7j+2, 7j+2) for some j > 0, then k(n) = 2j+4.

(10, 10) = 2 {5,5}                                                                    ( 4 moves )
(11, 11) = 2 {5,5} + {1,1}                                                      ( 6 moves )
(12, 12) = {7,7} + {5,5}                                                         ( 4 moves is the minimum )

Conjecture 5 (Exercise):  If (n, n) = (7j+5, 7j+5) for some j > 0, then k(n) = 2j+2.  This applies to (2021, 2021) = (7(288) + 5, 7(288) + 5) in which case k(j) = 2(288) + 2 = 578.

(13, 13) = 2{7,7} + {-1,-1}                                                    ( 6 moves )
(14, 14) = 2{7,7}                                                                     ( 4 moves is the minimum )
(15, 15) = 3 {5,5}                                                                    ( 6 moves )

Conjecture 6:  The only resultants (n, n) which can be reached in a minimal number of moves consisting only of {5,5} diagonal pairs are the six resultants 
(5, 5), (10, 10), (15, 15), (20, 20), (25, 25), and (30, 30).

Note:  (15, 15) = 3 {5,5} = 2 {7,7} + {1,1},  
              (20, 20) = 4 {5,5} = 3 {7,7} + {-1,-1},
              (25, 25) = 5 {5,5} = 2 {7,7} + 2 {5,5} + {1,1} = 3 {7,7} + 4 {1,1} = 4 {7,7} + 3 {-1,-1}.
              (30, 30) = 6 {5,5} = 4 {7,7} + 2 {1,1}
              
Conjecture 7 (pseudo-periodicity/additivity):  There is some m for which k(m+j) = k(m) + k(j) for all j.

(16, 16) = 2 {7,7} + 2 {1,1} = 3 {5,5} + {1,1}                  ( 8 moves ) 
(17, 17) = {7,7} + 2 {5,5}                                                     ( 6 moves )
(18, 18) = 2 {7,7} + {5,5} + {-1,-1}                                    ( 8 moves )

Conjecture 8:  The resultant (n, n) = (18, 18) is the first resultant requiring all three “kinds” of diagonal moves.

(19, 19) = 2 {7,7} + {5,5}                                                         ( 6 moves )
(20, 20) = 4 {5,5}                                                                       ( 8 moves )
(21, 21) = 3 {7,7}                                                                       ( 6 moves )
(22, 22) = 3 {7,7} + {1,1} = {7,7} + 3 {5,5}                          ( 8 moves )
(23, 23) = 3 {7,7} + 2 {1,1} = 2 {7,7} + 2 {5,5} + {-1,-1}  ( 10 moves )
(24, 24) = 2 {7,7} + 2 {5,5}                                                      ( 8 moves )
(25, 25) = 5 {5,5}                                                                       ( 10 moves )
(26, 26) = 3 {7,7} + {5,5}                                                         ( 8 moves is the minimum )
(27, 27) = {7,7} + 4 {5,5}                                                         ( 10 moves )
(28, 28) = 4 {7,7}                                                                       ( 8 moves is the minimum ) 
(29, 29) = 4 {7,7} + {1,1}                                                         ( 10 moves )
(30, 30) = 4 {7,7} + 2 {1,1} = 6 {5,5}                                    ( 12 moves )
(31, 31) = 3 {7,7} + 2 {5,5}                                                     ( 10 moves )
(32, 32) = {7,7} + 5 {5,5}                                                        ( 12 moves )
(33, 33) = 4 {7,7} + {5,5}                                                        ( 10 moves )
(34, 34) = 2 {7,7} + 4 {5,5} = 5 {7,7} + {-1,-1}                  ( 12 moves ) 
(35, 35) = 5 {7,7}                                                                     ( 10 moves is the minimum )
(36, 36) = 3 {7,7} + 3 {5,5} = 5 {7,7} + {1,1}                     ( 12 moves )           
(37, 37) =  {7,7} + 6 {5,5} = 5 {7,7} + 2 {1,1}                    ( 14 moves )
(38, 38) = 4 {7,7} + 2 {5,5}                                                    ( 12 moves )  Note:  This says the number m in Conjecture 7 is not 35.
(39, 39) = 2 {7,7} + 5 {5,5}                                                    ( 14 moves )
{40, 40} = 5 {7,7} + {5,5}                                                       (12 moves is the minimum )