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)
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
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 0000011) to its decimal equivalent and add plus 1. That would give the corresponding switch number !
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.
It occurred to me that I wouldn't need to take a note of the numbers to turn them off, it's just the ones that are "on". Also if done as described there the last round would be all the even numbers. But... What if the switches were not labelled on/off, and some of the lights are already on? I have an upper limit for the number of times I'd have to enter the room but I'm not sure if there's a way to get the number down?
I'm surprised that you wouldn't label them 0 to 99 . More generally you can label the switches with any numbers between 0 and 127 as long as each label is unique. You can skip numbers or put them in any order.
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=64100).
Hi Rafi.... I truly appreciate that you performed this calculation combining the two logics. It was so clean and easy to understand..... Kudos !! Since I had already uploaded a video based on heating concept... I too thought of combining the two logics. However, for this video, I thought of keeping it an individual logic, so I mentioned right in the beginning that 'there is nothing related to heating of a light'. But now after reading your explanation... I must prepare a dedicated video where we can have just 32 BULBS (to make it more easy to understand for the viewers) and combine the two logics.
@@LOGICALLYYOURS oh yeah....... i checked the video again....... yeah you clearly said "nothing related to heating of a light"........ i didn't pay attention at first 'cos earlier it sounded a bit incomprehensible......... so i didn't know, then i immediately thought, "is this related to that puzzle where you touch the lights?", without realizing that you said it doesn't count. Oh well, guess my answer is if it does. Still it's a brilliant puzzle.
@@LOGICALLYYOURS I thought of your approach, (like that puzzle with 3 lights). But the (temperature) variable, leaves to much room for me to err. I can't tell what is hot or not. For most people Your (log base (4) works well). As I got older I lost my sense of warm, cold, hungry, not hungry, or even tired. The (warm, not warm) would leave (way) to much room for error. For my shitty perception. BUT, technically your 4^4=256 would work better.
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.😀
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
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!
You are absolutely right. When we see that we have to store a greater amount of information in a smaller space, BINARY is the fist keyword that comes to mind.
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.
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.
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.
At the beginning he says, “There is nothing related to HITTING of a light.” Perhaps what he said was “heating”. If we assume that, no, he meant something else, you could break the switches into three groups instead of two; one group we turn off, the second we turn on for a few minutes and then turn off, the third we turn on. Then we enter the room, we can distinguish the second group from the first by checking which is still warm from being turned on. In this fashion, we can categorize all 100 lights in 5 steps instead of 7.
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
It's easy if you can find a trick. There are 2 conditions. On and off. [Let n = 100.] If we write (100-1) = 99 in 2 digit number system we get 1100011 which is a 7 digit number. So every switch of the board can be labeled with different numbers using 7 digit numbers of binary (if n had been a power of 2 then we would assign n equal to 0). Now first we assign numbers to the switch. Then every time before we go to check, we turn all the lights on which has 1st digit 1. Then we go to check. We write 1 under the switched on lights and 0 under the off. We continue this process for 7 times. Viola! We have marked all the switches and bulbs with the same marking in binary. In short we use log 100 base 2 and we round the number to the next one if there is decimal. Log 100 base 2 is 6.64 so we make it 7. If there were a third condition possible (like on or off) then the answer would be log 100 base 3 rounded up to the next number.
There can be a third condition. You can turn on X lights for a while, and then turn them OFF and turn on X lights. You will have, in this concrete case, 33 lights on, 34 lights off, and 33 hot bulbs. You can do it in 5 trips at the end.
Thanks a lot bro :) I am now working hard to upload frequently. By the way, a very fresh, very easy yet a trickiest riddle is on its way. Will be published on Sunday.
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.
I'm still working through the combinations mentally but I should be able to map all 100 lights with 6 trips instead of 7 by remembering the solution for 3 lights. The system doesn't have to be entirely binary cause there's a third option if you work quick. By turning the light on for a while then turning it back off when you enter the room you'll have two lights off and one light on, but of the two off, one will be warm. So if you introduce a "off but warm" notation to every test you can test 243 lights in 5 trips provided you're willing to wait for all bulbs to cool down to starting temp (you did say minimal entries not minimal time) But assuming you're not willing to do that I have an optimal solution, if you run the "warm" test only on the first switching then stop, because an "on" in any previous test means it'll always test warm, then do only on/off from there, you can test 96 in 6 trips. But this method leaves 5 switches that never get flipped, the one code: 000000 and the four not assigned combinations so if instead we take one of the four unassigned switches and flip them for a warm test on bits 2-6 when we enter the room and check only the bulbs labeled with only 0's and find the one that's warm, we will have uniquely identified which unassigned switch goes to which bulb, we can find the remaining 4, actually 5 that way bringing our total to 101 in 6 trips I know you can get a lot more optimal with the number of lightbulbs than this and I challenge the logic master to find out just how many... you can incorporate a w/2 combination into your 6 bit system only if that 2 is the first non-zero bit. How many combinations are possible? Can we get it down to 5 entries?
update: after waking up and getting coffee, i've mapped 63 lights onto 5 room entries (up from the previous method of 50) with the notation that you can only track "off but warm" on the lights that had previously never been turned on. so if we have to enter the room a 6th time i'm up to 127 mapping combinations, looks like with this method of using warm check, the number of lightbulbs you can check will always be 1 fewer light bulb than if you were allowed one extra entry to the room 2^(n+1)-1 instead of 2^n. so while the puzzle solution maps 128 light bulbs entering the room 7 times, this one maps 255 lightbulbs with the same 7 entries
There is something that you can use to minimize the number of required step less than 7 by considering the fact the light is energy and will make the temperature of lamp increased by the way you can simply feel it using your hand. For example, if I have 3 lamps on off mode: I will switch one on, the second one switch on for a small period of time, then switches off again, while the last one I will keep it on off mode. Then by entering the room,, I will see one is on and two are off, but by touching both of the two off lamps off I will feel one is more hotter, so I can distinguish three lamps by one move. Merging this with the idea of binary number that you used should minimize the number of movements. Regards, Ala Zayed
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.
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.
You're all too smart for me lol 😊 I'd be way too paranoid that some of those lights weren't working even when switched on, that my logic was flawed, or that I'd made a mistake somewhere. I'd definitely be asking a pal to stand in the room with a mobile phone telling me which light changed instead haha. I get the feeling half my life is doing things 'the long way' 😁
My initial thought was to set up a recursive function similar to merge sort, just didn't understand how. Marking their state which gives them a unique identifier is great. In code this would be a strong, and on every trip you += the string with the binary value. Then just check the string values to return on base case
two trips: I will take one video turning on all switches and I will take another video in the room while turning lights on outside the room and then go into the room with that video. You get the point...
Good one👍 ammar.. I am able to solve this in almost same method but labeled it differently, Instead of using binary I used alphabets and numericals alternatively... For first trip I used A and B, second trip it will be A1, A2, B1 &B2.. for third trip A1x, A1y, A2x, A2y like that, for fourth A1x1, A1x2... like that.
Hello, nice try. But you can reduce the steps eventuaally? What if… what if you do add another check? Instead of just switching on/off you also could turn 1/3 on for a minute, so some lamps will heat on. Then switch off 1/3 enter the room and check the warm lamps! If some lamps are still warm, you know that those are part of the group 3. How much steps are now required? Give it a try and maybe another video solution. :-) Yoirs…Bernhard
mapping is fine but how could you identify which switch belong to which light by jst entering room and not checking its switch...i dont get it....could you pls explain for my better understanding
You can try this way. If you know Binary search then it will be clear. Have you ever played this game where computer will guess your selected/wished number by simply asking 2 or 3 times like below : " hey, does your seleced number present in these numbers? " You can check answers for these things then it will help you in solving these kind of questions.
What if I tell you you can do it 5 rounds? Simple lighted bulbs become hot when lighted for abperiod of time. After switching off just check which one is hot. Rather than two categories we will have 3.
Can you not use the fact that, if you let one switch ON for some time it heats up, then close it? Now instead of two states (0 and 1), you have 3 states (Light on, Light off and cold, Light off and hot). So answer could be ceil(log(100)/log(3)) = 5??
I solved but in a harder way to memorise if i am realy doing this puzzle but same methode . I laybel all button from 1 to 100 first i turn on 50 and i label on lights 1 to 50 turn on and 51 to 100 turn next 1to25 and so on but when i have see 1 to 25 light turn on i have change the lable which is turn on of 25 lights on and so on but im not allowd to change beacause i have only pen your methode is 100% correct with the rule thanx to this amazing puzzle sorry about my english im an arabic boy
That is true. There is another logic puzzle, where you turn on one switch for some time and then turn it off and then go into the room to check which light is warm. 3^5 is 243, therefore entering the room 5 times should be enough. Before entering the first time you turn on 1:67 for a few minutes and then turn off 34:67 and then enter the room. Each light gets a 0 (on) a 1 (off warm) or a 2 (off cold). Next time you turn on 1:20 and 34:54 and 67:87 and then after 5 min you turn of 11:20 and 44:54 and 77:87. You enter the room and give each light the second ternary digit: 0 (on) a 1 (off warm) or a 2 (off cold). etc.
It depends on assumption that bulbs are warm long enough to check 100 of them. if you make assumption that also warming up takes enough time to check 100 - then you can add another state (on warm) and makem it 4^4. :)
Just do it all in 2 runs - turn all of them on and then one by one turn them off. The hottest is the last and otherwise (the coldest = first). Second run just to make sure.
what if we consider the heat generated by the lights into this problem, then we can have on state, off state, and off state with heat. that would make it 5 trips to the room.
you're thinking the bulb has 2 states on and off so the lowest trips is log 100 base 2 , which is over 6.64 so 7 trips, but bulbs heat up too! so if u count a heating state, this can be done in log 100 base 3 so in just 5 trips.
A brilliant riddle, and AS USUAL with Amar, the explanation is also brilliant. just wonderful! It is so surprising to find you need only 7 steps to solve the problem. Reminds me of a riddle based on similar logic: I choose a number from 1 to 100 and keep it in my heart. You have to guess what number I chose. You are only allowed to ask as: Is the number greater than 50? Is the number greater than 70? Or for example, is the number is smaller than 40? etc. etc'... For each question of you, I can only answer to you: "YES" or "NO". What do you think, how many gueses you need to find the number I chose? ANSWER: I can only tell that the answer is: It is enough to you to ask me ... only 7 questions !! I leave it to Amar to explain why. (-: No one do it better then him. Edited: And one more small and personal question: Amar !!! Where have you been and where have you disappeared ??? I already thought maybe aliens kidnapped you from Earth, and now you've amazing all kinds of green creatures somewhere in the Andromeda Galaxy ... Welcome back to Earth !!
Hi Tamir :) my friend i was waiting for this :) :) Extremely sorry for the delay... now I'll compensate it by posting back to back puzzles! I read your problem.. and i will give my best to SURPRISE you with a unique approach.. very soon :)
Interesting puzzle but very stupid from other point of view - because it requires to check state of the lights 7 times (for all of them - for 100 hundred lights!). And if to do it straight forward - you'll have to check state of the lights just once. Of course you'll have to do 100 hundred trips to the room but still it will be much faster. And real solution to this puzzle it to have one person near the switches and second person in the room with phone.
1 line answer : consider as binary , the number 64 has 6 digits binary while 128 has 7 , since 100 is between 64 and 128 , and more than 64 , 7 trips is the answer
Here is another variant: A landline company has laid down 500 pairs (1000 copper wires), alas they forgot to label them so they can't connect their clients. All you have is a line tester (an instrument that can tell you if a copper cable is broken). Find a way to label each cable uniquely at the two locations while minimizing the number of trips. What is the minimal number of trips ? Hint: It's way smaller than one may think!
I did this in a few seconds: import math print(math.ceil(math.log2(100))) # > 7 That's because I was already in front of my PC. You could also think 2^6 = 64 < 100 < 2^7 = 128 therefore 7.
Mostly, the light bulbs and switch board panel are always aligned...so if the panel is arranged as a 25x4 matrix and the light bulbs are arranged in the same way, then by just switching on the first switch, we can see whether the first bulb or the last bulb is glowing and so, get to know the switches for each bulb....for people thinking, bulbs and switches won't be arranged...just a hint, electricians are not dumb and the question didn't say that I can't assume ✌️
Shubham... in fact when a puzzle has switches and lights, our first instinct would be the heating concept. So i put the condition in the start that it's not a heating based puzzle.
How about using triary number : 1. Divide the switches into 3 groups (let say group 0, 1, and 2) 2. Switch on the group 2 3. After some time, switch on the group 1 4. F*CKIN QUICKLY go the the room 5. Now each of the lights has one off these states : off (group 0), only on (group 1), and on+warm (group 2). Mark each light based on its state you will need less trip.. only 5 trips to map the 100 lights
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)
mee too
haha same here. I instantly paused the video and figured out the rest
sure you did
same here
I cracked campus interview 2 years back using your questions.
Thanks for uploading.
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
Was about to post a similar base 3 approach
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 0000011) to its decimal equivalent and add plus 1. That would give the corresponding switch number !
First move- fire the electrician.
😀
Epic one 😂😂
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.
Yup! Perfect.
I have put a slide of this approach at 6:01
It occurred to me that I wouldn't need to take a note of the numbers to turn them off, it's just the ones that are "on". Also if done as described there the last round would be all the even numbers. But... What if the switches were not labelled on/off, and some of the lights are already on? I have an upper limit for the number of times I'd have to enter the room but I'm not sure if there's a way to get the number down?
I'm surprised that you wouldn't label them 0 to 99 . More generally you can label the switches with any numbers between 0 and 127 as long as each label is unique. You can skip numbers or put them in any order.
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=64100).
Hi Rafi.... I truly appreciate that you performed this calculation combining the two logics. It was so clean and easy to understand..... Kudos !!
Since I had already uploaded a video based on heating concept... I too thought of combining the two logics. However, for this video, I thought of keeping it an individual logic, so I mentioned right in the beginning that 'there is nothing related to heating of a light'.
But now after reading your explanation... I must prepare a dedicated video where we can have just 32 BULBS (to make it more easy to understand for the viewers) and combine the two logics.
@@LOGICALLYYOURS oh yeah....... i checked the video again....... yeah you clearly said "nothing related to heating of a light"........ i didn't pay attention at first 'cos earlier it sounded a bit incomprehensible......... so i didn't know, then i immediately thought, "is this related to that puzzle where you touch the lights?", without realizing that you said it doesn't count.
Oh well, guess my answer is if it does. Still it's a brilliant puzzle.
@@LOGICALLYYOURS I thought of your approach, (like that puzzle with 3 lights). But the (temperature) variable, leaves to much room for me to err. I can't tell what is hot or not. For most people Your (log base (4) works well). As I got older I lost my sense of warm, cold, hungry, not hungry, or even tired. The (warm, not warm) would leave (way) to much room for error. For my shitty perception. BUT, technically your 4^4=256 would work better.
If we allowed this I can also say that I have I thermometer which calculates the temperatures very precisely then I can find it in one step
@@vangildermichael1767 I have a feeling you're actually trying to reply to ME?
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.😀
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
Many thanks Manoj, and trust me I am really sorry for the delay... but you won't have any delays from now on :)
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!
You are absolutely right. When we see that we have to store a greater amount of information in a smaller space, BINARY is the fist keyword that comes to mind.
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.
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.
0:49 just listen
Explanation is superb. I came across this some time back.
Very interesting puzzle. Please
Upload the chess puzzle as soon as possible.
Thank you sir... I will certainly work on the chess miniature.
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.
Yes then you need to by a stair and have to touch all the light before they would get cool.
Puzzle already stated in begining that it has nothing to do with heating of light
At the beginning he says, “There is nothing related to HITTING of a light.” Perhaps what he said was “heating”. If we assume that, no, he meant something else, you could break the switches into three groups instead of two; one group we turn off, the second we turn on for a few minutes and then turn off, the third we turn on. Then we enter the room, we can distinguish the second group from the first by checking which is still warm from being turned on. In this fashion, we can categorize all 100 lights in 5 steps instead of 7.
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
It's easy if you can find a trick.
There are 2 conditions. On and off.
[Let n = 100.]
If we write (100-1) = 99 in 2 digit number system we get 1100011 which is a 7 digit number. So every switch of the board can be labeled with different numbers using 7 digit numbers of binary (if n had been a power of 2 then we would assign n equal to 0).
Now first we assign numbers to the switch. Then every time before we go to check, we turn all the lights on which has 1st digit 1. Then we go to check. We write 1 under the switched on lights and 0 under the off. We continue this process for 7 times.
Viola! We have marked all the switches and bulbs with the same marking in binary.
In short we use log 100 base 2 and we round the number to the next one if there is decimal. Log 100 base 2 is 6.64 so we make it 7.
If there were a third condition possible (like on or off) then the answer would be log 100 base 3 rounded up to the next number.
There can be a third condition. You can turn on X lights for a while, and then turn them OFF and turn on X lights. You will have, in this concrete case, 33 lights on, 34 lights off, and 33 hot bulbs. You can do it in 5 trips at the end.
This is a log(N) base 2 solution😂😂... love it ❤️❤️
I love your videos, and I was waiting for the new videos for so long. I hope you can make it faster.Keep up the great work, sir.
Thanks a lot bro :) I am now working hard to upload frequently. By the way, a very fresh, very easy yet a trickiest riddle is on its way. Will be published on Sunday.
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.
That is right. Just make sure its base 2 not 10 xD.
@@orrbezalely3332 yupp
Yup!! that looks good... As Orr mentioned, it base 2 :)
I have mentioned it in terms of powers of 2 at 6:01 .
But time complexity will be O(logn)
@@vikassinghpatel989 Yeah as O(log n)=O(log2 n). They only differ by a constant
I'm still working through the combinations mentally but I should be able to map all 100 lights with 6 trips instead of 7 by remembering the solution for 3 lights. The system doesn't have to be entirely binary cause there's a third option if you work quick. By turning the light on for a while then turning it back off when you enter the room you'll have two lights off and one light on, but of the two off, one will be warm. So if you introduce a "off but warm" notation to every test you can test 243 lights in 5 trips provided you're willing to wait for all bulbs to cool down to starting temp (you did say minimal entries not minimal time)
But assuming you're not willing to do that I have an optimal solution, if you run the "warm" test only on the first switching then stop, because an "on" in any previous test means it'll always test warm, then do only on/off from there, you can test 96 in 6 trips.
But this method leaves 5 switches that never get flipped, the one code: 000000 and the four not assigned combinations so if instead we take one of the four unassigned switches and flip them for a warm test on bits 2-6 when we enter the room and check only the bulbs labeled with only 0's and find the one that's warm, we will have uniquely identified which unassigned switch goes to which bulb, we can find the remaining 4, actually 5 that way bringing our total to 101 in 6 trips
I know you can get a lot more optimal with the number of lightbulbs than this and I challenge the logic master to find out just how many... you can incorporate a w/2 combination into your 6 bit system only if that 2 is the first non-zero bit. How many combinations are possible? Can we get it down to 5 entries?
update: after waking up and getting coffee, i've mapped 63 lights onto 5 room entries (up from the previous method of 50) with the notation that you can only track "off but warm" on the lights that had previously never been turned on. so if we have to enter the room a 6th time i'm up to 127 mapping combinations, looks like with this method of using warm check, the number of lightbulbs you can check will always be 1 fewer light bulb than if you were allowed one extra entry to the room 2^(n+1)-1 instead of 2^n. so while the puzzle solution maps 128 light bulbs entering the room 7 times, this one maps 255 lightbulbs with the same 7 entries
There is something that you can use to minimize the number of required step less than 7 by considering the fact the light is energy and will make the temperature of lamp increased by the way you can simply feel it using your hand. For example, if I have 3 lamps on off mode: I will switch one on, the second one switch on for a small period of time, then switches off again, while the last one I will keep it on off mode. Then by entering the room,, I will see one is on and two are off, but by touching both of the two off lamps off I will feel one is more hotter, so I can distinguish three lamps by one move. Merging this with the idea of binary number that you used should minimize the number of movements.
Regards,
Ala Zayed
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.
Perfect!
Surprisingly, I saw the answer. Might have something to do with the fact I wrote Assembly code for years and like the binary chop!
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.
He clearly mentioned that u cannot tell if a bulb is hot or not. So 5 is wrong answer
How did u editing like this...which software r u using for this
The moment you say 7 trips ,I got that how you get the answer
Me too, bro 😅
You're all too smart for me lol 😊 I'd be way too paranoid that some of those lights weren't working even when switched on, that my logic was flawed, or that I'd made a mistake somewhere. I'd definitely be asking a pal to stand in the room with a mobile phone telling me which light changed instead haha. I get the feeling half my life is doing things 'the long way' 😁
haha... i was hoping to get a straight forward approach from you :)
@@LOGICALLYYOURS I guess the real puzzle is how did I even pass maths? I'm certainly capable of problem solving...but rarely within the given rules! 😄
My initial thought was to set up a recursive function similar to merge sort, just didn't understand how. Marking their state which gives them a unique identifier is great. In code this would be a strong, and on every trip you += the string with the binary value. Then just check the string values to return on base case
Nice puzzle! I feel the 12 men on island puzzle (google interview puzzle) is much harder.
two trips: I will take one video turning on all switches and I will take another video in the room while turning lights on outside the room and then go into the room with that video. You get the point...
Almost always have someone working with you that you can just phone while they are in one room and you another.
@@PokerGuts Yeah. Single trip
The first thing that came to my mind was using 20 trips. Divide into rows and columns. You’d get a 2D coordinate system.
I too used the same logic, but 18 as after 9 trips in both row and column traversal what's left must be the 10th.
Ur explations are very good and exlent
And one more thing please mention which math theroy your using which help us
Thankyou..
Good one👍 ammar..
I am able to solve this in almost same method but labeled it differently, Instead of using binary I used alphabets and numericals alternatively... For first trip I used A and B, second trip it will be A1, A2, B1 &B2.. for third trip A1x, A1y, A2x, A2y like that, for fourth A1x1, A1x2... like that.
Yup... you got it right!!
Hello, nice try. But you can reduce the steps eventuaally? What if… what if you do add another check? Instead of just switching on/off you also could turn 1/3 on for a minute, so some lamps will heat on. Then switch off 1/3 enter the room and check the warm lamps! If some lamps are still warm, you know that those are part of the group 3. How much steps are now required? Give it a try and maybe another video solution. :-) Yoirs…Bernhard
mapping is fine but how could you identify which switch belong to which light by jst entering room and not checking its switch...i dont get it....could you pls explain for my better understanding
You can try this way. If you know Binary search then it will be clear.
Have you ever played this game where computer will guess your selected/wished number by simply asking 2 or 3 times like below : " hey, does your seleced number present in these numbers? "
You can check answers for these things then it will help you in solving these kind of questions.
Fantastic puzzle and superb explanation.
Love all your videos.They are all excellent but this one blew my mind
But you said there was a much faster algorithm? Could you link that as a video too?
On seeing the hint, I was able to solve the puzzle in two min. Thanks for this great puzzle❤️
We can also mention all the bulbs with numbers on glass and when we switch on it will gives light with that we can mention the switches na .....
You can do it by 5 visits, simply by creating 3 groups: on, off and off but warm bulb => 3^5 more than enough
How can you find thats type of interesting puzzles??
nice soln , I didn't solve any yet but I enjoy your riddles, keep the good work
By playing with the temperature you can do it even with 4 trips! Even if was 256 lighting.
Open cold open hot close cold close hot
By your method you should be able to distinguish A maximum of 2^7=128 lights. By mine 5 walkins are enough as 3^5 (which is 243 ) is larger than 100.
It's just amazing 💥💥
What if I tell you you can do it 5 rounds? Simple lighted bulbs become hot when lighted for abperiod of time. After switching off just check which one is hot. Rather than two categories we will have 3.
Is there any method by P and C?
Can you not use the fact that, if you let one switch ON for some time it heats up, then close it? Now instead of two states (0 and 1), you have 3 states (Light on, Light off and cold, Light off and hot).
So answer could be ceil(log(100)/log(3)) = 5??
Cheak the switch trip number of ""Switch 96 and Switch 97""
Haha
dont worry... its editing mistake... but he is right
@@suman-majhi i know it and i made this comment to re edit his mistake
I solved but in a harder way to memorise if i am realy doing this puzzle but same methode . I laybel all button from 1 to 100 first i turn on 50 and i label on lights 1 to 50 turn on and 51 to 100 turn next 1to25 and so on but when i have see 1 to 25 light turn on i have change the lable which is turn on of 25 lights on and so on but im not allowd to change beacause i have only pen your methode is 100% correct with the rule thanx to this amazing puzzle sorry about my english im an arabic boy
Thanks Tony....
And yes, you can do it the way you explained.
Marvelous trick bro. Love It. A lot of thanks
"You cant use the heating of the light". Someone used base 3, huh
That is true. There is another logic puzzle, where you turn on one switch for some time and then turn it off and then go into the room to check which light is warm. 3^5 is 243, therefore entering the room 5 times should be enough. Before entering the first time you turn on 1:67 for a few minutes and then turn off 34:67 and then enter the room. Each light gets a 0 (on) a 1 (off warm) or a 2 (off cold). Next time you turn on 1:20 and 34:54 and 67:87 and then after 5 min you turn of 11:20 and 44:54 and 77:87. You enter the room and give each light the second ternary digit: 0 (on) a 1 (off warm) or a 2 (off cold). etc.
It depends on assumption that bulbs are warm long enough to check 100 of them.
if you make assumption that also warming up takes enough time to check 100 - then you can add another state (on warm) and makem it 4^4. :)
Just do it all in 2 runs - turn all of them on and then one by one turn them off.
The hottest is the last and otherwise (the coldest = first).
Second run just to make sure.
what if we consider the heat generated by the lights into this problem, then we can have on state, off state, and off state with heat. that would make it 5 trips to the room.
you're thinking the bulb has 2 states on and off so the lowest trips is log 100 base 2 , which is over 6.64 so 7 trips, but bulbs heat up too! so if u count a heating state, this can be done in log 100 base 3 so in just 5 trips.
The minimum number of times is 5. If as a strategy you divide the lights in (hot /on, hot off, cold on, cold off).
i'd still prefer entering the room 100 times since it would take more time to keep track for 100 lights
This was one of the hardest puzzles on your channel according to me.
A brilliant riddle, and AS USUAL with Amar, the explanation is also brilliant. just wonderful! It is so surprising to find you need only 7 steps to solve the problem.
Reminds me of a riddle based on similar logic: I choose a number from 1 to 100 and keep it in my heart. You have to guess what number I chose. You are only allowed to ask as: Is the number greater than 50? Is the number greater than 70? Or for example, is the number is smaller than 40? etc. etc'...
For each question of you, I can only answer to you: "YES" or "NO". What do you think, how many gueses you need to find the number I chose?
ANSWER: I can only tell that the answer is: It is enough to you to ask me ... only 7 questions !!
I leave it to Amar to explain why. (-: No one do it better then him.
Edited:
And one more small and personal question:
Amar !!!
Where have you been and where have you disappeared ???
I already thought maybe aliens kidnapped you from Earth, and now you've amazing all kinds of green creatures somewhere in the Andromeda Galaxy ...
Welcome back to Earth !!
Yes, your riddle uses the same concept. A beautiful & amazing concept called the binary system.
Hi Tamir :) my friend i was waiting for this :) :)
Extremely sorry for the delay... now I'll compensate it by posting back to back puzzles!
I read your problem.. and i will give my best to SURPRISE you with a unique approach.. very soon :)
Simply use Binary Search technique by supposing On =1 and Off = 0
Brilliant 🤩
Easy stuff.
2 times, once to install a live cam system, twice to deinstall it
I started from the other end with the odd switches 1 3 5 7 9 with a 1 in the least significant bit
For any n number of switches , cheak for a minimum number k for which 2^k is greater than n .then k will the number of minimum trips
Very nice puzzle 👍👍
So it’s the number of times you can divide it by 2 until you get to 1 , but when it’s an odd number you add 1 before you divide it by 2
being a programmer first thing that came to my mind was binary search
On 1:45, i figured out, that for n bulbs / switches, you can do it in binary log of n checks (rounded up).
I love this, binary numbers are so powerful!
Loved this approach
It's a amazing puzzle. Initially I thought it might take more number of trips. Later I solved with more brain efforts. Thanks for the brain challenge.
Fantastic solution
I solved the problem using exactly the same method (first for 10 switches and then 100 : respectively 4 and 7 trips).
Interesting puzzle but very stupid from other point of view - because it requires to check state of the lights 7 times (for all of them - for 100 hundred lights!).
And if to do it straight forward - you'll have to check state of the lights just once. Of course you'll have to do 100 hundred trips to the room but still it will be much faster.
And real solution to this puzzle it to have one person near the switches and second person in the room with phone.
What a neat puzzle.
Excellent explanation.
🇧🇷
1 line answer : consider as binary , the number 64 has 6 digits binary while 128 has 7 , since 100 is between 64 and 128 , and more than 64 , 7 trips is the answer
Amazing solution 👍
Superb logic👌👌
Here is another variant:
A landline company has laid down 500 pairs (1000 copper wires), alas they forgot to label them so they can't connect their clients.
All you have is a line tester (an instrument that can tell you if a copper cable is broken).
Find a way to label each cable uniquely at the two locations while minimizing the number of trips. What is the minimal number of trips ?
Hint: It's way smaller than one may think!
2 power 7 is 128
Upto 128 switches we can map within 7 trips 😁
This method is derived from quick sort algorithm
0:43 can I turn on switches from inside the room.
lol
Another great puzzle from amar , keep up the amazing work ❤️❤️🔥🔥
This problem is similar to find the poisoned bottle problem with limited testing.
That problem and this problem both require binary solutions.
You're right. They are similar.
@@LOGICALLYYOURS Keep up the great work
I did this in a few seconds:
import math
print(math.ceil(math.log2(100)))
# > 7
That's because I was already in front of my PC. You could also think 2^6 = 64 < 100 < 2^7 = 128 therefore 7.
Quite interesting. Thanks for sharing.
Mostly, the light bulbs and switch board panel are always aligned...so if the panel is arranged as a 25x4 matrix and the light bulbs are arranged in the same way, then by just switching on the first switch, we can see whether the first bulb or the last bulb is glowing and so, get to know the switches for each bulb....for people thinking, bulbs and switches won't be arranged...just a hint, electricians are not dumb and the question didn't say that I can't assume ✌️
Technology is improved bro
I will just use camera to see which bulb turns on when I flick each switch 😅😂
Amazing...great idea...
Amazing videos
Sir, please increase the no. of videos per month
Hi Jatin, thanks for the appreciation :) and I will definitely increase the frequency of uploading videos.
@@LOGICALLYYOURS thanks for the reply sir
Amazing puzzle
ECE engineers be like: welcome to my world!!!
by seeing this puzzle's solution, i realised how dumb am i
haha, no need to feel dumb... Many people fail to solve binary puzzle first time. Later you'll be able to correlate binary based problems very easily.
Great video first I felt the three switches three bulb puzzle. Then I umderstood❤❤❤
Shubham... in fact when a puzzle has switches and lights, our first instinct would be the heating concept. So i put the condition in the start that it's not a heating based puzzle.
Can’t we use ternary number system, using hot off bulbs as third state. Answer will be 5 in that case.
Only one move.
Video call someone outside room and ask the person to switch on and off the switches when you are inside.
How about using triary number :
1. Divide the switches into 3 groups (let say group 0, 1, and 2)
2. Switch on the group 2
3. After some time, switch on the group 1
4. F*CKIN QUICKLY go the the room
5. Now each of the lights has one off these states : off (group 0), only on (group 1), and on+warm (group 2). Mark each light based on its state
you will need less trip.. only 5 trips to map the 100 lights
Fantastic, thank you 😀
How can you say that the off button is joined to off bulf there are total 99 off bulbs in room
Not going to lie but at the starting I was doubting your method 😅 but you explained it very well 👍❤️
Good solution, thank you.