Difference between revisions of "2021 April MIMC 10 Problems/Problem 11"

(Created page with "How many factors of <math>16!</math> is a perfect cube or a perfect square? <math>\textbf{(A)} ~158 \qquad\textbf{(B)} ~164 \qquad\textbf{(C)} ~180 \qquad\textbf{(D)} ~1280 \...")
 
(Solution)
 
Line 3: Line 3:
 
<math>\textbf{(A)} ~158 \qquad\textbf{(B)} ~164 \qquad\textbf{(C)} ~180 \qquad\textbf{(D)} ~1280 \qquad\textbf{(E)} ~3000</math>
 
<math>\textbf{(A)} ~158 \qquad\textbf{(B)} ~164 \qquad\textbf{(C)} ~180 \qquad\textbf{(D)} ~1280 \qquad\textbf{(E)} ~3000</math>
 
==Solution==
 
==Solution==
To be Released on April 26th.
+
We need to calculate the number of perfect squares and the number of perfect cubes and then subtract the number of <math>6</math>th power according to the principle of inclusion and exclusion. First of all, we need to factor <math>16!=2^{15}\cdot3^6\cdot5^3\cdot7^2\cdot11\cdot13</math>. Since we can choose even amount of each factor, there are a total of <math>8\cdot4\cdot2\cdot2\cdot1\cdot1=128</math> perfect squares. Using the same logic, any number that is a cube must have multiple of <math>3</math> factors for each factor. Therefore, there are <math>6\cdot3\cdot2\cdot1\cdot1\cdot1=36</math> cubes. In addition, there are <math>3\cdot2\cdot1\cdot1\cdot1\cdot1=6</math> numbers with <math>6</math>th power. In total, there are <math>128+36-6=\fbox{\textbf{(A)} 158}</math> perfect square or perfect cube factors of <math>16!</math>.

Latest revision as of 13:40, 26 April 2021

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!$.