Snake on a Plane

Task

In a video game called Snake, a player moves a snake through a square region in the plane, trying to eat the white pellets that appear.

 

 

If we imagine the playing field as a 32-by-32 grid of pixels, then the snake starts as a 4-by-1 rectangle of pixels, and grows in length as it eats the pellets:

• After the first pellet, it grows in length by one pixel.
• After the second pellet, it further grows in length by two pixels.
• After the third pellet, it further grows in length by three pixels.
• and so on, with the $n$-th pellet increasing its length by $n$ pixels.

Let $L(n)$ denote the length of the snake after eating $n$ pellets. For example, $L(3)=10$.

1. How long is the snake after eating 4 pellets? After 5 pellets? After 6 pellets?
2. Find a recursive description of the function $L(n)$.
3. Find a non-recursive expression for $L(100)$, and evaluate that expression to compute $L(100)$.
4. What is the largest number of pellets a snake could eat before he could no longer fit in the playing field? That is, how long is a perfect game of snake?

IM Commentary

This task has students approach a function via both a recursive and an algebraic definition, in the context of a famous game of antiquity that they may have encountered in a more modern form. The content underlying the algebra is the sum of the first $n$ natural numbers (also known as the $n^{\rm th}$ triangular number): $$ 1+2+3+\cdots+n=\frac{n(n+1)}{2}. $$ In addition to the general notions of recursive and algebraic functions, the task could be used either as a motivation for, or an application of, these types of sums. As an introduction to triangular numbers that might proceed this task, see http://www.illustrativemathematics.org/tasks/1830. Students may need help in understanding the play of the game, especially with regard to the turning and growing mechanism of the snake. It may be helpful to provide visual aids for this -- for example, the motivation for this task was the animated gif http://i.imgur.com/dAtcCfH.gif showing the perfect game addressed in the question (shows that indeed the maximum length can be achieved!).

Solution

1. Since $L(3)=10$, we can most easily compute $L(4)$ by adding 4 to $L(3)$, to get $L(4)=L(3)+4=10+4=14$, rather than starting from scratch, that is by calculating $L(4)=4+1+2+3+4=14$. Similarly, we find $L(5)=L(4)+5=14+5=19$, and $L(6)=L(5)+6=19+6=25$.
2. Generalizing the previous part, to compute the length after $n$ pellets, we take the length after $n-1$ pellets, and add on $n$ more pixels. Algebraically, this reads $$ L(n)=L(n-1)+n. $$ To complete the specification of a recursive function, we also need to include a starting value, which we are given as $L(0)=4$.
3. The recursive definition gives $L(100)=L(99)+100$, but this doesn't particularly help for computing this value. Instead, the "start from scratch" method gives $$ L(100)=4+1+2+3+\cdots+98+99+100. $$ One particularly neat method for evaluating this proceeds as follows: $$ 1+2+3+\cdots+98+99+100=(1+100)+(2+99)+(3+98)+\cdots+(50+51)=50\cdot 101=5050. $$ We conclude that $L(100)=4+5050=5054$. After 100 pellets, the snake will be 5054 pixels long.
4. We begin by noting that the 32-by-32 grid of pixels contains $32^2=1024$ pixels, so by the last part the snake definitely runs out of room by the time it eats 100 pellets. We are looking for the largest number $n$ such that $L(n)\lt 1024$, which algebraically takes the form $$ 4+1+2+3+\cdots+n\lt 1024. $$ Here we can either repeatedly apply the trick of the last part of this problem to solve for $n$ by trial-and-error, or generalize the previous part of the problem to arrive at the formula $$ 1+2+3+\cdots+n=\frac{n(n+1)}{2}:$$ the method from part (c) applies directly if $n$ is even while if $n$ is odd we find $\frac{n-1}{2}$ groups of $n+1$ along with the middle number $\frac{n+1}{2}$ and, adding these up, we check that the formula still holds. Substituting this formula into $L(n)\lt 1024$, we need to solve $$ 4+\frac{n(n+1)}{2}\lt 1024, $$ or $n(n+1)\lt 2040$. Again, we have a variety of methods for finding the largest such $n$, ranging from educated trial-and-error to solving the quadratic equation $$ n^2+n-2040=0 $$ which gives $n\approx 44.7$. With either method, we conclude that the snake can eat 44 pellets before running out of room.