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