New Zealand Mathematical Olympiad

Solution:
We claim the answer is $404$. First, we notice that $m \leq 2022$. Otherwise,
$$\frac{x_{1}(x_{1}-1)\cdots(x_{1}-m+1)}{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
$$\frac{x_{n}(x_{n}-1)\cdots(x_{n}-m+1)}{m!} = \frac{x_{n}(x_{n}-1)\cdots(x_{n}-m+1)(x_{n}-m)(x_{n}-m-1)\cdots 1}{m! \times (x_{n}-m)(x_{n}-m-1)\cdots 1} = \frac{x_{n}!}{m!(x_{n}-m)!}.$$
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(ab) = \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 + \dots + \left\lfloor \frac{n}{7^{d}} \right\rfloor,$$
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) + \dots + \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 $\lfloor n / 7^{i} \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 $0 < \{x\}, \{y\} < 1$, we have $-1 < \{x\} - \{y\} < 1$.

(a) If $0 \leq \{x\} - \{y\} < 1$, i.e. $\{x\} \geq \{y\}$, then $\lfloor x - y \rfloor = \lfloor x \rfloor - \lfloor y \rfloor$, so $\lfloor x \rfloor = \lfloor y \rfloor + \lfloor x - y \rfloor$.

(b) Otherwise, $\lfloor x - y \rfloor = \lfloor x \rfloor - \lfloor y \rfloor - 1$, so $\lfloor x \rfloor > \lfloor x \rfloor - 1 = \lfloor y \rfloor + \lfloor x - y \rfloor$.

Now we can use Lemma 1 to compute
$$\nu \left(\frac{x_{n}!}{m!(x_{n} - m)!}\right) = \nu(x_{n}!) - \nu(m!) - \nu((x_{n} - m)!) = \sum_{i = 1}^{d} \left\lfloor \frac{x_{n}}{7^{i}} \right\rfloor - \sum_{i = 1}^{l_{1}} \left\lfloor \frac{m}{7^{i}} \right\rfloor - \sum_{i = 1}^{l_{2}} \left\lfloor \frac{x_{n} - m}{7^{i}} \right\rfloor = \sum_{i = 1}^{d} \left( \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 \right).$$
Here $d$ is the largest integer such that $7^{d} \leq x_{n}$, $l_{1}$ is the largest integer such that $7^{l_{1}} \leq m$, and $l_{2}$ is the largest integer such that $7^{l_{2}} \leq x_{n} - m$. Increasing the range of the sums does not affect the result, as we are simply adding terms of the form $\lfloor a / 7^{b} \rfloor$, where $7^{b} > a$, which gives $0$.

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
$$7 \text{ doesn't divide } \frac{x_{n}(x_{n} - 1)\cdots(x_{n} - m + 1)}{m!}$$
if and only if
$$\nu \left(\frac{x_{n}!}{m!(x_{n} - m)!}\right) = 0$$
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$$
if and only if
$$\left\{ \frac{x_{n}}{7^{i}} \right\} \geq \left\{ \frac{m}{7^{i}} \right\}$$
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} \{ a / 7^{b} \}$ 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} \pmod{7^{i}} \geq m \pmod{7^{i}}.$$
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} + \dots + 5 \cdot 7^{0}.$$
Using this, we can find the smallest value of $x_{n}$ (mod $7^{i}$):
- 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:
As in solution A, we make the observation that
$$\frac{x_{n}(x_{n} - 1)\cdots(x_{n} - m + 1)}{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
$$\binom{a}{b} \equiv \prod_{i=0}^{k} \binom{a_{k}}{b_{k}} \pmod{7}.$$
In particular, we have
$$\binom{a}{b} \equiv 0 \pmod{7} \text{ if and only if } \binom{a_{k}}{b_{k}} \equiv 0 \pmod{7} \text{ for some } k$$
if and only if $a_{k} < b_{k}$ for some $k$.

Now, note $x_{1} = 2022 = 5616$ in base $7$, and thus $x_{n} = 5616555\dots 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} \text{ for all } n \text{ if and only if } a_{k} \geq m_{k} \text{ 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$,
- $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 = 1115$ in base $7$, or $m = 404$ (in base $10$).