Maths Olympiad Prep

Library / /11 of 11

Algebra Difficulty 7.7 National Olympiad, round 2 Prove it New Zealand

Problem:
The sequence x1,x2,x3,x_{1}, x_{2}, x_{3}, \ldots is defined by x1=2022x_{1} = 2022 and xn+1=7xn+5x_{n + 1} = 7x_{n} + 5 for all positive integers nn. Determine the maximum positive integer mm such that
xn(xn1)(xn2)(xnm+1)m! \frac{x_{n}(x_{n}-1)(x_{n}-2)\ldots(x_{n}-m+1)}{m!}
is never a multiple of 77 for any positive integer nn.

Solutions — 2

Solution 1

Solution:
We claim the answer is 404404. First, we notice that m2022m \leq 2022. Otherwise,
x1(x11)(x1m+1)m!=2022(20221)(2022m+1)m!=0, \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 77. Then, since xnx1=2022x_{n} \geq x_{1} = 2022 for all nn, we can write
xn(xn1)(xnm+1)m!=xn(xn1)(xnm+1)(xnm)(xnm1)1m!×(xnm)(xnm1)1=xn!m!(xnm)!. \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 nn, we define ν(n)\nu(n) as the exponent of 77 in the prime factorization of nn. For example, ν(1)=0\nu(1) = 0 and ν(98)=2\nu(98) = 2. Note ν(ab)=ν(a)+ν(b)\nu(ab) = \nu(a) + \nu(b) and ν(a/b)=ν(a)ν(b)\nu(a / b) = \nu(a) - \nu(b). We prove the following two Lemmas:

- Lemma 1:
ν(n!)=i=1dn7i=n7+n49++n7d, \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 dd is the largest integer such that 7dn7^{d} \leq n, for all non-negative integers nn.

Proof: Note that
ν(n!)=ν(1)+ν(2)++ν(n). \nu(n!) = \nu(1) + \nu(2) + \dots + \nu(n).
ν(n!)\nu(n!) has a contribution of +1+1 for each multiple of seven (less than or equal to nn) and there are n/7\lfloor n / 7 \rfloor such numbers. Each multiple of 4949 contributes another +1+1 to ν(n!)\nu(n!), and there are n/49\lfloor n / 49 \rfloor such numbers. Generally, there is an additional +1+1 contributed for each multiple of 7i7^{i}, of which there are n/7i\lfloor n / 7^{i} \rfloor numbers. Adding up all these contributions, we get the desired result.

- Lemma 2: xyxy0\lfloor x \rfloor - \lfloor y \rfloor - \lfloor x-y \rfloor \geq 0, for all reals xx and yy, with equality if and only if {x}{y}\{x\} \geq \{y\}.

Proof: Let x=x+{x}x = \lfloor x \rfloor + \{x\} and y=y+{y}y = \lfloor y \rfloor + \{y\}. Then xy=xy+{x}{y}x - y = \lfloor x \rfloor - \lfloor y \rfloor + \{x\} - \{y\}. Since 0<{x},{y}<10 < \{x\}, \{y\} < 1, we have 1<{x}{y}<1-1 < \{x\} - \{y\} < 1.

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

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

