Given a sequence $a_{1}, a_{2}, a_{3}, \ldots$ of positive integers, we define a new sequence $b_{1}, b_{2}, b_{3}, \ldots$ by $b_{1}=a_{1}$ and, for every positive integer $n \geq 1$,

$$
b_{n+1}= \begin{cases}b_{n}+a_{n+1} & \text { if } b_{n} \leq a_{n+1} \\ b_{n}-a_{n+1} & \text { if } b_{n}>a_{n+1}\end{cases}
$$

For example, when $a_{1}, a_{2}, a_{3}, \cdots$ is the sequence $1,2,1,2,1,2, \ldots$ we have

| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | $\cdots$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $a_{n}$ | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | $\cdots$ |
| $b_{n}$ | 1 | 3 | 2 | 4 | 3 | 1 | 2 | 4 | 3 | 1 | $\cdots$ |

(a) Suppose that $a_{n}=n^{2}$ for all $n \geq 1$. Determine the value of $b_{10}$.

(b) Suppose that $a_{n}=n$ for all $n \geq 1$. Determine all positive integers $n$ with $n<2015$ for which $b_{n}=1$.

(c) A sequence $x_{1}, x_{2}, x_{3}, \ldots$ is called eventually periodic if there exist positive integers $r$ and $p$ for which $x_{n+p}=x_{n}$ for all $n \geq r$.

Suppose that $a_{1}, a_{2}, a_{3}, \ldots$ is eventually periodic. Prove that $b_{1}, b_{2}, b_{3}, \ldots$ is eventually periodic.
(a) When $a_{n}=n^{2}$, we obtain

| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | $\cdots$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $a_{n}$ | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 | 100 | $\cdots$ |
| $b_{n}$ | 1 |  |  |  |  |  |  |  |  |  | $\cdots$ |

Since $b_{1} \leq a_{2}$, then $b_{2}=b_{1}+a_{2}=1+4=5$.

Since $b_{2} \leq a_{3}$, then $b_{3}=b_{2}+a_{3}=5+9=14$.

Since $b_{3} \leq a_{4}$, then $b_{4}=b_{3}+a_{4}=14+16=30$.

Since $b_{4}>a_{5}$, then $b_{5}=b_{4}-a_{5}=30-25=5$.

Since $b_{5} \leq a_{6}$, then $b_{6}=b_{5}+a_{6}=5+36=41$.

Since $b_{6} \leq a_{7}$, then $b_{7}=b_{6}+a_{7}=41+49=90$.

Since $b_{7}>a_{8}$, then $b_{8}=b_{7}-a_{8}=90-64=26$.

Since $b_{8} \leq a_{9}$, then $b_{9}=b_{8}+a_{9}=26+81=107$.

Since $b_{9}>a_{10}$, then $b_{10}=b_{9}-a_{10}=107-100=7$.

In tabular form, we have

| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | $\cdots$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $a_{n}$ | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 | 100 | $\cdots$ |
| $b_{n}$ | 1 | 5 | 14 | 30 | 5 | 41 | 90 | 26 | 107 | 7 | $\cdots$ |

(b) As in (a), we start by calculating the first several values of $b_{n}$ :

| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | $\cdots$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $a_{n}$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | $\cdots$ |
| $b_{n}$ | 1 | 3 | 6 | 2 | 7 | 1 | 8 | 16 | 7 | 17 | 6 | 18 | 5 | 19 | 4 | 20 | 3 | 21 | 2 | 22 | 1 | 23 | $\cdots$ |

We will show that if $k$ is a positive integer with $b_{k}=1$, then $b_{3 k+3}=1$ and $b_{n} \neq 1$ for each $n$ with $k1=b_{k}$, then $b_{k+1}=b_{k}+a_{k+1}=k+2$.

Since $a_{k+2}=k+2=b_{k+1}$, then $b_{k+2}=b_{k+1}+a_{k+2}=2 k+4$.

Continuing in this way, we find that $b_{k+2 m-1}=k+3-m$ for $m=1,2, \ldots, k+2$ and that $b_{k+2 m}=2 k+m+3$ for $m=1,2, \ldots, k+1$.

To justify these statements, we note that each is true when $m=1$ and that

- if $b_{k+2 m}=2 k+m+3$ for some $m$ with $1 \leq m \leq k+1$, then since $a_{k+2 m+1}=k+2 m+1$ and $b_{k+2 m}-a_{k+2 m+1}=k-m+2>0$ when $m \leq k+1$, then

$$
b_{k+2 m+1}=b_{k+2 m}-a_{k+2 m+1}=k-m+2
$$

which can be re-written as $b_{k+2(m+1)-1}=k+3-(m+1)$ and so is of the desired form; and

- if $b_{k+2 m-1}=k+3-m$ for some with $1 \leq m \leq k+1$, then since $a_{k+2 m}=k+2 m$ and $b_{k+2 m-1}-a_{k+2 m}=3-3 m \leq 0$ when $m \geq 1$, then

$$
b_{k+2 m}=b_{k+2 m-1}+a_{k+2 m}=(k+3-m)+(k+2 m)=2 k+m+3
$$

and so is of the desired form.

This tells us that, for these values of $m$, the terms in the sequence $b_{n}$ have the desired form.

Now $b_{k+2 m}=2 k+m+3 \neq 1$ for $m=1,2, \ldots, k+1$ and $b_{k+2 m-1}=k+3-m=1$ only when $m=k+2$.

Since $k+2(k+2)-1=3 k+3$, then $b_{3 k+3}=1$ and no other $n$ with $ka_{r+s p+1}=a_{r+t p+1}$, then

$$
b_{r+s p+1}=b_{r+s p}-a_{r+s p+1}=b_{r+t p}-a_{r+t p+1}=b_{r+t p+1}
$$

and if $b_{r+s p}=b_{r+t p} \leq a_{r+s p+1}=a_{r+t p+1}$, then

$$
b_{r+s p+1}=b_{r+s p}+a_{r+s p+1}=b_{r+t p}+a_{r+t p+1}=b_{r+t p+1}
$$

This argument then repeats at each step going forward.

In other words, starting at each of $b_{r+s p}$ and $b_{r+t p}$, the terms going forward will be equal, which means that the sequence $b_{1}, b_{2}, b_{3}, \ldots$ is eventually periodic. (We note that if $R=$ $r+s p$ and $P=(t-s) p$, then $b_{N}=b_{N+P}$ for each positive integer $N \geq R$.)