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 "2021 JMPSC Invitationals Problems/Problem 15"

m
(→‎Solution)
 
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
Note that <math>2021 \cdot 2^{2021} = 43 \cdot 47 \cdot 2^{2021}</math>, so we want to "select" for the numbers that are not factors of <math>2021</math>. This is <math>\frac{2022}{2022 \cdot 2 \cdot 2} = \frac{1}{4}</math> of them. In addition, for the factors of <math>2</math>, exactly <math>\frac{1}{2}</math> of them are perfect squares, and for each turn, there is a <math>\frac{1}{2}</math> probability that the product will be a perfect square since the product of the numbers before does not affect the probability (in this case). Therefore, for each turn, there is a <math>\frac{1}{8}</math> probability Abhishek will end, which means he is expected to end on his <math>\boxed{8} \text{ th turn}</math>
+
Note that <math>2021 \cdot 2^{2021} = 43 \cdot 47 \cdot 2^{2021}</math>, so we want to "select" for the numbers that are not factors of <math>2021</math>. This is <math>\frac{2022}{2022 \cdot 2 \cdot 2} = \frac{1}{4}</math> of them. In addition, for the factors of <math>2</math>, exactly <math>\frac{1}{2}</math> of them are perfect squares, and for each turn, there is a <math>\frac{1}{2}</math> probability that the product will be a perfect square since the product of the numbers before does not affect the probability (in this case). Therefore, for each turn, there is a <math>\frac{1}{8}</math> probability Abhishek will end, which means he is expected to end on his <math>\boxed{8}</math>th turn.
  
 
~Geometry285
 
~Geometry285

Latest revision as of 23:02, 11 July 2021

Problem

Abhishek is choosing positive integer factors of $2021 \times 2^{2021}$ with replacement. After a minute passes, he chooses a random factor and writes it down. Abhishek repeats this process until the first time the product of all numbers written down is a perfect square. Find the expected number of minutes it takes for him to stop.

Solution

Note that $2021 \cdot 2^{2021} = 43 \cdot 47 \cdot 2^{2021}$, so we want to "select" for the numbers that are not factors of $2021$. This is $\frac{2022}{2022 \cdot 2 \cdot 2} = \frac{1}{4}$ of them. In addition, for the factors of $2$, exactly $\frac{1}{2}$ of them are perfect squares, and for each turn, there is a $\frac{1}{2}$ probability that the product will be a perfect square since the product of the numbers before does not affect the probability (in this case). Therefore, for each turn, there is a $\frac{1}{8}$ probability Abhishek will end, which means he is expected to end on his $\boxed{8}$th turn.

~Geometry285

Solution 2

It factors as $43 \cdot 47 \cdot 2^{2021}$, and say that the form of the product of the numbers is $43^a \cdot 47^b \cdot 2^c$. With equal probability, $a$ is even and $a$ is odd at every step since at the first step, $a=0$ appears with $\frac{1}{2}$ probability and $a=1$ appears with $\frac{1}{2}$ probability. The same applies to 47, or $b$. The same goes for $c$. Because the numbers of $c$ range from 0 to 2021 each time, then obviously half of those numbers are odd and half are even. The probability of each $a,b,c$ being even (which is the requirement for being a perfect square) is $\frac{1}{2}$, so the answer should be $\left(\frac{1}{\frac{1}{2}}\right)^3= \boxed{8}$.

~lamphead

See also

  1. Other 2021 JMPSC Invitationals Problems
  2. 2021 JMPSC Invitationals Answer Key
  3. All JMPSC Problems and Solutions

The problems on this page are copyrighted by the Junior Mathematicians' Problem Solving Competition. JMPSC.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_JMPSC_Invitationals_Problems/Problem_15&oldid=158184"