2021 April MIMC 10 Problems/Problem 11

Revision as of 13:40, 26 April 2021 by Cellsecret (talk | contribs) (Solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

How many factors of $16!$ is a perfect cube or a perfect square?

$\textbf{(A)} ~158 \qquad\textbf{(B)} ~164 \qquad\textbf{(C)} ~180 \qquad\textbf{(D)} ~1280 \qquad\textbf{(E)} ~3000$

Solution

We need to calculate the number of perfect squares and the number of perfect cubes and then subtract the number of $6$th power according to the principle of inclusion and exclusion. First of all, we need to factor $16!=2^{15}\cdot3^6\cdot5^3\cdot7^2\cdot11\cdot13$. Since we can choose even amount of each factor, there are a total of $8\cdot4\cdot2\cdot2\cdot1\cdot1=128$ perfect squares. Using the same logic, any number that is a cube must have multiple of $3$ factors for each factor. Therefore, there are $6\cdot3\cdot2\cdot1\cdot1\cdot1=36$ cubes. In addition, there are $3\cdot2\cdot1\cdot1\cdot1\cdot1=6$ numbers with $6$th power. In total, there are $128+36-6=\fbox{\textbf{(A)} 158}$ perfect square or perfect cube factors of $16!$.