2021 JMPSC Invitationals Problems/Problem 15


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.


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.


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}$.


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