← Sensim Lab Sensim Math

AMC 10 · 2020 · #15

Grade 7 arithmetic
Archetype Small-Domain Constrained Search
factorialprime-factorizationdivisor-countperfect-squareslegendre-formulaprobability-basic identify-subproblemssystematic-enumeration ↑ Prerequisites: prime-factorizationdivisor-count
📏 Long solution 💡 3 insights

Problem

Pick an answer.

(A)
3
(B)
5
(C)
12
(D)
18
(E)
23
View mode:

Toolkit + CCSS Solution

Understand

Restated: A divisor of $12!$ is chosen at random (each divisor equally likely). The probability that the chosen divisor is a perfect square equals $\dfrac{m}{n}$ for relatively prime positive integers $m, n$. Find $m + n$.

Givens: Sample: a uniformly random positive divisor of $12!$; Success: the divisor is a perfect square ($k^2$ for some positive integer $k$); $\dfrac{m}{n}$ is the probability in lowest terms; Answer choices: $3,\; 5,\; 12,\; 18,\; 23$ (official: $m + n = 23$, choice $\textbf{(E)}$)

Unknowns: $m + n$

Understand

Restated: A divisor of $12!$ is chosen at random (each divisor equally likely). The probability that the chosen divisor is a perfect square equals $\dfrac{m}{n}$ for relatively prime positive integers $m, n$. Find $m + n$.

Givens: Sample: a uniformly random positive divisor of $12!$; Success: the divisor is a perfect square ($k^2$ for some positive integer $k$); $\dfrac{m}{n}$ is the probability in lowest terms; Answer choices: $3,\; 5,\; 12,\; 18,\; 23$ (official: $m + n = 23$, choice $\textbf{(E)}$)

Plan

Primary tool: #7 Identify Subproblems

Secondary: #2 Make a Systematic List, #3 Eliminate Possibilities

Tool #7 (Subproblems): break the question into four cleanly separate pieces — (1) prime factorization of $12!$, (2) total number of divisors, (3) number of perfect-square divisors, (4) probability and $m + n$. Each piece is a small standalone calculation. Tool #2 (Systematic List): list the primes $\le 12$ in order ($2, 3, 5, 7, 11$) and, for each prime, list the legal exponent choices and the smaller "must be even" sub-list. Tool #3 (Eliminate): match $m + n$ to the answer choices.

Execute — Answer: E

#2 Make a Systematic List 6.NS.B.4 Step 1
  • Prime-factorize $12!$ using Legendre's count (each multiple of $p^k$ inside $\{1, 2, \ldots, 12\}$ contributes one factor of $p$).
  • Exponent of $2$: $\lfloor 12/2 \rfloor + \lfloor 12/4 \rfloor + \lfloor 12/8 \rfloor = 6 + 3 + 1 = 10$.
  • Exponent of $3$: $\lfloor 12/3 \rfloor + \lfloor 12/9 \rfloor = 4 + 1 = 5$.
  • Exponent of $5$: $\lfloor 12/5 \rfloor = 2$.
  • Exponent of $7$: $\lfloor 12/7 \rfloor = 1$.
  • Exponent of $11$: $\lfloor 12/11 \rfloor = 1$.
$$12! = 2^{10} \cdot 3^{5} \cdot 5^{2} \cdot 7^{1} \cdot 11^{1}$$

💡 Grade 6 prime factors: list each prime and count how many times it appears across $1, 2, \ldots, 12$.

#7 Identify Subproblems 7.SP.C.8 Step 2
  • Count the total number of divisors of $12!$.
  • A divisor picks an independent exponent $b_i$ with $0 \le b_i \le a_i$ for each prime.
  • With exponents $(10, 5, 2, 1, 1)$, the number of choices for each is $(11, 6, 3, 2, 2)$.
  • By the multiplication principle, total divisors $= 11 \cdot 6 \cdot 3 \cdot 2 \cdot 2 = 792$.
$$\#\text{divisors} = (10+1)(5+1)(2+1)(1+1)(1+1) = 11 \cdot 6 \cdot 3 \cdot 2 \cdot 2 = 792$$

💡 Grade 7 product rule: independent choices multiply.

#2 Make a Systematic List 6.EE.A.1 Step 3
  • Count the perfect-square divisors.
  • A divisor $2^{b_1} \cdot 3^{b_2} \cdot 5^{b_3} \cdot 7^{b_4} \cdot 11^{b_5}$ is a perfect square exactly when every $b_i$ is even.
  • List the even choices in each range: $b_1 \in \{0, 2, 4, 6, 8, 10\}$ — $6$ choices.
  • $b_2 \in \{0, 2, 4\}$ — $3$ choices.
  • $b_3 \in \{0, 2\}$ — $2$ choices.
  • $b_4 \in \{0\}$ — $1$ choice.
  • $b_5 \in \{0\}$ — $1$ choice.
$$\#\text{square divisors} = 6 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 36$$

💡 Grade 6 exponents: a perfect square needs every prime's exponent to be even.

