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 "2019 AIME II Problems/Problem 4"
(add solution)
Line 1: Line 1:
 +
==Problem 4==
 
A standard six-sided fair die is rolled four times. The probability that the product of all four numbers rolled is a perfect square is <math>\dfrac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.
 
A standard six-sided fair die is rolled four times. The probability that the product of all four numbers rolled is a perfect square is <math>\dfrac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.
 +
 +
==Solution==
 +
Notice that, other than the number 5, the remaining numbers 1, 2, 3, 4, 6 are only divisible by 2 and/or 3. We can do some cases on the number of 5's rolled (note that there are <math>6^4 = 1296</math> outcomes).
 +
 +
Case 1 (easy): Four 5's are rolled. This has probability <math>\frac{1}{6^4}</math> of occurring.
 +
 +
Case 2: Two 5's are rolled.
 +
 +
Case 3: No 5's are rolled.
 +
 +
To find the number of outcomes for the latter two cases, we will use recursion. Consider a 5-sided die with faces numbered 1, 2, 3, 4, 6. For <math>n \ge 1</math>, let <math>a_n</math> equal the number of outcomes after rolling the die <math>n</math> times, with the property that the product is a square. Thus, <math>a_1 = 2</math> as 1 and 4 are the only possibilities.
 +
 +
To find <math>a_{n+1}</math> given <math>a_n</math> (where <math>n \ge 1</math>), we observe that if the first <math>n</math> rolls multiply to a perfect square, then the last roll must be 1 or 4. This gives <math>2a_n</math> outcomes. Otherwise, the first <math>n</math> rolls do not multiply to a perfect square (<math>5^n - a_n</math> outcomes). In this case, we claim that the last roll is uniquely determined (either 2, 3, or 6). If the product of the first <math>n</math> rolls is <math>2^x 3^y</math> where <math>x</math> and <math>y</math> are not both even, then we observe that if <math>x</math> and <math>y</math> are both odd, then the last roll must be 6; if only <math>x</math> is odd, the last roll must be 2, and if only <math>y</math> is odd, the last roll must be 3. Thus, we have <math>5^n - a_n</math> outcomes in this case, and <math>a_{n+1} = 2a_n + (5^n - a_n) = 5^n + a_n</math>.
 +
 +
Computing <math>a_2</math>, <math>a_3</math>, <math>a_4</math> gives <math>a_2 = 7</math>, <math>a_3 = 32</math>, and <math>a_4 = 157</math>. Thus for Case 3, there are 157 outcomes. For case 2, we multiply by <math>\binom{4}{2} = 6</math> to distribute the two 5's among four rolls. Thus the probability is
 +
 +
<cmath> \frac{1 + 6 \cdot 7 + 157}{6^4} = \frac{200}{6^4} = \frac{25}{162} \implies m+n = \boxed{187} </cmath>
 +
 +
-scrabbler94
 +
 +
==See Also==
 +
{{AIME box|year=2019|n=II|num-b=3|num-a=5}}
 +
{{MAA Notice}}

Revision as of 16:29, 22 March 2019

Problem 4

A standard six-sided fair die is rolled four times. The probability that the product of all four numbers rolled is a perfect square is $\dfrac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

Solution

Notice that, other than the number 5, the remaining numbers 1, 2, 3, 4, 6 are only divisible by 2 and/or 3. We can do some cases on the number of 5's rolled (note that there are $6^4 = 1296$ outcomes).

Case 1 (easy): Four 5's are rolled. This has probability $\frac{1}{6^4}$ of occurring.

Case 2: Two 5's are rolled.

Case 3: No 5's are rolled.

To find the number of outcomes for the latter two cases, we will use recursion. Consider a 5-sided die with faces numbered 1, 2, 3, 4, 6. For $n \ge 1$, let $a_n$ equal the number of outcomes after rolling the die $n$ times, with the property that the product is a square. Thus, $a_1 = 2$ as 1 and 4 are the only possibilities.

To find $a_{n+1}$ given $a_n$ (where $n \ge 1$), we observe that if the first $n$ rolls multiply to a perfect square, then the last roll must be 1 or 4. This gives $2a_n$ outcomes. Otherwise, the first $n$ rolls do not multiply to a perfect square ($5^n - a_n$ outcomes). In this case, we claim that the last roll is uniquely determined (either 2, 3, or 6). If the product of the first $n$ rolls is $2^x 3^y$ where $x$ and $y$ are not both even, then we observe that if $x$ and $y$ are both odd, then the last roll must be 6; if only $x$ is odd, the last roll must be 2, and if only $y$ is odd, the last roll must be 3. Thus, we have $5^n - a_n$ outcomes in this case, and $a_{n+1} = 2a_n + (5^n - a_n) = 5^n + a_n$.

Computing $a_2$, $a_3$, $a_4$ gives $a_2 = 7$, $a_3 = 32$, and $a_4 = 157$. Thus for Case 3, there are 157 outcomes. For case 2, we multiply by $\binom{4}{2} = 6$ to distribute the two 5's among four rolls. Thus the probability is

\[\frac{1 + 6 \cdot 7 + 157}{6^4} = \frac{200}{6^4} = \frac{25}{162} \implies m+n = \boxed{187}\]

-scrabbler94

See Also

2019 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME 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=2019_AIME_II_Problems/Problem_4&oldid=104754"