Puzzles

Some puzzles I like.

Eight Batteries

You have a flashlight that takes 2 working batteries. You have 8 batteries but only 4 of them work. What is the fewest number of pairs you need to test to guarantee you can get the flashlight on?

Note: The answer probably is one less than you might think initially.

100 Prisoners

The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a last chance. A room contains a cupboard with 100 drawers. The director randomly puts one prisoner’s number in each closed drawer. The prisoners enter the room, one after another. Each prisoner may open and look into 50 drawers in any order. The drawers are closed again afterwards. If, during this search, every prisoner finds their number in one of the drawers, all prisoners are pardoned. If just one prisoner does not find their number, all prisoners die. Before the first prisoner enters the room, the prisoners may discuss strategy - but may not communicate once the first prisoner enters to look in the drawers. What is the prisoners’ best strategy?

Note: There is a strategy that provides a survival probability of more than 30%.

Due to Philippe Flajolet and Robert Sedgewick, text taken from Wikipedia.

100 Prisoners and a Light Bulb

100 prisoners are sentenced to life in prison in solitary confinement. Upon arrival at the prison, the warden proposes a deal to keep them entertained, certain that the prisoners are too dim-witted and impatient to accomplish it. The warden has a large bowl containing the cell numbers of all the prisoners. Each day he randomly chooses one cell from the bowl, the corresponding prisoner is taken to the interrogation room, and the cell number is returned to the bowl. While in the interrogation room, the prisoner will not be allowed to touch anything except the light switch, which the prisoner may choose to turn on or off. The prisoner may make the assertion that all 100 prisoners have been in the room. If the prisoner’s assertion is correct, all prisoners will be released. If the prisoner is incorrect, the game is over and their chance to be freed is gone. The prisoners are given one meeting to discuss a strategy before their communication is completely severed. What strategy should they adopt in order to ensure, with absolute certainty, that one of them will guess correctly and all be freed?

Note: The prisoners know that the light initially is OFF. There is a winning strategy (not relying on chance).

Text adapted from Brett Berry.