The Great Ant Walk

We consider the number of paths where the ant visits the same point again. We can simply set $d=20-a-b-c$ since the observer will not see anything beyond that.

As the ant only makes 4 anti-clockwise turns at right angles, it can only visit the same point after turning three times where it's y-coordinate is $c-a$ . Since the first section of the path lies between $(0,0)$ and $(0,-a)$ , we get that the point of intersection is $(0,c-a)$ and since it lies in that path, $c-a \leq 0 \Rightarrow c \leq a$ .

The ant will travel in a rectangle to reach that point and the total distance traveled to reach that point is $a+b+c+b$ and for the observer to notice the repeat, this value must be at most 20. Therefore, we want to count the number of positive integer triplets $a,b,c$ satisfying $c \leq a$ and $a+2b+c \leq 20$

For a given $b$ , we have $c+a \leq 20-2b$ and as $c leq a$ we have $1 \leq c \leq 10-b$ and for each $c$ , we have $c \leq a \leq 20-2b-c$ which gives $21-2b-2c$ values of $a$ so the total number of possible pairs of $(a,c)$ is $(21-2b-2)+...+(21-2b-2(10-b))$ $=1+3+...+(19-2b) = (10-b)^2$

$a+c \geq 2 \Rightarrow 0 < 2b \leq 18 \Rightarrow 1 \leq b \leq 9$ so the number of positive integer solutions is $(10-1)^2+(10-2)^2...+(10-9)^2=1+4+...+81=285$

We then consider the total number of possible paths regardless of the condition. Each path is uniquely determined by when the ant decides to turn. Out of the first 19 points visited excluding $(0,0)$ the ant can choose to turn at up to 3 points. Therefore, the total number of paths is ${19 \choose 0}+{19 \choose 1}+{19 \choose 2}+{19 \choose 3}=1+19+171+969=1160$ and thus the number of paths satisfying the condition is $1160-285=875$

If a >= 20, then the observer only saw the ant moving 20 units downwards. There is obviously no overlapping of the path, so this is 1 possible path. If a < 20 but a+b >= 20, then the observer saw the ant moving downwards then rightwards (for 20 units in total). There is no overlapping of the path as well, so we consider all solutions to a+b=20. Since a and b are positive, then (a,b) = (1,19), (2,18), ... , (19,1). There are 19 possible paths. If a+b < 20 but a+b+c > 20, then the observer saw the ant moving downwards then rightwards then upwards (for 20 units in total). There cannot be overlapping of the path as well, so we consider all solutions to a+b+c=20. There are 19C2 = 171 possible paths for this. If a+b+c<20, then the observer must have seen the ant moving downwards then rightwards then upwards then leftwards (for 20 units in total). So a+b+c+d=20. There are 19C3=969 such paths. But there might be overlapping of paths, and this happens precisely when two conditions are satisfied: (1) the ant moves fewer or equal units upwards compared to downwards; (2) the ant moves fewer or equal units rightwards compared to leftwards. In other words, the ant crosses its own path iff c<=a and b<=d. We consider the number of such possibilities. In such a scenario, we can let a = c+m and b = d+n, where m and n are non-negative integers. So now we have 2b+2c+m+n=20. Letting e = b-1 and f = c-1 (note that b and f are now non-negative integers), we have 2e+2f+m+n=16. Now all the possible (e+f, m+n) are (0,16), (1,14), (2,12), (3,10), ... , (8,0). For any non-negative integers p,q and r such that p+q=r, there are r+1 possibilities for (p,q) [which are (0,r), (1,r-1), ... (r,0)]. Using this fact, we can easy calculate the number of possibilities of e, f, m and n for the cases above. The total number of possibilities is thus 1(17)+2(15)+3(13)+...+9(1)=285. Note that for any unique (e,f,m,n), we can reconstruct a unique (a,b,c,d). So there are 285 possibilities for (a,b,c,d). Now we need to subtract these 285 possibilities from the 969 to give us 684 possible non-overlapping paths when a+b+c+d=20.

The total number of possible paths should thus be 1+19+171+684=875.

Note that the ant begins with positive a units in the negative y direction and, as only 20 first units are observed, may or may not continue its path in other directions, which means that the paths should ensure the conditions of a>0; if c=0 then d must equals 0 and if b=0 then c=0 and d=0.

Considering two cases:

1) $a>0, c=d=0$ : always satisfactory because only two directions are followed: a may take any value from 1 to 20 (then b=20-a), so 20 paths

2) a,b,c>0: So as for the ant to visit no point more than once, $d < b$ (stays to the right of the y axis) or $c > a$ (goes up over the x axis before walking to the left) Number of paths = paths( $d < b$ )+paths( $c > a$ )-paths( $d < b$ and $c > a$ ) (Refer here )

