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

2020 AMC 10B Problems/Problem 25

Revision as of 10:50, 23 December 2021 by Isabelchen (talk | contribs)

Solution 7(Integer Partition)

Note that $96 = 2^5 \cdot 3$. $D(n)$ depends on dividing $2^5$ into different terms, which is the integer partition of $5$.

Divide $96$ into $1$ term:

There is only one way. $\underline{\textbf{1}}$


Divide $96$ into $2$ terms: 

Case $1$: $3$ is alone
$(2^5,3)$ has ${\textbf{2}}$ different arrangements.

Case $2$: $3$ is with $2^n$
$5 = 1 + 4 = 2 + 3$. For $(2, 2^4)$ and $(2^2, 2^3)$, $3$ can be with any term from the $2$ tuples, and the arrangement of the $2$ terms is $2$. $2 \cdot 2 \cdot 2 = {\textbf{8}}$

$2 + 8 = \underline{\textbf{10}}$


Divide $96$ into $3$ terms: 

Case $1$: $3$ is alone
$5 = 2 + 3 = 1 + 4$. For $(2^2, 2^3, 3)$ and $(2, 2^4, 3)$, there are $3!$ arrangements each. $2 \cdot 3! = {\textbf{12}}$

Case $2$: $3$ is with $2^n$
$5 = 1 + 1 + 3 = 1 + 2 + 2$. For $(2, 2, 2^3)$ and $(2, 2^2, 2^2)$, $3$ can be with any term from the $2$ tuples. If $3$ is with $2^3$ for the first tuple, or $2$ for the second tuple, the number of arrangements will be $3$ for each. If $3$ is with $2$ for the first tuple, or $2^2$ for the second tuple, the number or arrangements will be $6$ for each. $2 \cdot 3 + 2 \cdot 6 = {\textbf{18}}$

$12 + 18 = \underline{\textbf{30}}$


Divide $96$ into $4$ terms: 

Case $1$: $3$ is alone
$5 = 1 + 1 + 3 = 1 + 2 + 2$. For $(2, 2, 2^3, 3)$ and $(2, 2^2, 2^2, 3)$, there are $\frac{4!}{2!}$ arrangements each. $2 \cdot \frac{4!}{2!} = {\textbf{24}}$

Case $2$: $3$ is with $2^n$
$5 = 1 + 1 + 1 + 2$. For $(2, 2, 2, 2^2)$, $3$ can be with any term from the tuple. If $3$ is with $2^2$, the number of arrangements will be $\frac{4!}{3!}$. If $3$ is with $2$, the number or arrangements will be $\frac{4!}{2!}$. $\frac{4!}{3!} + \frac{4!}{2!} = {\textbf{16}}$

$24 + 16 = \underline{\textbf{40}}$


Divide $96$ into $5$ terms:

When dividing $5$ into $5$ parts there are $2$ cases. 

Case $1$: $3$ is alone
$5 = 1 + 1 + 1 + 2$. For $(2, 2, 2, 2^2, 3)$, there are $\frac{5!}{3!}$ arrangements. $\frac{5!}{3!} = {\textbf{20}}$

Case $2$: $3$ is with $2^n$
$5 = 1 + 1 + 1 + 1 + 1$. For $(2, 2, 2, 2, 2)$, $3$ can only be with $2$. The number or arrangements will be $\frac{5!}{4!} = \textbf{5}$

$20 + 5 = \underline{\textbf{25}}$


Divide $96$ into $6$ terms:

$5 = 1 + 1 + 1 + 1 + 1$, $\frac{6!}{5!} = \underline{\textbf{6}}$

$1 + 10 + 12 + 18 + 24 + 16 + 20 + 5 + 6 = \boxed{\textbf{(A) }112}$

~isabelchen

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_AMC_10B_Problems/Problem_25&oldid=168355"