HARD PUZZLE : 100 Switches & 100 Lights Puzzle

This Brilliant Riddle would test your brain power.
There are 100 lights in a huge room. A switch panel outside the room has 100 switches each corresponding to one light in the room.
But none of the switches or lights are labelled, so it's extremely difficult to identify which switch turns on which light.
You are standing outside of the room... and your task is to map each switch to its corresponding light using a marker pen.
You have to do this mapping in minimum number of trips to the room.
Initially, all the switches are turned off.
What's the minimum number of times you need to enter the room to complete the mapping of each switch to its corresponding light.

Please note a few points:
(To check the state of a light, you must enter the room, you cannot check it from outside.)
(There is nothing related to heating of a light... everything here is perfectly logical)
So.
Pause the video..... and think logically.

and here is a hint for you.
(Hint : Surprisingly, the answer is a smaller number)

This video explains this puzzle the best way. You will certainly learn the optimal way and the best approach of solving difficult puzzles.
Of course it's a difficult riddle, but I encourage you to take your own time and try to solve this challenging riddle.
Also try these mind blowing puzzles:
100 Doors Puzzle || Hard puzzle for Genius minds

Which Tank Will Fill Up First? || Solution || VIRAL PUZZLE

Can you solve the Tricky Puzzle || The Clever Commuter || Logical Puzzle

You can follow my facebook page of Logically Yours( Mohammed Ammar ):

[AkshayKumar-fczs]

I cracked campus interview 2 years back using your questions.
Thanks for uploading.

[pedrosil]

This is really incredible. I would probably never think of this binary mapping, but at least I instantly noticed that 7 is the first power of 2 that is higher than 100 (2^7=128)

[KuyashiiPlays]

Depending on how well the bulbs retain heat you can do slightly better. 5 moves. For each step: Turn a third of them on, wait until they heat up, turn them off and them turn another third on. Go inside and quickly test which off lights are still hot. That should give log3(100) or 4.19... moves

[agytjax]

Instead of this dividing and sub-dividing and ensuring that the switches have achieved "unique values", another simpler way to understand the solution :

The no. of trips is CEIL(log2 (100)) = 7

Mark all the switches as 1 thru 100
1. In the first trip, switch ON only those switches that leaves a remainder of zero when divided by 2^1 (2)
On the bulbs, mark as 0, if it does not glow and as 1, if it glows

2. In the 2nd trip, switch ON only those switches that leaves a remainder of zero when divided by 2^2 (4)
On the bulbs, mark as 0, if it does not glow and as 1, if it glows beside the earlier marking from left to right. For e.g 10 or 11 or 01 or 00


3. In the 3rd trip, switch ON only those switches that leaves a remainder of zero when divided by 2^3 (8)
On the bulbs, mark as 0, if it does not glow and as 1, if it glows beside the earlier marking from left to right. For e.g 110 or 111 or 101 or 100