• paths( $d<b$ ): as $a,b,c \geq 1$ , d<b, d takes one value between 0 and [(20-1-1-1)/2]=[17/2]=8 ([x]: floor function), b takes one between d+1 and 20-1-1-d=18-d, c between 1 and 19-b-d (a=20-b-c-d), so there are $\sum_{d=0}^{8} \sum_{b=d+1}^{18-d} (19-b-d)=615$ different paths
• paths( $c>a$ ): similarly, the number of paths is $\sum_{a=1}^{9} \sum_{c=a+1}^{19-a} (20-b-d)=525$
• paths( $d < b$ and $c > a$ ): $c > a \geq 1 \Rightarrow c \geq 2$ d takes one value between 0 and [(20-1-1-2)/2]=8, b takes one between d+1 and 20-1-2-d=17-d, thus c>(c+a)/2 => c>[(20-b-d)/2], c takes one from [(20-b-d)/2]+1 to 19-b-d so there are $\sum_{d=0}^{8} \sum_{b=d+1}^{17-d} \Big((19-b-d)-\big([(20-b-d)/2]+1\big)+1\Big)$ $=\sum_{d=0}^{8} \sum_{b=d+1}^{17-d} (9-[(b+d)/2])$ $=(9+8+8+7+...+1+1)+(8+7+7+...+1+1)$ $+(7+6+6+...+1+1)+...+(2+1+1)+1)$ $=(17+15+13+...+3+1)+(15+13+...+1)$ $+(13+11+...+1)+(3+1)+1)$ $=9^2+8^2+7^2...+2^2+1$ $=285$ paths

In conclusion the total number of different possible paths is: 20+615+525-285=875

There are a few cases to consider for this problem.

~~~~

Case 1: The ant didn't turn before it has walked 20 units. There is only $1$ possible path.

Case 2: The ant turned once before it has walked 20 units. It must have turned before walking the 20th unit, so it could have turned after walking 1 unit, after walking 2 units, ..., or after walking 19 units. Hence the number of possible paths is $\binom{19}{1}=19$ .

Case 3: The ant turned twice before it has walked 20 units. Again, it must have turned before walking the 20th unit, so the number of possible paths is $\binom{19}{2}=171$ .

~~~~

It is easy to see that in these first three cases, it is impossible for the ant's path to cross itself. Hence we don't have to subtract from the number of paths calculated above.

~~~~

Case 4: The ant turned three times before it has walked 20 units. As above, the number of possible paths should be $\binom{19}{3}=969$ . However, in some of these paths, the ant visits some point twice; we have to count how many such paths there are.

Firstly, observe that the path of the ant can only cross itself at most once, and this point must be on the negative $y$ -axis.

Let's say the path crosses itself at $(0,0)$ . How many such paths are there? We count as follows:

• If the ant reaches $(0,0)$ after walking for 20 units, its path must be a rectangle with positive integer side lengths and perimeter 20. There are exactly 9 such rectangles, so there are 9 possible paths in this case.
• If the ant reaches $(0,0)$ after walking for 18 units, its path must be a rectangle with positive integer side lengths and perimeter 18, followed by walking 2 units to the left (in the negative $x$ direction). There are exactly 8 such rectangles, so there are 8 possible paths in this case.
• ...
• If the ant reaches $(0,0)$ after walking for 4 units, its path must be a rectangle with positive integer side lengths and perimeter 4, followed by walking 16 units to the left. There is exactly 1 such rectangle, so there is 1 possible path in this case.
• Notice that the ant can't return to $(0,0)$ after walking an odd number of units, as its path is a rectangle with integer sides, whose perimeter must be even.

So the total number of paths that cross themselves at $(0,0)$ is $9+8+\cdots+1=\binom{10}{2}$ .

By a similar argument, we see that:

• If the path crosses itself at $(0,0)$ , the ant must walk for 0 units, then trace out a rectangle with perimeter at most 20, and continue walking to the left. There are $\binom{10}{2}$ such paths.
• If the path crosses itself at $(-1,0)$ , the ant must walk for 1 unit, then trace out a rectangle with perimeter at most 18, and continue walking to the left. There are $\binom{9}{2}$ such paths.
• If the path crosses itself at $(-2,0)$ , the ant must walk for 2 units, then trace out a rectangle with perimeter at most 18, and continue walking to the left. There are $\binom{9}{2}$ such paths.
• If the path crosses itself at $(-3,0)$ , the ant must walk for 3 units, then trace out a rectangle with perimeter at most 16, and continue walking to the left. There are $\binom{8}{2}$ such paths.
• ...
• If the path crosses itself at $(-16,0)$ , the ant must walk for 16 units, then trace out a rectangle with perimeter at most 4, and continue walking to the left. There are $\binom{2}{2}$ such paths.

