Puzzle- 100 Prisoners and a Light Bulb

Every once in a while, I hear puzzles about 100 prisoners and a meticulous, demanding warden. All of these puzzles share a common characteristic, a set of prisoners must work together to devise a clever scheme to thwart the warden. I hear these puzzles often enough that each time they reappear, I view them with an increased level of understanding corresponding to the stage of my mathematics education. Any problem may have a solution, but, sometimes, that solution may not be the most efficient one possible. For example, suppose you want to find something in your room but don’t remember where you put it. You can either search the room by yourself. Or you can call your (many) friends to help you. From a correctness standpoint, both solutions are correct. You’ll find what you’re looking for eventually. But from an algorithmic standpoint, the second solution where you search in parallel with your friends is better because it has a shorter runtime. The same holds for solutions to the 100 prisoners puzzle. Some solutions may be theoretically correct answers to the puzzle but may have expected runtimes that exceed the life span of an average person and are, thus, practically undesirable. Now, through this lens, the lens of a theoretical computer science student, I would like to present to you the 100 prisoners puzzle and its variants.100 Prisoners and a Light Bulb The original, very famous puzzle involving an interrogation room, a light bulb, and 100 prisoners is the following :

One hundred prisoners just arrived in prison. The warden tells them that starting tomorrow, each of them will be placed in an isolated cell, unable to communicate amongst themselves. Each cell has a window so the prisoners will be able to count the days. Each day, the warden will choose one of the prisoners uniformly at random with replacement, and place him in a central interrogation room containing only a light bulb with a toggle switch. The light bulb is initially switched off. The prisoner may observe the current state of the light bulb. If he wishes, he may toggle the light bulb. He also has the option of announcing that he believes all prisoners have visited the interrogation room at some point in time. If this announcement is true, then all prisoners are set free, but if it is false, all prisoners are executed. The warden leaves and the prisoners huddle together to discuss their fate. Can they agree on a strategy that will guarantee their freedom?

What you think about this puzzle? Subscribe My newsletter and stay tuned to my blog. Do share your thought below in the comments.

Comments

Time Management: Pomodoro Technique

Are you facing challenges in managing your time properly? If you often waste time on unproductive tasks and finally at the end of the day feel you have wasted your day. Pomodoro Technique may be a good solution to all your problems. Today I am going to discuss here, a very useful technique to improve your productivity and better time management. The credit for this technique goes to Francesco Cirillo. He utilized a tomato-shaped sandglass to manage his time effectively. He called it the Pomodoro technique (which is an Italian word for “tomato”). The idea behind the Pomodoro Technique is to break down all of your tasks into 25-minute time blocks. Between two session , keep a five-minute break. And after completing four Pomodoros sessions taking an extended break usually 15-20 min. There are six steps in the original technique: Decide on the task to be done. Set the Pomodoro timer (traditio...

Ramanujan in London

When super genius Indian Mathematician Srinivasan Ramanujan arrived London, he was greeted by Professor Godfrey Harold Hardy. Just to break the silence , Hardy commented on the Taxi number , he came in is 1729- " seems like an uneventful number". Ramanujan had a cursory glance at the taxi number plate himself and replied casually "Oh No, actually it's a really interesting number. It is the smallest number representable in two alternative ways as the sum of two cubes and then this brilliant man told the equation on the spot. 1729 is the sum of the cubes of 10 and 9 - cube of 10 is 1000 and cube of 9 is 729; adding the two numbers results in 1729. 1729 is also the sum of the cubes of 12 and 1- cube of 12 is 1728 and cube of 1 is 1; adding the two results in 1729.

IIT Delhi Launches IITPAL Portal

The Indian Institute of Technology (IIT) Delhi launched an interactive IIT- PAL website —iitpal.iitd.ac.in — to give free videotape lectures to class 11 and 12 scholars who are preparing for competitive examinations similar as JEE, NEET, IAT and others. www.iitpal.com This action of the Ministry of Education (MoE) had started with an end to make their understanding of the wisdom subjects (Physics, Chemistry, Maths and Biology) better and to help tone- studying scholars do well in competitive examinations like JEE, NEET, IAT and others. Now, to bring all coffers together, IIT-D has launched a website. The website —iitpal.iitd.ac.in — will act as a single platform where scholars across India can pierce videotape lectures that are telecast on the Ministry of Education’s Swayam Prabha Channels, interact live with IIT Professors and ask them questions. “ This website will be helpful to scholars especially from regions where they may not have access to specialist prec...

IITPAL

Search This Blog