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"

(→‎Solution 2)
(→‎Solution 2)
Line 25: Line 25:
 
We can solve this without finding the amount of cases. Notice when we roll a 1 or a 4, it does not affect whether or not the product is a square number. We have a 1/3 chance of rolling either a 1 or 4. We have a 2/3 chance of rolling a 2,3,5 or 6. Lets call rolling 1 or 4 rolling a dud.  
 
We can solve this without finding the amount of cases. Notice when we roll a 1 or a 4, it does not affect whether or not the product is a square number. We have a 1/3 chance of rolling either a 1 or 4. We have a 2/3 chance of rolling a 2,3,5 or 6. Lets call rolling 1 or 4 rolling a dud.  
  
−
Probability of rolling 4 duds: (1/3)^4
+
Probability of rolling 4 duds: <math> (\frac{1}{3})^4 </math>
  
−
Probability of rolling 3 duds: 4 * (1/3)^3 * (2/3)
+
Probability of rolling 3 duds: <math> 4 * (\frac{1}{3})^3 * \frac{2}{3} </math>
  
−
Probability of rolling 2 duds: 6 * (1/3)^2 * (2/3)^2
+
Probability of rolling 2 duds: <math> 6 * (\frac{1}{3})^2 * (\frac{2}{3})^2 </math>
  
−
Probability of rolling 1 dud: 4 * (1/3) * (2/3)^3
+
Probability of rolling 1 dud: <math> 4 * \frac{1}{3} * (\frac{2}{3})^3 </math>
−
 
 
−
Probability of rolling 0 duds: (2/3)^4
 
  
 +
Probability of rolling 0 duds: <math> (\frac{2}{3})^4 </math>
 +
 
Now we will find the probability of a square product given we have rolled a each amount of duds
 
Now we will find the probability of a square product given we have rolled a each amount of duds
  
Line 41: Line 41:
 
Probability of getting a square product given 3 duds: 0 (you will have 1 non-dud and that's never going to be square)
 
Probability of getting a square product given 3 duds: 0 (you will have 1 non-dud and that's never going to be square)
  
−
Probability of getting a square product given 2 duds: 1/4 (as long as our two non-duds are the same, our product will be square)
+
Probability of getting a square product given 2 duds: <math> \frac{1}{4}</math> (as long as our two non-duds are the same, our product will be square)
  
−
Probability of getting a square product given 1 duds: (3!/4^3) = 3/32 (the only way to have a square  product is rolling a 2,3 and 6. There are 3! ways of doing that and a total of 4^3 ways to roll 3 non-duds).
+
Probability of getting a square product given 1 duds: <math>\frac{3!}{4^3}</math> = <math>\frac{3}{32}</math>(the only way to have a square  product is rolling a 2,3 and 6. There are 3! ways of doing that and a total of <math>4^3</math> ways to roll 3 non-duds).
  
−
Probability of getting a square product given 0 duds: 40/4^4 = 5/32 (We can have any two non-duds twice. For example, 2,2,5,5. There are 4c2 ways of choosing which two non-duds to use and 4c2 ways of choosing how to arrange those 4 numbers. That gives us 6*6=36 combinations. We can also have 2,2,2,2 or 3,3,3,3 or 5,5,5,5 or 6,6,6,6. This gives us a total of 40 combinations).
+
Probability of getting a square product given 0 duds: <math> \frac{40}{4^4} </math>= <math>\frac{5}{32} </math> (We can have any two non-duds twice. For example, 2,2,5,5. There are <math>\binom{4}{2} = 6</math> ways of choosing which two non-duds to use and <math>\binom{4}{2} = 6</math> ways of choosing how to arrange those 4 numbers. That gives us 6*6=36 combinations. We can also have 2,2,2,2 or 3,3,3,3 or 5,5,5,5 or 6,6,6,6. This gives us a total of 40 combinations).
  
 
We multiply each probability of rolling k duds with the probability of getting a square product given k duds and then sum all the values.
 
We multiply each probability of rolling k duds with the probability of getting a square product given k duds and then sum all the values.
  
−
(1/3)^4 * 1 + 4 * (1/3)^3 * (2/3) * 0 + 6 * (1/3)^2 * (2/3)^2 * 1/4 + 4 * (1/3) * (2/3)^3 * 3/32 + (2/3)^4 * 5/32 = 25/162.
+
<cmath> (\frac{1}{3})^4 * 1 + 4 * (\frac{1}{3})^3 * \frac{2}{3} * 0 + 6 * (\frac{1}{3})^2 * (\frac{2}{3})^2 * \frac{1}{4} + 4 * \frac{1}{3} * (\frac{2}{3})^3 * \frac{3}{32} + (\frac{2}{3})^4 * \frac{5}{32} = \frac{25}{162}. </cmath>
  
−
25+162 = <cmath> \boxed{187} </cmath>
+
<math>25+162</math> = <math>\boxed{187}</math>  
  
 
-dnaidu (silverlizard)
 
-dnaidu (silverlizard)

Revision as of 22:01, 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 $\tfrac{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

Solution 2

We can solve this without finding the amount of cases. Notice when we roll a 1 or a 4, it does not affect whether or not the product is a square number. We have a 1/3 chance of rolling either a 1 or 4. We have a 2/3 chance of rolling a 2,3,5 or 6. Lets call rolling 1 or 4 rolling a dud.

Probability of rolling 4 duds: $(\frac{1}{3})^4$

Probability of rolling 3 duds: $4 * (\frac{1}{3})^3 * \frac{2}{3}$

Probability of rolling 2 duds: $6 * (\frac{1}{3})^2 * (\frac{2}{3})^2$

Probability of rolling 1 dud: $4 * \frac{1}{3} * (\frac{2}{3})^3$

Probability of rolling 0 duds: $(\frac{2}{3})^4$

Now we will find the probability of a square product given we have rolled a each amount of duds

Probability of getting a square product given 4 duds: 1

Probability of getting a square product given 3 duds: 0 (you will have 1 non-dud and that's never going to be square)

Probability of getting a square product given 2 duds: $\frac{1}{4}$ (as long as our two non-duds are the same, our product will be square)

Probability of getting a square product given 1 duds: $\frac{3!}{4^3}$ = $\frac{3}{32}$(the only way to have a square product is rolling a 2,3 and 6. There are 3! ways of doing that and a total of $4^3$ ways to roll 3 non-duds).

Probability of getting a square product given 0 duds: $\frac{40}{4^4}$= $\frac{5}{32}$ (We can have any two non-duds twice. For example, 2,2,5,5. There are $\binom{4}{2} = 6$ ways of choosing which two non-duds to use and $\binom{4}{2} = 6$ ways of choosing how to arrange those 4 numbers. That gives us 6*6=36 combinations. We can also have 2,2,2,2 or 3,3,3,3 or 5,5,5,5 or 6,6,6,6. This gives us a total of 40 combinations).

We multiply each probability of rolling k duds with the probability of getting a square product given k duds and then sum all the values.

\[(\frac{1}{3})^4 * 1 + 4 * (\frac{1}{3})^3 * \frac{2}{3} * 0 + 6 * (\frac{1}{3})^2 * (\frac{2}{3})^2 * \frac{1}{4} + 4 * \frac{1}{3} * (\frac{2}{3})^3 * \frac{3}{32} + (\frac{2}{3})^4 * \frac{5}{32} = \frac{25}{162}.\]

$25+162$ = $\boxed{187}$

-dnaidu (silverlizard)

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=104842"