#7 Identify Subproblems 6.NS.B.4 Step 4
  • Compute the probability and reduce.
  • $\dfrac{36}{792}$.
  • Both numerator and denominator share the factor $6 \cdot 3 \cdot 2 = 36$, so $\dfrac{36}{792} = \dfrac{1}{22}$.
  • Since $\gcd(1, 22) = 1$, this is already in lowest terms with $m = 1, n = 22$.
$$\dfrac{36}{792} = \dfrac{1}{22},\quad \gcd(1, 22) = 1$$

💡 Grade 6 GCF / fraction reduction: divide top and bottom by their largest common factor.

#7 Identify Subproblems 1.OA.A.1 Step 5

Add: $m + n = 1 + 22 = 23$.

$$m + n = 1 + 22 = 23$$

💡 Grade 1 addition: a tiny final sum after all the heavy lifting.

#3 Eliminate Possibilities 4.NBT.A.2 Step 6
  • Match to the choices: $23$ is option (E).
  • The other choices ($3, 5, 12, 18$) would correspond to forgetting an exponent factor, mis-reducing the fraction, or stopping before computing $m + n$.
$$m + n = 23 \;\Rightarrow\; \textbf{(E)}$$

💡 Grade 4 comparison: only one option equals $23$.

[1] #2 6.NS.B.4 Prime-factorize $12!$ using Legendre's count (each multiple of $p^k$ inside ${1
[2] #7 7.SP.C.8 Count the total number of divisors of $12!$. A divisor picks an independent expo
[3] #2 6.EE.A.1 Count the perfect-square divisors. A divisor $2^{b_1} \cdot 3^{b_2} \cdot 5^{b_3
[4] #7 6.NS.B.4 Compute the probability and reduce. $\dfrac{36}{792}$. Both numerator and denomi
[5] #7 1.OA.A.1 Add: $m + n = 1 + 22 = 23$.
[6] #3 4.NBT.A.2 Match to the choices: $23$ is option (E). The other choices ($3, 5, 12, 18$) wou

Review

Reasonableness: Quick sanity: $\dfrac{1}{22}$ is the rough chance, $\approx 4.5\%$. There's a clean conceptual reason — each odd-exponent prime contributes a factor $\dfrac{\lceil (a_i + 1)/2 \rceil}{a_i + 1}$ to the ratio. For our exponents $(10, 5, 2, 1, 1)$, that's $\dfrac{6}{11} \cdot \dfrac{3}{6} \cdot \dfrac{2}{3} \cdot \dfrac{1}{2} \cdot \dfrac{1}{2} = \dfrac{6 \cdot 3 \cdot 2}{11 \cdot 6 \cdot 3 \cdot 2 \cdot 2} = \dfrac{1}{22}$. ✓ Matches. $m + n = 23$.

Alternative: Tool #16 (Complement / Change Focus): instead of counting perfect-square divisors directly, count by independent probabilities. For each prime $p_i$ with $a_i + 1$ allowed exponents, the chance that a uniformly chosen exponent is even is $\dfrac{\lfloor a_i/2 \rfloor + 1}{a_i + 1}$. Multiplying gives $\dfrac{6}{11} \cdot \dfrac{3}{6} \cdot \dfrac{2}{3} \cdot \dfrac{1}{2} \cdot \dfrac{1}{2} = \dfrac{1}{22}$. So $m + n = 23$, answer (E).

CCSS standards used (min grade 7)

  • 1.OA.A.1 Solve addition and subtraction word problems within 20 (Adding $m + n = 1 + 22 = 23$.)
  • 4.NBT.A.2 Read and write multi-digit whole numbers and compare using symbols (Matching the final sum $23$ to the answer choices.)
  • 6.EE.A.1 Write and evaluate numerical expressions involving whole-number exponents (Identifying a perfect square as a number whose prime factorization has only even exponents.)
  • 6.NS.B.4 Find greatest common factor and least common multiple of two numbers (Prime-factorizing $12!$ and reducing $\dfrac{36}{792}$ to $\dfrac{1}{22}$ via the shared factor $36$.)
  • 7.SP.C.8 Find probabilities of compound events using organized lists, tables, and simulation (Multiplying $11 \cdot 6 \cdot 3 \cdot 2 \cdot 2 = 792$ and $6 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 36$ for independent exponent choices.)

⭐ This AMC 10 problem only needs Grade 7 counting you already know! Factor $12! = 2^{10} \cdot 3^{5} \cdot 5^{2} \cdot 7 \cdot 11$. Total divisors: $11 \cdot 6 \cdot 3 \cdot 2 \cdot 2 = 792$. Perfect-square divisors need every exponent even, so count even choices in each range: $6 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 36$. Probability $= \dfrac{36}{792} = \dfrac{1}{22}$, so $m + n = 1 + 22 = \mathbf{23}$, answer (E).

⭐ This AMC 10 problem only needs Grade 7 counting you already know! Factor $12! = 2^{10} \cdot 3^{5} \cdot 5^{2} \cdot 7 \cdot 11$. Total divisors: $11 \cdot 6 \cdot 3 \cdot 2 \cdot 2 = 792$. Perfect-square divisors need every exponent even, so count even choices in each range: $6 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 36$. Probability $= \dfrac{36}{792} = \dfrac{1}{22}$, so $m + n = 1 + 22 = \mathbf{23}$, answer (E).

More like this

Same archetype — closest grade level first.