Do this for 7 Iterations. On each of the bulbs, convert the binary numbers that you have written down (like to its decimal equivalent and add plus 1. That would give the corresponding switch number !

[andrewchallen]

Same solution really but start by labelling all the switches 1-100 in binary. Turn them all on according to the first digit of the label. Go in room and write 0 next to the off ones and 1 with light on. Repeat for all 7 digits, and on the final trip write the 100 digits on in decimal. Make a note which ones are on so you can turn them off before you go home.

[rafaelliman]

I thought we would "touch the lights to see if they're still hot"
Y'know, when you just turn the lights on & touch it, it's still cold. Wait for a few moments until it turns hot. Then when you turn it off, it's still hot.
But then I watched your already brilliant solution. After even more thinking, I realize I could COMBINE it with that thought I just wrote. How about that?

To explain it further, there are FOUR states: Hot/On, Hot/Off, Cold/On, Cold/Off. So divide the switches to FOUR groups.
Turn the Hot/On & Hot/Off groups on, and wait for a few moments. Then turn the Hot/Off group off, turn the Cold/On group on, & immediately enter.
Touch the either on/off lights to know if they're hot/cold & label them with values according to the right state. Again, there are FOUR states, so there are FOUR labels/values, for example A (Hot/On), B (Hot/Off), C (Cold/On), D (Cold/Off).
Then for every group that have the same value, divide them to 4 groups again & do the same thing. (Reset all the lights to off firsthand & wait till they're cold for a clean slate.)
Then put the next right label to each of the lights (in perspective, the switches & lights will have values like AA, AB, BB, BD, CA, CD, BA, DC, etc).
Repeat until all lights have unique values (like you said).

So the system used isn't binary, but QUATERNARY.
This way, ONLY FOUR TRIPS are required (because 4^3=64<100, but 4^4=256>100).

[spencerkeene]

This would probably be the fastest method but assuming we aren’t looking for speed and purely are looking for fewest trips you could solve this in less than 7 trips. Assuming the lights also produce heat, you can turn 1/3 on to let them heat up then turn them off and turn a different 1/3 on before you walk in. Then instead of splitting the lights up into 2 groups (on/off) you split them into 3 groups (on/off and cool/off and hot). This allows you to map them all in 5 moves. Assuming you can check all the lights temperature fairly quickly, you can additionally break them down into 4 groups by turning on 1/2 the lights to let them warm up then then turn off 1/2 of those lights and turn on 1/2 of the lights already off before you walk in. This splits the lights into 4 groups (on and cool or slightly warm/on and hot/off and hot/off and cool). This allows you to map all the lights in only 4 trips.

[chapmanchapman]

We can use 3 state to reduce the trip.
Turn on the light a while and off it.
Then we have:
1. the light is on;
2.the light is off with heat;
3.the light is off but cold.

3^5 > 100. Therefore, only 5 trip.

[manojmathai]

Really love your videos. Would really appreciate if you increase the frequency of your videos to at least once a week. Great content. Keep up the good work. Regards

[prasaddamale]

I started with minimum number of switches, like from 1 and tried counting the minimum number of trips upto 10 switches. After analysing the pattern as if you have 1 or 2 switches you require minimum 1 trip, if you have 3 to 4 switches you require 2 trips, if you have 5 to 8 switches, you require minimum 3 trips and then I just tried once for 10 switches and I was sure about the minimum number of trips should come equal to 4. So, by finding minimum number of trips for 1 to 10 switches, I predicted the formula and got the answer.

I liked your explanation a lot. Thank you for giving so much of food for thought. All the best😀 keep posting such good puzzles. Thanx a lot.😀

[orrbezalely]

Its really nice to see how after seeing many problems of this type you start to answer them instinctively. For example this question I instantly thought about binary and that 100 different numbers can be represented with 7 bits in binary. Thanks a lot for the questions!

[cricketcoachingforchildren]

Explanation is superb. I came across this some time back.
Very interesting puzzle. Please
Upload the chess puzzle as soon as possible.

[wyattstevens]

Here's an outside-the-box solution for n=3: First, flip one switch. After maybe 5 minutes (at least long enough to let the bulb heat up) switch it off and another on. Now go in: there's one that's on (our switch 2) and between the two others, feel one. If it's still warm, it's switch 1, and otherwise switch 3.

[adrianshum]

Could do it in 5 trips: just combine with another famous puzzle of 3 switch 3 bulb : each trip you can distinguish 3 states: on, off-but-warm, and off. 5 trips could give you 243 distinct values.

[anubhavajmera]

The moment you say 7 trips, I got that how you get the answer

[disguisedhell]

I knew that it was 7 as 2^6 is largest power of 2 less than 100 and therefore we would need at least 7 bits including 2^0. The involvement of binary can be known instantly as each switch can be on or off indicating assigning 0 or 1.

[suman-majhi]

This is a log(N) base 2 solution😂😂... love it ❤️❤️

[nobody]

For 2 switch = 1 trip
For 10 switch = 4 trip
For 100 switch = 7 trip
For 1000 switch = 10 trip
It's so simple => (2^x = number of switch) => x=ln(no of switch)÷ln 2
This video was so helpful, thank you

[argsahoo]

What if we do it like this:
minimum no. of trips = ceil(log(n)) [where, n is the total number of switches]

If we take the ceiling value of log(n) it should give us the ans. I took a few test examples and it worked. With this the time complexity will reduce to O(1).

Please correct me if I am wrong.

[danik]

On 1:45, i figured out, that for n bulbs / switches, you can do it in binary log of n checks (rounded up).