Now we can use Lemma 1 to compute
ν(xn!m!(xnm)!)=ν(xn!)ν(m!)ν((xnm)!)=i=1dxn7ii=1l1m7ii=1l2xnm7i=i=1d(xn7im7ixnm7i). \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 dd is the largest integer such that 7dxn7^{d} \leq x_{n}, l1l_{1} is the largest integer such that 7l1m7^{l_{1}} \leq m, and l2l_{2} is the largest integer such that 7l2xnm7^{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 a/7b\lfloor a / 7^{b} \rfloor, where 7b>a7^{b} > a, which gives 00.

If we let x=xn/7ix = x_{n} / 7^{i} and y=m/7iy = m / 7^{i}, then this final sum consists of terms of the form xyxy0\lfloor x \rfloor - \lfloor y \rfloor - \lfloor x - y \rfloor \geq 0. Therefore, we get that
7 doesn’t divide xn(xn1)(xnm+1)m! 7 \text{ doesn't divide } \frac{x_{n}(x_{n} - 1)\cdots(x_{n} - m + 1)}{m!}
if and only if
ν(xn!m!(xnm)!)=0 \nu \left(\frac{x_{n}!}{m!(x_{n} - m)!}\right) = 0
if and only if
xn7i=m7i+xnm7i for all 0id \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
{xn7i}{m7i} \left\{ \frac{x_{n}}{7^{i}} \right\} \geq \left\{ \frac{m}{7^{i}} \right\}
for all 0id0 \leq i \leq d.

By Lemma 2. This must hold for all nn. Notice
{xn7i}{m7i} if and only if 7i{xn7i}7i{m7i}, \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 7b{a/7b}7^{b} \{ a / 7^{b} \} is simply the remainder of aa modulo 7b7^{b}. Hence we have
{xn7i}{m7i} if and only if xn(mod7i)m(mod7i). \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 x1=2022=573+672+171+670x_{1} = 2022 = 5 \cdot 7^{3} + 6 \cdot 7^{2} + 1 \cdot 7^{1} + 6 \cdot 7^{0}, we inductively get
xn=57n+2+67n+1+17n+67n1+57n2++570. 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 xnx_{n} (mod 7i7^{i}):
- For i=1i = 1, the smallest value is 5705 \cdot 7^{0}, when n2n \geq 2.
- For i=2i = 2, the smallest value is 171+6701 \cdot 7^{1} + 6 \cdot 7^{0}, when n=1n = 1.
- For i=3i = 3, the smallest value is 172+671+5701 \cdot 7^{2} + 6 \cdot 7^{1} + 5 \cdot 7^{0}, when n=2n = 2.
- For i=4i = 4, the smallest value is 173+672+571+5701 \cdot 7^{3} + 6 \cdot 7^{2} + 5 \cdot 7^{1} + 5 \cdot 7^{0}, when n=3n = 3.
- For i5i \geq 5, the smallest value is 573+672+171+6705 \cdot 7^{3} + 6 \cdot 7^{2} + 1 \cdot 7^{1} + 6 \cdot 7^{0}, when n=1n = 1.

Thus if we write mm in the form m=a373+a272+a171+a070m = a_{3} \cdot 7^{3} + a_{2} \cdot 7^{2} + a_{1} \cdot 7^{1} + a_{0} \cdot 7^{0}, where 0ai60 \leq a_{i} \leq 6, we must have a05a_{0} \leq 5, a11a_{1} \leq 1, a21a_{2} \leq 1, and a31a_{3} \leq 1, which are necessary and sufficient.

Therefore the maximum integer mm is achieved when a0=5a_{0} = 5 and a1=a2=a3=1a_{1} = a_{2} = a_{3} = 1. This gives m=73+72+71+5=404m = 7^{3} + 7^{2} + 7^{1} + 5 = 404.

Solution 2

Solution:
As in solution A, we make the observation that
xn(xn1)(xnm+1)m!=(xnm). \frac{x_{n}(x_{n} - 1)\cdots(x_{n} - m + 1)}{m!} = \binom{x_{n}}{m}.
- Lemma: Let aa and bb be two positive integers with akak1a0\overline{a_{k}a_{k - 1}\cdots a_{0}} and bkbk1b0\overline{b_{k}b_{k - 1}\cdots b_{0}} the base 77 representations of aa and bb respectively, possibly with leading zeroes. (ab)\binom{a}{b} is not a multiple of 77 if and only if aibia_{i} \geq b_{i} for all 0ik0 \leq i \leq k.

Proof: By Lucas' Theorem
(ab)i=0k(akbk)(mod7). \binom{a}{b} \equiv \prod_{i=0}^{k} \binom{a_{k}}{b_{k}} \pmod{7}.
In particular, we have
(ab)0(mod7) if and only if (akbk)0(mod7) for some k \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 ak<bka_{k} < b_{k} for some kk.

Now, note x1=2022=5616x_{1} = 2022 = 5616 in base 77, and thus xn=561655555x_{n} = 5616555\dots 55 in base 77 (where the rightmost n1n - 1 digits are '5's). Let xn=akak1a0x_{n} = \overline{a_{k}a_{k - 1}\cdots a_{0}} in base 77. Hence if m=mkmk1m0m = \overline{m_{k}m_{k - 1}\cdots m_{0}}, we get that
7(xnm) for all n if and only if akmk for all n,k. 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=1n = 1 we have ak=0a_{k} = 0 for k4k \geq 4, so this means mk=0m_{k} = 0 for k4k \geq 4. Also notice that
- a05a_{0} \geq 5 with equality when n2n \geq 2,
- a11a_{1} \geq 1 with equality when n=1n = 1,
- a21a_{2} \geq 1 with equality when n=2n = 2,
- a31a_{3} \geq 1 with equality when n=3n = 3.

This implies m05m_{0} \leq 5 and m1,m2,m31m_{1}, m_{2}, m_{3} \leq 1, which gives necessary and sufficient conditions for mm.

The maximum value of mm can now be found by taking the maximum values of all mkm_{k}. This gives m=1115m = 1115 in base 77, or m=404m = 404 (in base 1010).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.