The sequences $t_{1}, t_{2}, t_{3}, \ldots$ and $s_{1}, s_{2}, s_{3}, \ldots$ are defined by

- $t_{1}=1$,
- $t_{2}=m$ for some positive integer $m>0$,
- $s_{k}=t_{1}+t_{2}+t_{3}+\cdots+t_{k-1}+t_{k}$ for each $k \geq 1$, and
- $t_{n}=n s_{n-1}$ for each $n \geq 3$.

There exist positive integers $m$ that end in in exactly four $9 \mathrm{~s}$ and for which $t_{30}=N$ ! for some positive integer $N$. Determine all of these corresponding values of $N$.

(If $n$ is a positive integer, the symbol $n$ ! (read " $n$ factorial") is used to represent the product of the integers from 1 to $n$. That is, $n!=n(n-1)(n-2) \cdots(3)(2)(1)$. For example, $5!=5(4)(3)(2)(1)$ or $5!=120$.)
If $m$ is a positive integer that ends in 9999 , then $m+1$ must end in 0000 .

This means that $m+1$ is a multiple of 10000 ; that is, $m+1=10000 k=10^{4} k$ for some positive integer $k$.

Since $m$ does not end in five or more 9 s, then $m+1$ does not end in 00000 and so the units digit of $k$ is not 0 . In other words, $k$ is not divisible by 10 .

We determine the first several terms in each sequence to see if we can find a pattern.

By definition, $t_{1}=1$ and $t_{2}=m$.

Next, $s_{2}=t_{1}+t_{2}=m+1=10^{4} k$.

This gives $t_{3}=3 s_{2}=3 \cdot 10^{4} k$.

Next, $s_{3}=t_{1}+t_{2}+t_{3}=s_{2}+t_{3}=10^{4} k+3 \cdot 10^{4} k=4 \cdot 10^{4} k$.

This gives $t_{4}=4 s_{3}=4 \cdot 4 \cdot 10^{4} k$.

Next, $s_{4}=s_{3}+t_{4}=4 \cdot 10^{4} k+4 \cdot\left(4 \cdot 10^{4} k\right)=5 \cdot 4 \cdot 10^{4} k$.

This gives $t_{5}=5 s_{4}=5 \cdot 5 \cdot 4 \cdot 10^{4} k$.

Next, $s_{5}=s_{4}+t_{5}=5 \cdot 4 \cdot 10^{4} k+5 \cdot\left(5 \cdot 4 \cdot 10^{4} k\right)=6 \cdot 5 \cdot 4 \cdot 10^{4} k$.

This gives $t_{6}=6 \cdot 6 \cdot 5 \cdot 4 \cdot 10^{4} k$.

Based on this apparent pattern, we guess that, for $n \geq 5$, we have $t_{n}=n \cdot n \cdot(n-1) \cdots \cdot \cdot 5 \cdot 4 \cdot 10^{4} k=$ $\frac{n \cdot n!\cdot 10^{4} k}{3!}$ and $s_{n-1}=n \cdot(n-1) \cdots \cdot 5 \cdot 4 \cdot 10^{4} k=\frac{n!\cdot 10^{k}}{3!}$.

We will proceed based on this guess, which we will prove at the end of this solution.

Following this guess, $t_{30}=\frac{30 \cdot 30!\cdot 10^{4} k}{3!}=5 \cdot 30!\cdot 10^{4} k$.

We want to find all positive integers $N$ for which $5 \cdot 30!\cdot 10^{4} k=N$ ! for some positive integer $k$ that is not divisible by 10 .

We note that 30 ! must be a divisor of $N$ ! and so $N \geq 30$.

We also know that $N$ ! contains at least five more factors of 5 than 30 ! since $N!=30!\cdot 5 \cdot 5^{4} \cdot 2^{4} k$. This means that $N$ must be enough larger than 30 so that $N$ ! includes at least five more factors of 5 .

We note that $35!=35(34)(33)(32)(31) 30!$, which contains one more factor of 5 than 30 ! and that 35 ! is the smallest factorial with this property.

Similarly, 40 ! contains one more factor of 5 than 35 !.

Also, 45 ! contains one more factor of 5 than 40 ! and is the smallest factorial that includes three more factors of 5 than 30 !.

Since $5^{2}$ is a divisor of 50 , then 50 ! contains two more factors of 5 than 45 ! and is the smallest factorial that thus includes five more factors of 5 than 30 !. We conclude that $N \geq 50$.

We note that 50!, 51!, 52!, 53!, and 54! each contain the same number of factors of 5 , and that 55 ! (and thus every $N$ ! with $N \geq 55$ ) contains at least six more factors of 5 than 30 !.

Now since $N \geq 50$, then 50 ! is a divisor of $N!=30!\cdot 5^{5} \cdot 2^{4} k$.

Rearranging, we get $N(N-1)(N-2) \cdots(33)(32)(31)=5^{5} \cdot 2^{4} k$ or $N(N-1)(N-2) \cdots(33)(2)(31)=$ $5^{5} k$.

Since the left side is even, then $k$ is even.

Since $k$ is even and $k$ is not divisible by 10 , then $k$ is not divisible by 5 . (That is, the right side contains exactly five factors of 5 .)

This means that $N$ cannot be 55 or greater, as in this case the number of factors of 5 (at least six on the left side) would not balance.

Therefore, the possible values of $N$ are $50,51,52,53,54$.

To complete our solution, we prove that $t_{n}=\frac{n \cdot n!\cdot 10^{4} k}{3!}$ and $s_{n-1}=\frac{n!\cdot 10^{4} k}{3!}$ when $n \geq 5$.

We already know that $t_{5}=5 \cdot 5 \cdot 4 \cdot 10^{4} k=\frac{5 \cdot 5!\cdot 10^{4} k}{3!}$ and that $s_{4}=5 \cdot 4 \cdot 10^{4} k=\frac{5!\cdot 10^{4} k}{3!}$.

We prove that the desired formulas are true for all $n \geq 5$ by using a technique called mathematical induction.

We have proven that these formulas are correct for $n=5$.

If we can prove that whenever the forms are correct for $n=j$, then they must be correct for $n=j+1$, then their correctness for $n=5$ will give their correctness for $n=6$ which will give their correctness for $n=7$ and so on, giving their correctness for all $n \geq 5$.

So suppose that $t_{j}=\frac{j \cdot j!\cdot 10^{4} k}{3!}$ and that $s_{j-1}=\frac{j!\cdot 10^{4} k}{3!}$.

Then $s_{j}=s_{j-1}+t_{j}=\frac{j!\cdot 10^{4} k}{3!}+\frac{j \cdot j!\cdot 10^{4} k}{3!}=\frac{j!\cdot 10^{4} k}{3!}(1+j)=\frac{(j+1)!\cdot 10^{4} k}{3!}$, as expected.

This means that $t_{j+1}=(j+1) s_{j}=(j+1) \cdot \frac{(j+1)!\cdot 10^{4} k}{3!}=\frac{(j+1) \cdot(j+1)!\cdot 10^{4} k}{3!}$, as expected.

Therefore, if $t_{j}$ and $s_{j-1}$ have the correct forms, then $t_{j+1}$ and $s_{j}$ have the correct forms.

This proves that $t_{n}$ and $s_{n-1}$ have the correct forms for all $n \geq 5$, which completes our solution.

ANSWER: $50,51,52,53,54$

## Relay Problems

(Note: Where possible, the solutions to parts (b) and (c) of each Relay are written as if the value of $t$ is not initially known, and then $t$ is substituted at the end.)