There are 1,000 (one thousand) lamps numbered from 1 to 1,000, which are all turned off.

There are 1,000 (one thousand) people numbered from 1 to 1,000.

The first person goes and turns on all the lamps.
The second goes to the even numbers of lamps (2, 4, 6…) and turns them off.
The third goes to the lamps which are multiples of 3 (3, 6, 9…) and turns on the "off" lamps or turns off the "on" lamps.
The fourth goes to the lamps which are multiples of 4 (4, 8, 12…) and turns on the "off" lamps or turns off the "on" lamps.
This continues up to the 1,000th person.
The 1,000th person goes to the 1,000th lamp, and turns it on if it is "off" or turns it off if it is "on."

How many lamps are "on" after all people finish their jobs?


Solution to the Problem:


31 lamps will remain on.
Construct a table.   The perfect squares 1, 4, 9, 16, 25, ..., 961 will be the lit lamps.

Any lamp that was touched an "even" number of times will be turned off at the end.
Example:
The 24th lamp has been touched by the 1st, 2nd, 3rd, 4th, 6th, 8th, 12th and 24th person, which means the number of touches is 8.   Therefore it will be off.

The 59th lamp has been touched by the 1st and 59th person, which means the number of touches is 2, so it will also be off.

The 501th lamp has been touched by the 1st, 3rd, 167th and 501th person, which means the number of touches is 4.   Therefore it will be off.

A perfect square numbered lamp has been touched an "odd" number of times.
Example: The 4th lamp has been touched by the 1st, 2nd and 4th person, which means the number of touches is 3.   Therefore, it will be on.

The 49th lamp has been touched by the 1st, 7th and 49th person, which means the number of touches is 3.

The 81th lamp has been touched by the 1st, 3rd, 9th, 27th, 81th person, which means the number of touches is 5.

So the answer is the "number of perfect squares" less than 1,000.   We can take the greatest integer of the square root of 1,000 which equals 31.



Correctly solved by:

1. K. Sengupta Calcutta, India
2. Colin (Yowie) Bowey Beechworth, Victoria, Australia
3. Ivy Joseph Pune, Maharashtra, India
4. Eloise A. Michael Greenfield, Massachussetts
5. Dr. Hari Kishan D.N. College,
Meerut, Uttar Pradesh, India
6. Ritwik Chaudhuri Santiniketan, West Bengal, India
7. Eddie G. Muckleshoot Tribal School,
Auburn, Washington
8. Cameron W. Muckleshoot Tribal School,
Auburn, Washington
9. Tabor Muckleshoot Tribal School,
Auburn, Washington
10. Paul Muckleshoot Tribal School,
Auburn, Washington