5. Problem: The sequence $x_{1}, x_{2}, x_{3}, \ldots$ is defined by $x_{1}=2022$ and $x_{n+1}=7 x_{n}+5$ for all positive integers $n$. Determine the maximum positive integer $m$ such that
$$
\frac{x_{n}\left(x_{n}-1\right)\left(x_{n}-2\right) \ldots\left(x_{n}-m+1\right)}{m!}
$$
is never a multiple of 7 for any positive integer $n$.
Solution A: (Ishan Nath)
We claim the answer is 404 . First, we notice that $m \leq 2022$. Otherwise,
$$
\frac{x_{1}\left(x_{1}-1\right) \cdots\left(x_{1}-m+1\right)}{m!}=\frac{2022(2022-1) \cdots(2022-m+1)}{m!}=0,
$$
which is a multiple of 7 . Then, since $x_{n} \geq x_{1}=2022$ for all $n$, we can write
$$
\begin{aligned}
\frac{x_{n}\left(x_{n}-1\right) \cdots\left(x_{n}-m+1\right)}{m!} & =\frac{x_{n}\left(x_{n}-1\right) \cdots\left(x_{n}-m+1\right)\left(x_{n}-m\right)\left(x_{n}-m-1\right) \cdots 1}{m!\times\left(x_{n}-m\right)\left(x_{n}-m-1\right) \cdots 1} \\
& =\frac{x_{n}!}{m!\left(x_{n}-m\right)!} .
\end{aligned}
$$

