Difference between revisions of "2021 JMPSC Invitationals Problems/Problem 15"
(Created page with "==Problem== Abhishek is choosing positive integer factors of <math>2021 \times 2^{2021}</math> with replacement. After a minute passes, he chooses a random factor and writes i...") |
(→Solution) |
||
| (5 intermediate revisions by 5 users not shown) | |||
| 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}</math>th turn. | |
| + | |||
| + | ~Geometry285 | ||
| + | |||
| + | ==Solution 2== | ||
| + | It factors as <math>43 \cdot 47 \cdot 2^{2021}</math>, and say that the form of the product of the numbers is <math>43^a \cdot 47^b \cdot 2^c</math>. With equal probability, <math>a</math> is even and <math>a</math> is odd at every step since at the first step, <math>a=0</math> appears with <math>\frac{1}{2}</math> probability and <math>a=1</math> appears with <math>\frac{1}{2}</math> probability. The same applies to 47, or <math>b</math>. The same goes for <math>c</math>. Because the numbers of <math>c</math> range from 0 to 2021 each time, then obviously half of those numbers are odd and half are even. The probability of each <math>a,b,c</math> being even (which is the requirement for being a perfect square) is <math>\frac{1}{2}</math>, so the answer should be <math>\left(\frac{1}{\frac{1}{2}}\right)^3= \boxed{8}</math>. | ||
| + | |||
| + | ~lamphead | ||
| + | |||
| + | ==See also== | ||
| + | #[[2021 JMPSC Invitationals Problems|Other 2021 JMPSC Invitationals Problems]] | ||
| + | #[[2021 JMPSC Invitationals Answer Key|2021 JMPSC Invitationals Answer Key]] | ||
| + | #[[JMPSC Problems and Solutions|All JMPSC Problems and Solutions]] | ||
| + | {{JMPSC Notice}} | ||
Latest revision as of 23:02, 11 July 2021
Contents
Problem
Abhishek is choosing positive integer factors of 
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 
, so we want to "select" for the numbers that are not factors of 
. This is 
of them. In addition, for the factors of 
, exactly 
of them are perfect squares, and for each turn, there is a 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 
probability Abhishek will end, which means he is expected to end on his 
th turn.
~Geometry285
Solution 2
It factors as 
, and say that the form of the product of the numbers is 
. With equal probability, 
is even and is odd at every step since at the first step, 
appears with probability and 
appears with probability. The same applies to 47, or 
. The same goes for 
. Because the numbers of range from 0 to 2021 each time, then obviously half of those numbers are odd and half are even. The probability of each 
being even (which is the requirement for being a perfect square) is , so the answer should be 
.
~lamphead
See also
- Other 2021 JMPSC Invitationals Problems
- 2021 JMPSC Invitationals Answer Key
- All JMPSC Problems and Solutions
The problems on this page are copyrighted by the Junior Mathematicians' Problem Solving Competition. 
