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?
+9676 We can consider the prime factorisation of the product of 10, 20, 30, ... 90.
\(10 \times 20 \times 30 \times \cdots \times 90 = 10^9 \times 2\times 3\times 2^2 \times 5 \times 2 \times 3 \times 7\times 2^3\times 3^2=2^{16}\times 3^4\times 5^{10}\times 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.
\(\dfrac{10 \times 20 \times 30 \times \cdots \times 90 }{70} = 2^{15} \times 3^4 \times 5^9 \)
But we can't leave 215 and 59 there. Now without affecting the exponent of 3, we remove 10.
\(\dfrac{10 \times 20 \times 30 \times \cdots \times 90 }{70\times } = 2^{14} \times 3^4 \times 5^8 = \left(2^7\times 3^2\times 5^4\right)^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.
