Light bulbs and switches There are 40 light bulbs in a room of a big house and 40 switches at a switchboard close to the entrance, far away from the room and without visual contact with it. Each of the switches corresponds to one light bulb. We can only see the status (on, off) of each light bulb by walking to the room. 
We want to find out which switch is connected to each bulb. What is the minimum number of times we will need to walk to the bulbs room? 
I understand that there must be a pattern leaving aside some of the bulbs each time, in a unique way. I assume something having to do with the prime factorisation of 40? 
 A: hint
If there were $2^n$ bulbs you would need $n$ switchings, so you would need 6 switchings because $40>2^5$
You have to prove that whenever you have more than $2^n$ you need more than n swithcings, and here is a method in 6 steps to discover all 40.
Let switches be $S_1,S_2,...,S_{40}$ and $s(ak+b)$ be switching of all the switches with index $i=ak+b$, where $a,k,b\in Z$


*

*$s(2k)$

*$s(4k)$ and $s(4k-1)$

*$s(8k)$ and $s(8k-2)$ and $s(8k-1)$ and $s(8k-3)$

*$s(16k)$ and $s(16k-1)$ and $s(16k-2)$... and $s(16k-7)$

*$s(32k)$ and $s(32k-1)$ and $s(32k-2)$... and $s(32k-15)$

*$s(64k)$ and $s(64k-1)$ and $s(64k-2)$... and $s(32k-31)$


EDIT - this what I wrote stands with preposition that all the bulbs were off at the beginning. If it was not the case than you would need one more walk to the room. So n+1, or in this particular case 7 times visiting the room.
If you haven't prove the statement yet, this problem is like assigning a binary number to each bulb and to each switch. So whenever you touch a switch you adding 1 to the array of its bits, and if you skip a switch you adding zero to it. Same for bulbs when it change state you add 1, and if it remains same you add 0. In the end each switch fits bulb with the same binary number.
So for each switch to have a different number you need at least $n$ digits for each of them.
