Step step step step step

We can rotate the coordinate plane $135^\circ$ degrees clockwise, forming a pyramid, and our steps are now:

1. down two levels (S)
2. down and to the left (SW)
3. down and to the right (SE)
4. left (W)
5. right (E)

From this, we can tell that you cannot go up levels, and once you are on a level, there is exactly one way to move to any of the points there (since points can't be repeated). Therefore, every point on a level has the same $\|S_{x,y}\|$ , and it is equal to the number of ways to get to that level.

Define $f(x)$ to be the number of ways to get to a point on level $x$ . For every dot on the previous level, we can go down in two ways (SW and SE), and for every dot two levels above, we can go down in one way (S). Therefore, we have a recurrence relation: $f(x)=2(x-1)f(x-1)+(x-2)f(x-2)$ Our initial values are $f_1=1$ and $f_2=2$ . We can calculate modulo 3, since we want to find multiples of 3. Calculating: $f_3\equiv 0\pmod 3$ $f_4\equiv 1\pmod 3$ $f_5\equiv 2\pmod 3$ Now, we have the same values as we started with, and since $1\equiv 4\pmod 3$ and $2\equiv 5\pmod 3$ , we have a pattern: 1,2,0,1,2,0,1,2,0...

Therefore, our answer is, since we have a square and are finding every third row. $3+6+9+\cdots+27+30+29+26+23+\cdots+5+2$ This is equal to $165+155=\boxed{320}$ .

It turns out the traditional rectangular cartesian coordinates are not the optimal way to look at the problem. It is better to look at the problem in terms of taking steps between the lines $x + y = k$ and along them. Note that from any point on a line $x+y = k$ , we can walk to any other point on the line and there is exactly one way to do it. Now if $N$ is the number of ways to reach a line $x+y=k$ from the point $(1,1)$ (but we are not yet moving along the line) then every point on the line has exactly $N$ ways to reach it when we allow traversing along a line. Now call $a_n$ the numbers of ways to get to each point on the line $x+y = n$ . It is easy to see that for $n \ge 4$ , we have $a_n = 2(n-1)a_{n-1} + (n-2)a_{n-2}$ . Now by induction we can prove that $a_n \equiv n \pmod{3}$ by utilizing the fact that $2(n-1)^2 + (n-2)^2 - n \equiv 3(n^2 - 3n + 2) \equiv 0 \pmod{3}$ and the base cases are trivial.

Thus the problem is reduced to counting the number of points $(x,y)$ such that $x + y \equiv 0 \pmod{3}$ . This is just: $10 \cdot 11 + 21 \cdot 10 = \boxed{320}$ because that are $10$ cases when $11$ such points lie on the line $x=k$ , i.e. when $k \equiv 2 \pmod{3}$ and $10$ cases otherwise.

• Let $Q_n$ be the set of points $(x,y)$ with positive integers $x,y$ and $x+y=n$ . Note that $Q_n$ is exactly the set of all lattice points in the first quadrant that are on the diagonal through the points $(0,n)$ and $(n,0)$ .

• Let $T_n$ be the set of lattice paths from $(1,1)$ to any point in $Q_n$ , with the last step in $\{ (1,1),(1,0),(0,1) \}$ and all other steps in $S$ .

  I claim that, for any point $(x,y)$ in $Q_n$ ,

$\lvert S_{x,y} \rvert = \lvert T_n \rvert.$

This can easily be seen, as in order for a lattice path to go to $(x,y)$ , it first needs to go to any point in $Q_n$ , and if that point isn't $(x,y)$ , then it can go to $(x,y)$ by using the steps $(-1,1)$ and $(1,-1)$ .

Note that this implies that $S_{x,y}$ is constant for any point $(x,y)$ in $Q_n$ .

For all $k \geq 3$ ,

$\lvert T_k \rvert = 2(n-1)\lvert T_{k-1} \rvert + (n-2)\lvert T_{k-2} \rvert ,$

because from any point $(a,b)$ in $Q_{k-1}$ (there are $k-1$ of those), there are two ways to go to $Q_k$ in one step $\left(\text{i.e. with }(1,0)\text{ and }(0,1)\right)$ and $\lvert S_{a,b}\rvert =\lvert T_{k-1} \rvert$ . Similarly, from any point in $Q_{k-2}$ , there is one way to go to $Q_k$ in one step $\left(\text{i.e. with }(1,1)\right)$ .

I claim that for any positive integer $n > 1$ ,

$\lvert T_n \rvert \equiv n-1 \pmod{3}.$

I will prove this by strong induction. It is easy to see that this is true for $n \in \{ 2,3 \}$ , because $\lvert T_2\rvert =1$ and $\lvert T_3\rvert =2$ . Now, let's assume that it is true for $k-2$ and $k-1$ , for some positive integer $k>3$ . We know that

$\begin{aligned} \lvert T_k \rvert &= 2(k-1)\lvert T_{k-1} \rvert + (k-2)\lvert T_{k-2} \rvert\\ &\equiv 2(k-1)(k-2) + (k-2)(k-3)\\ &\equiv (2k^2-6k+2) + (k^2-5k+6)\\ &\equiv 3k^2-11k+8\\ &\equiv k-1. \end{aligned}$

So, all lattice points $(x,y)$ such that $\lvert S_{x,y}\rvert$ is a multiple of $3$ , are exactly all points in $Q_{3k+1}$ for some positive integer $k$ . In other words, $\lvert S_{x,y}\rvert$ is a multiple of $3$ if and only if $x+y\equiv 1 \pmod{3}$ .

We know that $1\leq x,y \leq 31$ , but if we look at $1\leq x \leq 30$ instead, we see that a third of those points $(x,y)$ satisfies $x+y\equiv 1\pmod{3}$ , which are $\frac{1}{3} \cdot 30 \cdot 31 = 310$ ordered pairs. If $x=31\equiv 1\pmod{3}$ , then $y$ has to be a multiple of $3$ , and there are $10$ positive multiples of $3$ no larger than $31$ . Hence, the total number of ordered pairs $(x,y)$ that satisfy the conditions is $310+10=\boxed{320}$ .

In a given diagonal of the lattice $1 \leq x, y \leq 31$ , one may only travel within the diagonal in one direction to the point $(x, y)$ (either $(-1, 1)$ , up-and-left, or $(1, -1)$ , down-and-right). For lattice paths that include both in a given diagonal, at least one vertex is used twice. Furthermore, for any point $(x, y)$ on diagonal $D_n$ , defined as the set of lattice points $(k+1, n-k)$ , $0 \leq k \leq n-1$ , one may travel to it directly from the points $(x-1, y-1)$ or $(x-1, y)$ , or any other point on diagonal $D_n$ by means of steps of size $(1, -1)$ or $(-1, 1)$ . We may find that $S(n) = |S_{x, y}|$ for a point on diagonal $D_n$ is equal to $(n-2)\cdot S(n-2) + (n-1)\cdot S(n-1)$ , with $S(1) = 1$ and $S(2) = 1$ , which can be rewritten as $P_0(n) \cdot S(n) + P_1(n)\cdot S(n+1) + P_2(n)\cdot S(n+2) = 0$ , where $P_0(n) = n$ , $P_1(n) = n+1$ , and $P_2(n) = -1$ . Thus, $\sum _{j=0}^k P_j(n)\cdot S(n+j) = 0$ , where $k = 2$ . We may find the exponential generating function for this by applying the formula for the exponential generating function $Y(t) = \sum _{n=0}^{\infty } a(n) \frac{t^n}{n!}$ to get $\sum _{j=0}^k P_j(\phi ) Y^{[j]} = 0$ , where $\phi$ is the operator $t D_t = t \frac{d}{dt}$ . Thus, the recurrence relation for $S$ has the exponential generating function defined by the differential equation $(t-1) Y'' + (t+1) Y' = 0 \Rightarrow Y'' = -\frac{t+1}{t-1} Y'$ , $Y'(0) = 1$ . Working backwards from our exponential generating function, $S(n) = n!\cdot Y^{[n]}(0)$ , which we may find by some ansatz to be $(n+1) (n-1)! \sum _{k=0}^{n+1} \frac{(-1)^k}{k!} = (n+1) (n-1)! \sum _{k=0}^n \left(\frac{(-1)^k}{k!}\right)-\frac{(-1)^n}{n}$ . By plugging and testing $n = 3k$ , $n = 3k+1$ , and $n = 3k+2$ for $k \in \mathbb{N}$ , we may find that $S(n) \equiv 0 \text{ (mod 3)}$ for all $n = 3k$ .

Of course, the recurrence equation can simply be tested for small $n$ to find that every diagonal $D_n$ such that $n \equiv 0 \text{ (mod 3)}$ gives $S(n) \equiv 0 \text{ (mod 3)}$ as well. In a given diagonal $D_n$ constrained by $1 \leq x, y \leq 31$ , there are $31-\left| n-31\right|$ lattice points. We sum $31-\left| n-31\right|$ over all multiples of $3$ from $3$ to $60$ . Our answer is the sum $\sum _{k=1}^{20} (31-\left| 3 k-31\right| ) = \boxed{320}$

Consider one particular set $S_{x,y}$ and let $x+y=k\geq 4$ . How do all the paths in $S_{x,y}$ look like? For any path in $S_{x,y}$ , consider the moment when it first reaches the diagonal $x+y=k$ . Since that moment, the path is uniquely determined: as we cannot use the same vertex twice, we can only walk along the diagonal (using either $(-1,1)$ steps only, or $(1,-1)$ steps only) until we reach $(x,y)$ .

Now consider the step in which we reached the diagonal $x+y=k$ . There are two possibilities: First, this can be a step by $(1,1)$ . In that case, what we have before the step is any valid path that ends at the diagonal $x+y=k-2$ . Second, it can be a step by $(1,0)$ or by $(0,1)$ . In this case, what we have before can be any valid path that ends at the diagonal $x+y=k-1$ .

This is clearly a bijection.

Once again in other words. If we fix a cell at the diagonal $x+y=k$ , we can construct all paths that end in this cell as follows: we can extend any path that ends on $x+y=k-2$ in one way, and we can extend any path that ends on $x+y=k-1$ in two ways.

From the above argument it follows that for any $k\geq 4$ if we consider the sets $S_{x,y}$ for all $(x,y)$ such that $x+y=k$ , these sets all have the same size. This is also trivially true for $k=2$ and $k=3$ .

Thus, let $T_k = |S_{k-1,1}|$ . (Note that we just showed that $T_k = |S_{x,y}|$ for any $x+y=k$ .) We clearly have $T_2=1$ and $T_3=2$ . We can now use the above observations to write the following recurrence: $\forall k\geq 4: T_k = 2(k-2)T_{k-1} + (k-3)T_{k-2}$

Computing modulo 3, we can now easily verify that $\forall k: T_k \equiv k-1 \pmod 3$ . Thus the answer is the number of $(x,y)$ such that $1\leq x,y\leq 31$ and $x+y\equiv 1\pmod 3$ . This is easily computed to be $\fbox{320}$ .

First of all, note that all steps either increase (x+y) by 1 or 2, or keep it constant. That is, once we reach a certain value of coordinate sum, it is not possible to reduce it by taking any more steps.

Next, note that if we reach (x,y) with a step from a coordinate with a lower value of coordinate sum, there is exactly one way to reach any (x',y') with same coordinate sum.

Combining these ideas, we obtain that the total number of ways of reaching any point with given coordinate sum is equal to the total number of ways of reaching some point with that coordinate sum. But from any point (x',y') with coordinate sum x+y - 1 or 2, there is exactly one way to reach some point with x+y as coordinate sum.

Let |S(x,y)| = N(x+y). We obtain the recurrence N(l) = (l-1)N(l-1) + (l-2) N(l-2). With the given starting values N(1)=0,N(2)=1 it is easy to see that N(l) divides 3 iff l=1 mod 3.

Thus we need the number of points with x+y=1 mod 3 and 1<=x,y<=31. There are 320 such points.