Hence the total number of paths that cross themselves is $\binom{10}{2}+2\left\{\binom{9}{2}+\binom{8}{2}+\cdots+\binom{2}{2}\right\}\\=\binom{10}{2}+2\binom{10}{3}\\=285$

~~~~

Therefore the total number of possible paths that do not cross themselves is $1+19+171+969-285=875$ .

We will solve the question in general for when the observer watches the ant travel $2k$ units.

There are 4 legs to the ant's journey. If the observer did not see the 4th leg, then the ant could not have possibly intersected it, no matter the values of $a,b,c$ . We consider 4 cases, based on how many of the legs the observer saw.

If the observer saw only the first leg (or part of it), then the ant walked $2k$ units down, so there is only one possible observed path.

If the observer saw parts of the first two legs, then the ant walked $a$ units down and $2k - a$ units to the right. Both $a$ and $2k - a$ are positive integers, so $1 \leq a \leq 2k-1$ , so there are $2k-1$ possible paths that could have been seen.

If the observer saw parts of the first three legs, then the ant walked $a$ units down, $b$ units to the right, and $2k - a - b$ units up. This is equivalent to saying that $a-1$ and $b-1$ are non-negative integers with sum at most $2k-1$ . There are $\binom{2k-1}{2}$ ways this can happen, so there are $\binom{2k-1}{2}$ possible paths that could be seen.

We lastly consider the case where the observer saw parts of all 4 legs. For simplicity, we will assume that $a + b + c + d = 2k$ . We will consider all possible paths the ant could have taken with these parameters, and note that the ant will step on the same intersection more than once if and only if $a \geq c$ and $d \geq b$ . Since $a,b,c,d$ are all positive integers, we can rewrite our equation as $(a-1) + (b-1) + (c-1) \leq 2k-4$ . This inequality will have the same set of solutions as the original equation. We have 3 non-negative integers that sum to $2k-4$ so there are $\binom{2k-1}{3}$ solutions.

Let $S$ be the set of $\binom{2k-1}{3}$ solutions to $a + b + c + d = 2k$ . We divide $S$ into 4 sets:

$S_{ac,\overline{bd}}$ are the solutions in $S$ with $a=c, b \neq d$

$S_{ac,bd}$ are the solutions in $S$ with $a=c, b = d$

$S_{\overline{ac},\overline{bd}}$ are the solutions in $S$ with $a \neq c, b \neq d$

$S_{\overline{ac},bd}$ are the solutions in $S$ with $a\neq c, b = d$

Paths corresponding to solutions in $S_{ac,bd}$ contain the point $(0,0)$ twice, so do not give paths the ant could have travelled. Paths corresponding to solutions in $S_{ac,\overline{bd}}$ give paths the ant could have travelled if and only if $b > d$ . This occurs half of the time, since if we swap $b$ and $d$ then this is also a solution. Similarly, half of the solutions in $S_{\overline{ac},bd}$ will give valid paths. Three quarters of the solutions in $S_{\overline{ac},\overline{bd}}$ will also give valid paths. We will now determine the sizes of these 4 sets.

A solution in $S_{ac,bd}$ gives a solution to the equation $a + b = k$ , of which there are $k-1$ such solutions, so $\vert S_{ac,bd} \vert = k-1$ .

A solution in $S_{ac,\overline{bd}}$ gives a solution to the equation $2a + b + d = 2k$ . When $a = k-1$ there is 1 solution, when $a= k-2$ , there are 3 solutions, and as we decrease $a$ by 1 we get 2 additional solutions. Thus, the total number of solutions is $1 + 3 + \cdots + 2k-3 = (k-1)^2$ . However, this also counts solutions with $b=d$ , of which there are $k-1$ , so $\vert S_{ac,\overline{bd}}\vert =(k-1)(k-2)$ . We also have $\vert S_{\overline{ac},bd} \vert = (k-1)(k-2)$ by symmetry.

This means that $\vert S_{\overline{ac},\overline{bd}} \vert = \binom{2k-1}{3} - 2(k-1)(k-2) -(k-1) = \frac{2}{3}(k-1)(k-2)(2k-3).$ This tells us that the number of valid paths when the observer sees all 4 legs will be $\frac{(k-1)(k-2)}{2} + \frac{(k-1)(k-2)}{2} + \frac{(k-1)(k-2)(2k-3)}{2} = \frac{(k-1)(k-2)(2k-1)}{2}.$

This gives the total number of paths as $\frac{(k-1)(k-2)(2k-1)}{2} + \frac{(2k-1)(2k-2)}{2} + (2k-1) + 1 = \frac{2k^3 - 3k^2 + 5k}{2}.$ When $k = 7$ , we get $287$ paths the ant could have taken.