Lights out

Number Theory Level 3

There are 100 bulbs in a hall numbered from 1 to 100 with their switches also numbered accordingly.100 students enter the hall one by one and each student operates the switches whose number is a multiple of his order of entering the hall.If all switches were initially off how many will be on after all students have entered?

Example: The student who enters first operates(on) all switches having 1 as a factor. Student no. 2 operates(off) all switches having 2 as a factor.And so on.....

16 10 9 12

1 solution

Brian Charlesworth
Oct 10, 2015

For the $n$ th switch, if $n$ has an even number of positive divisors then that switch will end up being off after all the students have entered the hall, and if $n$ has an odd number of positive divisors then that switch will end up being on. The only positive integers that have an odd number of positive divisors are perfect squares, so since $100 = 10^{2}$ there will be $\boxed{10}$ switches on after all $100$ students enter the hall.

Lights out

1 solution

0 pending reports