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 "2023 AMC 12A Problems/Problem 22"

m (forgot to sign my username :))
Line 3: Line 3:
  
 
<math>\textbf{(A)}~-1536\qquad\textbf{(B)}~96\qquad\textbf{(C)}~108\qquad\textbf{(D)}~116\qquad\textbf{(E)}~144</math>
 
<math>\textbf{(A)}~-1536\qquad\textbf{(B)}~96\qquad\textbf{(C)}~108\qquad\textbf{(D)}~116\qquad\textbf{(E)}~144</math>
 +
== Solution 1 (Very Thorough) ==
 +
First, we note that <math>f(1) = 1</math>, since the only divisor of <math>1</math> is itself. 
 +
 +
 +
Then, let's look at <math>f(p)</math> for <math>p</math> a prime. We see that
 +
<cmath>\sum_{d \mid p} d \cdot f\left(\frac{p}{d}\right) = 1</cmath>
 +
<cmath>1 \cdot f(p) + p \cdot f(1) = 1</cmath>
 +
<cmath>f(p) = 1 - p \cdot f(1)</cmath>
 +
<cmath>f(p) = 1-p</cmath>
 +
Nice. 
 +
 +
Now consider <math>f(p^k)</math>, for <math>k \in \mathbb{N}</math>.
 +
<cmath>\sum_{d \mid p^k} d \cdot f\left(\frac{p^k}{d}\right) = 1</cmath>
 +
<cmath>1 \cdot f(p^k) + p \cdot f(p^{k-1}) + p^2 \cdot f(p^{k-2}) + \dotsc + p^k f(1) = 1</cmath>. 
 +
 +
 +
It can be (strongly) inductively shown that <math>f(p^k) = f(p) = 1-p</math>. Here's how.   
 +
 +
We already showed <math>k=1</math> works. Suppose it holds for <math>k = n</math>, then
 +
 +
<cmath>1 \cdot f(p^n) + p \cdot f(p^{n-1}) + p^2 \cdot f(p^{n-2}) + \dotsc + p^n f(1) = 1 \implies f(p^m) = 1-p \; \forall \; m \leqslant n</cmath>
 +
 +
For <math>k = n+1</math>, we have
 +
 +
<cmath>1 \cdot f(p^{n+1}) + p \cdot f(p^{n}) + p^2 \cdot f(p^{n-1}) + \dotsc + p^{n+1} f(1) = 1</cmath>, then using <math>f(p^m) = 1-p \; \forall \; m \leqslant n</math>, we simplify to
 +
 +
<cmath>1 \cdot f(p^{n+1}) + p \cdot (1-p) + p^2 \cdot (1-p) + \dotsc + p^n \cdot (1-p) + p^{n+1} f(1) = 1</cmath>
 +
<cmath>f(p^{n+1}) + \sum_{i=1}^n p^i (1-p) + p^{n+1} = 1</cmath>
 +
<cmath>f(p^{n+1}) + p(1 - p^n) + p^{n+1} = 1</cmath>
 +
<cmath>f(p^{n+1}) + p = 1 \implies f(p^{n+1}) = 1-p</cmath>. 
 +
 +
Very nice! Now, we need to show that this function is multiplicative, i.e. <math>f(pq) = f(p) \cdot f(q)</math> for <math>p,q</math> prime.
 +
It's pretty standard, let's go through it quickly.
 +
<cmath>\sum_{d \mid pq} d \cdot f\left(\frac{pq}{d}\right) = 1</cmath>
 +
<cmath>1 \cdot f(pq) + p \cdot f(q) + q \cdot f(p) + pq \cdot f(1) = 1</cmath>
 +
Using our formulas from earlier, we have
 +
<cmath>f(pq) + p(1-q) + q(1-p) + pq = 1 \implies f(pq) = 1 - p(1-q) - q(1-p) - pq = (1-p)(1-q) = f(p) \cdot f(q)</cmath>
 +
 +
Great! We're almost done now.
 +
Let's actually plug in <math>2023 = 7 \cdot 17^2</math> into the original formula.
 +
<cmath>\sum_{d \mid 2023} d \cdot f\left(\frac{2023}{d}\right) = 1</cmath>
 +
<cmath>1 \cdot f(2023) + 7 \cdot f(17^2) + 17 \cdot f(7 \cdot 17) + 7 \cdot 17 \cdot f(17) + 17^2 \cdot f(7) + 7 \cdot 17^2 \cdot f(1) = 1</cmath>
 +
Let's use our formulas! We know
 +
<cmath>f(7) = 1-7 = -6</cmath>
 +
<cmath>f(17) = 1-17 = -16</cmath>
 +
<cmath>f(7 \cdot 17) = f(7) \cdot f(17) = (-6) \cdot (-16) = 96</cmath>
 +
<cmath>f(17^2) = f(17) = -16</cmath>
 +
 +
So plugging ALL that in, we have
 +
