Jesse's path

We first attempt to find an explicit formula that corresponds to how much the man (let's call him Bob) spends in the $n$ th county.

Let $a_n$ denote the amount that Bob spent in the $n$ th county he walked through, letting the first county correspond to $n=0$ . We easily calculate and list the first few terms in the sequence: $a_0 = 1 = 1\cdot2^0, a_1 = 2 = 1\cdot2^1, a_2 = -12 = (-1)^{2-1} \cdot 3 \cdot 2^2,$ $a_3 = 40 = (-1)^{3-1} \cdot 5 \cdot 2^3, ...$ .

It seems as though $a_n = (-1)^{n-1} \cdot (2n-1) \cdot 2^n$ for $n \geq 1$ . Let's see if this is the case: $a_{n+2} = -4(a_{n+1}+a_n) =$ $-4((-1)^n \cdot (2n+1) \cdot 2^{n+1} + (-1)^{n-1} \cdot (2n-1) \cdot 2^n) =$ $-4((-1)^n \cdot 2^n \cdot ((4n+2) - (2n-1))) =$ $(-1)^{(n+2) - 1} \cdot (2(n+2) - 1) \cdot 2^{n+2} \checkmark$ . This relation means that we've found an explicit formula for how much Bob spends in each county.

$\\$

Now we need to find how many counties Bob walks through on his way through the plot of land. It is well-known that the diagonal line through a rectangle with side lengths $c,d \in \mathbb{Z}^+$ will cross through $c + d - \gcd(c,d)$ unit squares, which means that Bob will walk through $18 + 57 - \gcd(18,57) = 72$ squares (or counties, in this problem).

This can be easily verified. In order to travel $57$ miles south and $18$ miles west in a straight line, Bob will walk across $56$ horizontal lines and $17$ vertical lines which mark the borders of the counties. Each time Bob walks across a border, he enters a new county, and so the total number of counties he walks through "should" be $56 + 17$ . However, this does not account for the fact that Bob sometimes walks across two borders at once (he walks across the corner of a county directly to a diagonally adjacent county). This clearly happens two times, since we do not care about the bottom-left corner. Finally, we need to account for the county which Bob begins in (the top-right one). Therefore, our total becomes $56 + 17 - 2 + 1 =$ $57 + 18 - \gcd(18,57) = 72$ , as expected.

$\\$

We now know that we want to find was $a_{71}$ is (remember that we called the first county "county 0"). Using the explicit formula we found above, we get that $a_{71} = (-1)^{71-1} \cdot (2 \cdot 71 - 1) \cdot 2^{71} = 141 \cdot 2^{71}$ . Thus, we have $a = 141, b = 71$ , and so our answer is $141 + 72 = \fbox{212}$ .

$\\$ $\\$

Note: For more information on the theorem about diagonals and square grids seen above, visit this website .

Let's assume the man travels from the lattice point $(18,57)$ to the origin in two-dimensional Euclidean space, where each unit square represents a county. After the man has visited the upper right county, he will still have to visit $17$ counties to his left and $56$ counties below him. Also, the man visits two lattice points on his way, by which he travels a square left and a square down while only visiting one new county, instead of two. So, the man visits a total of $1 + 17 + 56 - 2 = 72$ counties.

Now, let $M_n$ denote the amount of money the man spends in the $n$ -th county. We know that

$M_n = -4(M_{n-1} + M_{n-2}),$

for all integers $n \geq 3$ . Let's prove by induction that

$M_n = (-1)^n \cdot (2n-3) \cdot 2^{n-1},$

for all positive integers $n$ . The base cases $M_1 = 1$ and $M_2 = 2$ are true. Let's assume that it is true for some positive integers $k-1,k-2$ with $k \geq 3$ . Then

$\begin{aligned} M_k &= -4 (M_{k-1} + M_{k-2}) \\ &= -4\left( \left( (-1)^{k-1} \cdot (2k-5) \cdot 2^{k-2} \right) + \left( (-1)^{k-2} \cdot (2k-7) \cdot 2^{k-3} \right) \right) \\ &= -4 \cdot (-1)^{k-2} \cdot 2^{k-3} \cdot \left( ( -1 \cdot (2k-5) \cdot 2 ) + ( 2k-7 ) \right) \\ &= (-1) 2^2 \cdot (-1)^{k-2} \cdot 2^{k-3} \cdot (-1)(2k-3) \\ &= (-1)^k \cdot (2k-3) \cdot 2^{k-1}, \end{aligned}$

which is what we wanted. So, the amount of money the man spends in the last county is

$M_{72} = (-1)^{72} \cdot (2(72)-3) \cdot 2^{72-1} = 141 \cdot 2^{71},$

so

$a + b = 141 + 71 = \boxed{212} .$

We will divide this problem into two sections. In the first section, we have to find the number of counties the man passes through, and in the second section, we will find a general pattern for the amount of money in the $n^{th}$ county.

For the first section, we note that the greatest common divisor of $18$ and $57$ is $3$ . Thus the rectangle can be further divided into $9$ smaller rectangles, each of size $6 \times 19$ (by dividing each side into three). The man's path will cut through the corners of exactly $3$ of the $6 \times 19$ rectangles.

Now, we will prove that for an $m \times n$ rectangle with $gcd(m,n)=1$ , the number of counties the man passes through when he traverses the diagonal will be $m+n-1$ . Indeed, the borders of the counties comprise $m+1$ vertical lines and $n+1$ horizontal lines. As the man traverses the diagonal, the number of vertical lines he crosses is $m-1$ and the number of horizontal lines he crosses is $n-1$ , because he does not cross the 2 lines at the extremes. Starting from the top corner (the first county), each time he crosses a line, he enters a new county. Because he crosses $m+n-2$ lines, the total number of counties he visits will be $1+(m+n-2)=m+n-1$ .

Thus for a $6 \times 19$ rectangle, the man will cross $6+19-1=24$ counties. He crosses exactly $3$ such rectangles, so the total number of counties he visits is $24 \times 3 = 72$ .

We proceed to the second section, to find the general pattern for the amount spent in the $n^{th}$ county. Let $A_n$ be the amount spent in the $n^{th}$ county. We calculated the first few amounts and get: $A_1 = 1, A_2 = 2, A_3=-12,A_4=40,A_5=-112, A_6=288$

The question hints that the pattern will contain a $2^b$ term, so we quickly note that $A_2$ is divisible by $2$ , $A_3$ is divisible by $4$ , $A_4$ is divisible by $8$ , $A_5$ is divisible by $16$ , and $A_6$ is divisible by $32$ . Furthermore,

$\frac{A_2}{2} = 1, \frac{A_3}{4}=-3,\frac{A_4}{8}=5,\frac{A_5}{16}=-7, \frac{A_6}{32}=9$

Thus we arrive at a conjecture: $\frac{|A_n|}{2^{n-1}}=2n-3$ or $|A_n|=\left(2^{n-1}\right)(2n-3)$

You can prove this using mathematical induction.

Now the answer is simple. At the $72^{th}$ county, the absolute value of the amount spent is $\left(2^{72-1}\right)(2\times72-3) = 2^{71}\times141$ .

Therefore $a+b=71+141=\fbox{212}$

Label the grid in Cartesian coordinates. Note that (by symmetry) the problem is not changed if the man goes from the bottom left corner to the top right corner instead (I chose this interpretation so that the co-ordinates of the intersections of the counties were positive; this was not necessary at all). Let the starting point of the man be labelled $(0, 0)$ . Then, the coordinates of the ending point are $(18, 57)$ [assuming that the horizontal length of the grid is $18$ ; by symmetry the scenario does not change if the grid is flipped by $90^\circ$ ]. The equation of the path of the man is then $y= \frac{57}{18}x= \frac{19}{6} x$ , $1 \leq x \leq 18$ (consequently $1 \leq y \leq 57$ ). Then, note that the lattice points on the path will be $(6, 19)$ , $(12, 38)$ , and $(18, 57)$ (a lattice point is a point whose coordinates are integers; note that $\gcd(19, 6)= 1$ , so for a point to be a lattice point, its $x$ coordinate has to be a multiple of $6$ ). Now, for the man to go from the bottom left corner to the top right corner, he has to cross every straight line parallel to either the $x$ axis or the $y$ axis. Call a straight line good if it is parallel to either the $x$ axis or the $y$ axis, its distance from both the axes is positive, and it connects the lattice points. Then, the man will go from one county to another if and only if he crosses a good line. Conversely, if a man crosses a good line, he shifts from the county he is in to another county. So, for the man to travel from the bottom left to the top right, he has to cross all good lines located within the grid. The total number of good lines located within the grid are $57+18= 75$ . So we can conclude that the man has gone through $75$ counties in total. However, we have double counted certain cases. When a man passes through a lattice point, he passes through two good lines at once (the converse is also true). As mentioned previously, there are a total of $3$ lattice points on the man's path, so $3$ counties have been double counted. Subtracting this number, we find out that the man has gone through $75-3= 72$ counties in all.

Now let $a_n$ be the sequence defined by $a_{n+2}= -4(a_{n+1} + a_n)$ for all $n \geq 3$ , $a_1= 1$ , and $a_2= 2$ . We simply wish to determine $a_{72}$ . Note that the characteristic equation of the recurrence relation is $x^2 - 4x - 4= 0$ , which has only $1$ distinct root:- $x= -2$ . Hence we can conclude that the closed form for this relation will be $a_n= c_1 (-2)^n + c_2 n (-2)^n$ , where $c_1$ and $c_2$ are constants (see link provided). Plugging $a_1= 1$ and $a_2= 2$ , we get a system of linear equations which has solution $(c_1, c_2)= (-\frac{3}{2}, 1)$ . Therefore we get the closed form $a_n= -\frac{3}{2} (-2)^n + n (-2)^n$ .

Then, $a_{72}= -\frac{3}{2} (-2)^{72} + 72(-2)^{72}= 141.2^{71}$ . Thus, $a= 141$ , $b= 71$ , and $a+b= 141+71= 212$ (note that the representation of a number in the form $(2m+1) 2^n$ is unique).

First, we count the number of counties the man goes through. Let us consider a general case of a $x$ by $y$ plot. To get from the top-right to the bottom-left, he has to go down $y-1$ squares and over $x-1$ squares. Including the first square, that is $x+y-1$ squares. However, he may go down a square and over a square at the same time. This will happen $\gcd(x,y)-1$ times, and each time it happens, he goes through one less county than he would usually go through. We had $x+y-1$ , and subtracting $\gcd(x,y)-1$ , we have the total number of squares he goes through, $x+y-\gcd(x,y)$ . Applying this to our 18 by 57 plot, we find he goes through $18+57-3=72$ squares.

Now, we find the amount he pays in the $n$ th county, $a_n$ . In the third, he spends $-12$ dollars. By induction, we will show that $a_n=(-1)^n\cdot 2^{n-1}\cdot (2n-3)$ for all positive integers $n>1$ . For $n=2,3$ , the equation is clearly satisfied. For $n=k$ , we have $-4\cdot((-1)^{k-2}\cdot 2^{k-3}\cdot(2k-7)+(-1)^{k-1}\cdot 2^{k-2}\cdot (2k-5))$ $=-4\cdot(-1)^{k-1}\cdot 2^{k-3}\cdot(2(2k-5)-(2k-7))$ $=(-1)^k\cdot 2^{k-1}\cdot(2k-3)$ Our induction is complete.

Finally, the amount spent in the last square is $2^{71}(141)$ , and the answer is $71+141=\boxed{212}$ .