Rhona wrote down a list of nine multiples of ten: 10, 20, 30, 40, 50, 60, 70, 80, and 90. She then deleted some of the nine multiples so that the product of the remaining multiples was a perfect square. What is the least number of multiples that she could have deleted?
We can consider the prime factorisation of the product of 10, 20, 30, ... 90.
10×20×30×⋯×90=109×2×3×22×5×2×3×7×23×32=216×34×510×7
We can't leave that 7 there, because everything in the product must be a perfect square. By a greedy approach, we remove 70 first and see what happens.
10×20×30×⋯×9070=215×34×59
But we can't leave 215 and 59 there. Now without affecting the exponent of 3, we remove 10.
10×20×30×⋯×9070×=214×34×58=(27×32×54)2
And there we go, a perfect square, and it only took us 2 removals.
P.S. Notice that 1 removal doesn't work because you have to take away that 7, so you must first remove 70, but that affects the exponent of 2 and 5 so it doesn't work and we have to take an extra move.