Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2019 CIME I Problems/Problem 15"

(problem and solution)
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
Let <math>{\mathcal{F}_n}_{n \geq 1}</math> be a sequence of functions going from <math>\mathbb{N}^+</math> to <math>\mathbb{N}^+</math> defined recursively by <math>\mathcal{F}_1(n)=1</math> and <cmath>\mathcal{F}_k(n)=\sum_{d|n}\mathcal{F}_{k-1}(d)</cmath> for all <math>k \geq 1</math>. Compute the greatest integer less than or equal to <math>\frac{\mathcal{F}_{2019}(864)}{\mathcal{F}_{2019}(648)}</math>.
+
Let <math>(\mathcal{F}_n)_{n \geq 1}</math> be a sequence of functions going from <math>\mathbb{N}^+</math> to <math>\mathbb{N}^+</math> defined recursively by <math>\mathcal{F}_1(n)=1</math> and <cmath>\mathcal{F}_k(n)=\sum_{d|n}\mathcal{F}_{k-1}(d)</cmath> for all <math>k \geq 1</math>. Compute the greatest integer less than or equal to <math>\frac{\mathcal{F}_{2019}(864)}{\mathcal{F}_{2019}(648)}</math>.
  
 
==Solution==
 
==Solution==
Line 9: Line 9:
  
 
==See also==
 
==See also==
−
{{CIME box|year=2019|num-b=14|after=Last problem}}
+
{{CIME box|year=2019|n=I|num-b=14|after=Last problem}}
  
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]
 
{{MAC Notice}}
 
{{MAC Notice}}

Latest revision as of 17:57, 4 October 2020

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 (Problems • Answer Key • Resources)
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_CIME_I_Problems/Problem_15&oldid=134604"