2019 CIME I Problems/Problem 15

Let $(\mathcal{F}_n)_{n \geq 1}$ be a sequence of functions going from $\mathbb{N}^+$ to $\mathbb{N}^+$ defined recursively by $\mathcal{F}_1(n)=1$ and \[\mathcal{F}_k(n)=\sum_{d|n}\mathcal{F}_{k-1}(d)\] for all $k \geq 1$. Compute the greatest integer less than or equal to $\frac{\mathcal{F}_{2019}(864)}{\mathcal{F}_{2019}(648)}$.

Solution

Note that the function on the right is $F_{k}(n)$’s sum function, so if $F_{k}(n)$ is multiplicative so is $F_{k+1}(n)$. Now since $F_{1}(n)=1$ is multiplicative, it is not hard to see using induction that all $F_{k}(n)$ are multiplicative too.

Therefore we can just consider one prime and its exponent. Say $n=p_1^{e_1}\cdots p_k^{e_k}$. Note that $F_{1}(p^e)=1$ and $F_2(p^e)=1+1+1+\cdots +1=e+1=\binom{e+1}{1}$. Then $F_3(p^e)=\sum_{i=0}^e \binom{i+1}{1} =\binom{e+2}{2}$ by the Hockey Stick Identity. We can continue this process (summing and using the hockey stick identity for each exponent) to obtain $F_{2019}(p^e)=\binom{e+2018}{2018}$.

Now $864=2^5 3^3$ and $648=2^3 3^4$ thus our answer is $\frac{\binom{2023}{2018}\binom{2021}{2018}}{\binom{2021}{2018}\binom{2022}{2018}}=\dfrac{2023 \cdot 2022 \cdot 2021 \cdot 2020 \cdot 2019 \cdot 24}{2022 \cdot 2021 \cdot 2020 \cdot 2019 \cdot 120} = 2023 \cdot \frac{24}{120} = \frac{2023}{5} = 404.6 \rightarrow \boxed{404}$.

See also

2019 CIME I (ProblemsAnswer KeyResources)
Preceded by
Problem 14
Followed by
Last problem
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All CIME Problems and Solutions

The problems on this page are copyrighted by the MAC's Christmas Mathematics Competitions. AMC logo.png