For a positive integer $n$, we define $\nu(n)$ as the exponent of 7 in the prime factorization of $n$. For example, $\nu(1)=0$ and $\nu(98)=2$. Note $\nu(a b)=\nu(a)+\nu(b)$ and $\nu(a / b)=\nu(a)-\nu(b)$. We prove the following two Lemmas:
- Lemma 1 :
$$
\nu(n!)=\sum_{i=1}^{d}\left\lfloor\frac{n}{7^{i}}\right\rfloor=\left\lfloor\frac{n}{7}\right\rfloor+\left\lfloor\frac{n}{49}\right\rfloor+\cdots
$$
where $d$ is the largest integer such that $7^{d} \leq n$, for all non-negative integers $n$. Proof: Note that
$$
\nu(n!)=\nu(1)+\nu(2)+\cdots+\nu(n) .
$$
$\nu(n!)$ has a contribution of +1 for each multiple of seven (less than or equal to $n$ ) and there are $\lfloor n / 7\rfloor$ such numbers. Each multiple of 49 contributes another +1 to $\nu(n!)$, and there are $\lfloor n / 49\rfloor$ such numbers. Generally, there is an additional +1 contributed for each multiple of $7^{i}$, of which there are $\left\lfloor n / 7^{i}\right\rfloor$ numbers. Adding up all these contributions, we get the desired result.
- Lemma 2: $\lfloor x\rfloor-\lfloor y\rfloor-\lfloor x-y\rfloor \geq 0$, for all reals $x$ and $y$, with equality if and only if $\{x\} \geq\{y\}$
Proof: Let $x=\lfloor x\rfloor+\{x\}$ and $y=\lfloor y\rfloor+\{y\}$. Then $x-y=\lfloor x\rfloor-\lfloor y\rfloor+\{x\}-\{y\}$ Since $0a$ which gives $C$
If we let $x=x_{n} / 7^{i}$ and $y=m / 7^{i}$, then this final sum consists of terms of the form $\lfloor x\rfloor-\lfloor y\rfloor-\lfloor x-y\rfloor \geq 0$. Therefore, we get that
$$
\begin{array}{ll}
7 \text { doesn't divide } \frac{x_{n}\left(x_{n}-1\right) \cdots\left(x_{n}-m+1\right)}{m!} & \\
\text { if and only if } \nu\left(\frac{x_{n}!}{m!\left(x_{n}-m\right)!}\right)=0 & \\
\text { if and only if }\left\lfloor\frac{x_{n}}{7^{i}}\right\rfloor=\left\lfloor\frac{m}{7^{i}}\right\rfloor+\left\lfloor\frac{x_{n}-m}{7^{i}}\right\rfloor & \text { for all } 0 \leq i \leq d \\
\text { if and only if }\left\{\frac{x_{n}}{7^{i}}\right\} \geq\left\{\frac{m}{7^{i}}\right\} & \text { for all } 0 \leq i \leq d .
\end{array}
$$
for all $0 \leq i \leq d$
for all $0 \leq i \leq d$.
by Lemma 2. This must hold for all $n$. Notice
$$
\left\{\frac{x_{n}}{7^{i}}\right\} \geq\left\{\frac{m}{7^{i}}\right\} \text { if and only if } 7^{i}\left\{\frac{x_{n}}{7^{i}}\right\} \geq 7^{i}\left\{\frac{m}{7^{i}}\right\}
$$
and $7^{b}\left\{a / 7^{b}\right\}$ is simply the remainder of $a$ modulo $7^{b}$. Hence we have
$$
\left\{\frac{x_{n}}{7^{i}}\right\} \geq\left\{\frac{m}{7^{i}}\right\} \text { if and only if } x_{n}\left(\bmod 7^{i}\right) \geq m\left(\bmod 7^{i}\right) .
$$

Since $x_{1}=2022=5 \cdot 7^{3}+6 \cdot 7^{2}+1 \cdot 7^{1}+6 \cdot 7^{0}$, we inductively get
$$
x_{n}=5 \cdot 7^{n+2}+6 \cdot 7^{n+1}+1 \cdot 7^{n}+6 \cdot 7^{n-1}+5 \cdot 7^{n-2}+\cdots+5 \cdot 7^{0} .
$$

Using this, we can find the smallest value of $x_{n}\left(\bmod 7^{i}\right)$ :
- For $i=1$, the smallest value is $5 \cdot 7^{0}$, when $n \geq 2$.
- For $i=2$, the smallest value is $1 \cdot 7^{1}+6 \cdot 7^{0}$, when $n=1$.
- For $i=3$, the smallest value is $1 \cdot 7^{2}+6 \cdot 7^{1}+5 \cdot 7^{0}$, when $n=2$.
- For $i=4$, the smallest value is $1 \cdot 7^{3}+6 \cdot 7^{2}+5 \cdot 7^{1}+5 \cdot 7^{0}$, when $n=3$.
- For $i \geq 5$, the smallest value is $5 \cdot 7^{3}+6 \cdot 7^{2}+1 \cdot 7^{1}+6 \cdot 7^{0}$, when $n=1$.

Thus if we write $m$ in the form $m=a_{3} \cdot 7^{3}+a_{2} \cdot 7^{2}+a_{1} \cdot 7^{1}+a_{0} \cdot 7^{0}$, where $0 \leq a_{i} \leq 6$, we must have $a_{0} \leq 5, a_{1} \leq 1, a_{2} \leq 1$, and $a_{3} \leq 1$, which are necessary and sufficient, Therefore the maximum integer $m$ is achieved when $a_{0}=5$ and $a_{1}=a_{2}=a_{3}=1$. This gives $m=7^{3}+7^{2}+7^{1}+5=404$.

Solution B: (Ishan Nath)
As in solution $\mathrm{A}$, we make the observation that
$$
\frac{x_{n}\left(x_{n}-1\right) \cdots\left(x_{n}-m+1\right)}{m!}=\binom{x_{n}}{m} .
$$
- Lemma: Let $a$ and $b$ be two positive integers with $\overline{a_{k} a_{k-1} \cdots a_{0}}$ and $\overline{b_{k} b_{k-1} \cdots b_{0}}$ the base 7 representations of $a$ and $b$ respectively, possibly with leading zeroes. $\binom{a}{b}$ is not a multiple of 7 if and only if $a_{i} \geq b_{i}$ for all $0 \leq i \leq k$.
Proof: By Lucas' Theorem

In particular, we have
$$
\binom{a}{b} \equiv 0(\bmod 7) \text { if and only if }\binom{a_{k}}{b_{k}} \equiv 0(\bmod 7) \text { for some } k
$$
if and only if $a_{k}<b_{k}$ for some $k$.

Now, note $x_{1}=2022=\overline{5616}$ in base 7, and thus $x_{n}=\overline{5616555 \cdots 55}$ in base 7 (where the rightmost $n-1$ digits are ' 5 's). Let $x_{n}=\overline{a_{k} a_{k-1} \cdots a_{0}}$ in base 7 . Hence if $m=$ $\overline{m_{k} m_{k-1} \cdots m_{0}}$, we get that
$7 \nmid\binom{x_{n}}{m}$ for all $n$ if and only if $a_{k} \geq m_{k}$ for all $n, k$.

When $n=1$ we have $a_{k}=0$ for $k \geq 4$, so this means $m_{k}=0$ for $k \geq 4$. Also notice that
- $a_{0} \geq 5$ with equality when $n \geq 2$,
- $a_{1} \geq 1$ with equality when $n=1$,
- $a_{2} \geq 1$ with equality when $n=2$, and
- $a_{3} \geq 1$ with equality when $n=3$.

This implies $m_{0} \leq 5$ and $m_{1}, m_{2}, m_{3} \leq 1$, which gives necessary and sufficient conditions for $m$.
The maximum value of $m$ can now be found by taking the maximum values of all $m_{k}$.
This gives $m=\overline{1115}$ in base 7 , or $m=404$ (in base 10)