<cmath>f(2023) = 1 - \left(7 \cdot (-16) + 17 \cdot (-6) \cdot (-16) + 7 \cdot 17 \cdot (-16) + 17^2 \cdot (-6) + 7 \cdot 17^2\right)</cmath>
 +
which, be my guest simplifying, is <math>\boxed{\textbf{(B)} \ 96}</math>
 +
 +
~ <math>\color{magenta} zoomanTV</math>
  
 
==Video Solution by MOP 2024==
 
==Video Solution by MOP 2024==

Revision as of 16:02, 9 November 2023

Problem

Let $f$ be the unique function defined on the positive integers such that \[\sum_{d\mid n}d\cdot f\left(\frac{n}{d}\right)=1\] for all positive integers $n$. What is $f(2023)$?

$\textbf{(A)}~-1536\qquad\textbf{(B)}~96\qquad\textbf{(C)}~108\qquad\textbf{(D)}~116\qquad\textbf{(E)}~144$

Solution 1 (Very Thorough)

First, we note that $f(1) = 1$, since the only divisor of $1$ is itself.


Then, let's look at $f(p)$ for $p$ a prime. We see that \[\sum_{d \mid p} d \cdot f\left(\frac{p}{d}\right) = 1\] \[1 \cdot f(p) + p \cdot f(1) = 1\] \[f(p) = 1 - p \cdot f(1)\] \[f(p) = 1-p\] Nice.

Now consider $f(p^k)$, for $k \in \mathbb{N}$. \[\sum_{d \mid p^k} d \cdot f\left(\frac{p^k}{d}\right) = 1\] \[1 \cdot f(p^k) + p \cdot f(p^{k-1}) + p^2 \cdot f(p^{k-2}) + \dotsc + p^k f(1) = 1\].


It can be (strongly) inductively shown that $f(p^k) = f(p) = 1-p$. Here's how.

We already showed $k=1$ works. Suppose it holds for $k = n$, then

\[1 \cdot f(p^n) + p \cdot f(p^{n-1}) + p^2 \cdot f(p^{n-2}) + \dotsc + p^n f(1) = 1 \implies f(p^m) = 1-p \; \forall \; m \leqslant n\]

For $k = n+1$, we have

\[1 \cdot f(p^{n+1}) + p \cdot f(p^{n}) + p^2 \cdot f(p^{n-1}) + \dotsc + p^{n+1} f(1) = 1\], then using $f(p^m) = 1-p \; \forall \; m \leqslant n$, we simplify to

\[1 \cdot f(p^{n+1}) + p \cdot (1-p) + p^2 \cdot (1-p) + \dotsc + p^n \cdot (1-p) + p^{n+1} f(1) = 1\] \[f(p^{n+1}) + \sum_{i=1}^n p^i (1-p) + p^{n+1} = 1\] \[f(p^{n+1}) + p(1 - p^n) + p^{n+1} = 1\] \[f(p^{n+1}) + p = 1 \implies f(p^{n+1}) = 1-p\].

Very nice! Now, we need to show that this function is multiplicative, i.e. $f(pq) = f(p) \cdot f(q)$ for $p,q$ prime. It's pretty standard, let's go through it quickly. \[\sum_{d \mid pq} d \cdot f\left(\frac{pq}{d}\right) = 1\] \[1 \cdot f(pq) + p \cdot f(q) + q \cdot f(p) + pq \cdot f(1) = 1\] Using our formulas from earlier, we have \[f(pq) + p(1-q) + q(1-p) + pq = 1 \implies f(pq) = 1 - p(1-q) - q(1-p) - pq = (1-p)(1-q) = f(p) \cdot f(q)\]

Great! We're almost done now. Let's actually plug in $2023 = 7 \cdot 17^2$ into the original formula. \[\sum_{d \mid 2023} d \cdot f\left(\frac{2023}{d}\right) = 1\] \[1 \cdot f(2023) + 7 \cdot f(17^2) + 17 \cdot f(7 \cdot 17) + 7 \cdot 17 \cdot f(17) + 17^2 \cdot f(7) + 7 \cdot 17^2 \cdot f(1) = 1\] Let's use our formulas! We know \[f(7) = 1-7 = -6\] \[f(17) = 1-17 = -16\] \[f(7 \cdot 17) = f(7) \cdot f(17) = (-6) \cdot (-16) = 96\] \[f(17^2) = f(17) = -16\]

So plugging ALL that in, we have \[f(2023) = 1 - \left(7 \cdot (-16) + 17 \cdot (-6) \cdot (-16) + 7 \cdot 17 \cdot (-16) + 17^2 \cdot (-6) + 7 \cdot 17^2\right)\] which, be my guest simplifying, is $\boxed{\textbf{(B)} \ 96}$

~ $\color{magenta} zoomanTV$

Video Solution by MOP 2024

https://YouTube.com/watch?v=gdhVqdRhMsQ

~r00tsOfUnity

See also

2023 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 21 		Followed by
Problem 23
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_AMC_12A_Problems/Problem_22&oldid=201081"