A prison has 1000 cells. Initially, all cells are marked with - signs. From days 1 thru 1000, the jailor toggles marks on some of the cells: from + to - and from - to +. On the i-th day, the signs on cells that are multiples of i get toggled. On the 1001-th day, all cells marked with + signs are opened. Which cells are these?

I remember hearing this puzzle sometimes in 1987, when I was in grade 9, from Samir Khosla. And I remember solving it in the football field in school.

A cell is toggled as many times as the number of divisors it has. For example, cell number 24 is toggled on days 1, 2, 3, 4, 6, 8, 12 and 24. Now, divisors come in pairs like 24 = 1*24 = 2*12 = 3*8 = 4*6. So the total number of divisors is even, except when the number is a perfect square, in which case the total number of divisors is odd. Since all cells are initially marked with - signs, only those cells that have an odd number of divisors have + signs eventually. These are cell numbers 1, 4, 9, 16, 25, 36, and so on.