2021 JMPSC Invitationals Problems/Problem 15

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} \text{ 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

Page

Toolbox

Search

2021 JMPSC Invitationals Problems/Problem 15

Contents

Problem

Solution

Solution 2

See also