Puzzles

Main Sources:
https://forums.serenesforest.net/index.php?/topic/19021-math-thread/#comments
http://wiki.xkcd.com/irc/Puzzles

=====
Bulbs
=====
An evil megalomaniac has set you a task. You are in a room with three switches, all of which are off. One of them controls a lightbulb in the next room. You may manipulate the switches as much as you like for as long as you like, and then you must go into the room with the lightbulb.

You must tell your captor which switch controls the light or he will execute you.

===============
Bridge-Crossing
===============
4 people need to cross a thin bridge one night. Only two people can cross it an once, and since it's dark, the flashlight needs to be with any person or pair crossing the bridge. One of them can travel across the bridge in 1 minute, one can travel across it in 2 minutes, one can travel across it in 5 minutes, and one can travel across it 10 minutes. If two are going across at once, they will travel at the slower speed. What is the fastest way for everyone to cross the bridge?

=======
Buckets
=======
I have three buckets: One holds 8 liters, one holds 5 liters and one holds 3 liters. My 8 liter bucket is full, but I need to get 4 liters from them today. How can I do it?

================
Combining Chains
================
You find 5 chains. 2 of them have 3 rings, and 3 of them have 4 rings. You take them to the blacksmith to make one long unbranched chain. It costs 10 cents a cut and 10 cents a weld. Each cut only cuts one ring (so no stacking) and each weld only welds one ring as well. What is the cheapest way to make the chain, and how?

==============
String-burning
==============
You have 2 pieces of string of different, unspecified length, and some matches. Each piece of string takes exactly an hour to burn, but the burn rate is not constant. This means that it could take 59 minutes to burn the first 1⁄4, and 1 minute for the rest. The strings have different burn rates, and of course you don't know the rates anyway.

Using only the matches and the strings, measure 45 minutes.

====================
Mutilated Chessboard
====================
Given a mutilated chessboard where two diagonally opposite squares are missing (the unmutilated version of it has 64 squares), and given 31 domino pieces (that measure 2x1), is it possible to cover the entire chessboard with the dominoes?

=======================
Three Men and a Bellboy
=======================
One day three men go to a hotel, rooms are $10 each, and they pay a total of $30 for their rooms. Later, the landlord remembers they have a special offer, three rooms for $25.

He gives $5 to the bellboy to give back the men. The bellboy, instead of trying to split $5 three ways, keeps $2 and gives each man $1 back.

Now, the three men have each paid $9, a total of $27. With the bellboy's $2 this only amounts to $29. Yet they paid $30 initially, where did the other $ go from their $30?

================
Tree Arrangement
================
You have ten trees. Line them up in such a way that you have 5 rows of 4 trees each.

================================
Wolves and Sheep on a Chessboard
================================
On a 5x5 chessboard, you must place 5 wolves and 3 sheep. A wolf moves like a queen in chess (vertically, horizontally, or diagonally), and none of the sheep can be in the attack range of the wolves. Where are all of the animals placed?

===================
Lying about the Day
===================
You ask four people about what day it is, and get these answers:
A: Yesterday was Wednesday.
B: Tomorrow will be Sunday.
C: Today is Friday.
D: The day before yesterday was Thursday.
Because everything you need to know is how many people lied, I will not tell. What day of the week was it?

===============
Ants on a Stick
===============
100 ants (zero-length points) walk on a meter stick (a line) at 1 cm/second. When two ants collide, they both reverse direction. If an ant reaches the end of the stick, it falls off. What arrangement of ants maximizes the time before all ants have fallen off? How long can they last?

Alternative: There are (n + k) ants on the meter stick, evenly spaced with one ant on each end. The n ants on the left are initially moving right, while the k ants on the right are initially moving left. How many ant collisions will there be before all ants fall off?

=============
Face-Up Cards
=============
You are blindfolded and given a deck of 52 cards, with the guarantee that 26 of the cards are face-up, while the other 26 are face-down. You are to present the cards as two piles in a desk in front of you such that each pile contains the same number of face-up cards as the other pile. How do you do it?

=============
Pill Accident
=============
You wake up feeling sick one morning, so you go to doctor. He tells you that the illness you have is normally terminal, and most people with it die. But there is a recently developed cure that hasn't started mass production yet. He gives you two bottles: one labeled A and one labeled B, each containing 15 solid pills. For the next 15 mornings, you will have to consume exactly one A pill and exactly one B pill. If, in one morning, you eat more or less than that, you will die in 6 hours. Also, the A and B pills are identical and completely indistinguishable, even by the doctor himself. Finally, there are no other A or B pills in the entire world until the next batch completes production in 15 days.

So the next morning you follow your instructions and eat one of each pill. The morning after that, however, you accidentally pour one A pill and two B pills into your hand, and you don't know which is which. What do you do?

===============
Three daughters
===============
A mathematician enters a bar and starts chatting with the bartender. The bartender tells him about his three daughters, and when he is asked about their age, he decides to make it a bit more interesting, as he is interested in mathematics as well. He says, “The product of their ages is 72.” The mathematician answers, “OK, but that didn’t help a lot.” — “Then I should tell you that the sum of their ages is equal to the street number of this bar.” The mathematician leaves the bar, returns, and says, “Great, but I still don’t know their age.” The bartender smiles and says, “My youngest daughter really likes strawberry ice cream.” Now the mathematician knows their ages.

How old are the three daughters? (Think of age as an integer of the number of years.)

==========
Monty Hall
==========
You're about to go on a game show.

In this game show, the host, Monty Hall, will ask you to select from 3 doors. One of the doors holds the main prize, the others are booby prizes you don't want. Monty knows what is behind the doors. After you have selected a door Monty will always open another door that is the booby prize, selecting randomly if there are two booby prizes to pick from. Monty will always then ask if you want to change your choice to the other remaining door.

You pick a door randomly, and Monty Hall then opens another door with the booby prize, as expected, and then asks if you want to change your choice. Would changing your choice affect the probability of winning? Why or why not?

==============
Poisoned Wells
==============
A dragon and a knight live on an island where the only sources of fresh water are a lake (containing ordinary water) and six wells, numbered 1 to 6. Each well's water is completely indistinguishable from lake water, but contains a magical poison that has no immediate symptoms, yet suddenly kills the drinker about an hour after imbibing.

But, each well contains a different variety of poison. If a drinker who has been poisoned by a well drinks the water from a higher-numbered well, then both poisons will eliminate each other and the drinker will be cured. This effect only works when the lower-numbered well's poisoned water is drunk before the higher-numbered well's water.

As a result of these rules, water from well 6 can cure poison from any of the other wells, but, when drunk by someone who is not poisoned, is incurably lethal.

Furthermore, while wells 1-5 are a short walking distance from each other, well 6 is located at the top of an unclimbable mountain on the island that the knight cannot reach but the dragon can fly onto very quickly.

This sets the stage for the following puzzle: both knight and dragon understand these rules completely, and each want the other dead. Being evenly matched in combat, they arrange a special sort of duel. Each secretly fills a glass of water from one of the island's sources, then meets the other in a field, where they exchange glasses, and drink. Then, they may seek water from any of the island's sources that they can personally reach.

Level 1: As the dragon, can you guarantee your survival?
Level 2: As the knight, can you guarantee your survival?

Note: drinking the same poison twice in a row (or 20 times in a row) has exactly the same effect as drinking the poison once.

==========================
Coins in Four Compartments
==========================
There is a circular device with four quarter-circle compartments and a light bulb in the center. Each compartment carries a coin, and the light bulb will only turn on when the compartments are closed and if either all four coins face heads or if they all face tails.

The game runs in five stages. At each stage, you are allowed to open any two compartments at the same time, look at the coin states inside, and can choose to flip the coin states for one or both the coins. Then the compartments are closed at the same time, and the device will spin very quickly so that you cannot identify the compartments after the device stops.

How can you ensure that the light is on after all five stages?

==================
Points on a Circle
==================
There are n points that are randomly generated with uniform distribution at the circumference of a circle. What is the probability that all n points lie within a semicircle?

================
The Lake Monster
================
You are on a rowboat in the middle of a large, perfectly circular lake. On the perimeter of the lake is a monster who wants to eat you, but fortunately, he can't swim. He can run (along the perimeter) exactly 4x as fast as you can row, and he will always run towards the closest bit of shore to your boat. If two paths take him to this location equally quickly, he will arbitrarily choose one. If you can touch shore even for a second without the monster already being upon you, you can escape. The monster can reverse direction instantaneously and you can turn your boat instantaneously. Suggest a strategy that will allow you to escape, and prove that it works.

======================
Returning to the Start
======================
Level 1: From point A, I travel 400 km South, then 400 km East, and then 400 km North and find myself back to point A. How?
Level 2: I repeat this exercise of traveling 400 km South, then 400 km East, and then 400 km North everyday for a year, but I start at a different point each day. I always find myself back to the starting point of the exercise. How?
Level 3: Same as Level 2, except I also mark the path in which I travel, and find that for the exercise of each day, the path overlaps at only finitely many points with the paths of all the other days in the year. How?

Note: Smooth globe (no mountains or valleys), cardinal directions defined as usual.

=============
Two Guardians
=============
You are trapped in a dungeon and must escape, when you face two supernatural guardians guarding two doors in an unknown order. One door is the exit to freedom, while the other leads to certain death. The two guardians are Truth, who always tells the truth, and False, who always lies. You can ask only one yes-no question, and to only one guardian. If a guardian is faced with a question to which either answer is possible or neither answer is possible, he answers randomly. What question can you ask to determine which door leads to the exit?

===============
Three Guardians
===============
You are trapped in a dungeon and must escape, when you face three supernatural guardians guarding three doors in an unknown order. One door is the only exit to freedom, while the other two lead to certain death. The three guardians are Truth, who always tells the truth, False, who always lies, and Random, who answers randomly. The guardians only speak in a two-word language in which Ja and Da mean 'yes' and 'no', but you do not know which is which. Truth and False understand English (and other languages for that matter) and have complete knowledge of everything. Random's mind can be modeled as a fair coin flip for which, if it lands heads, he will say Ja; if tails, Da.

You can ask up to three yes-no questions total, each to one guardian (though any guardian can be questioned more than once). Which three questions should you ask to determine which door leads to the exit?

If a guardian is faced with a question to which either answer is possible or neither answer is possible, he answers randomly.

VARIATION: If a guardian is faced with a question to which neither answer is possible, his head explodes. In this variation, you are allowed only two questions.

=========
Blue Eyes
=========
A group of people with assorted eye colors live on an island. They are all perfect logicians- if a conclusion can be logically deduced, they will do so instantly. No one knows the color of their own eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph.

On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes). So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and one with green), but that does not indicate their own eye color; as far as the individual knowsm the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and the individual could have red eyes.

The Guru is allowed to speak once (let's say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following:

"I can see someone who has blue eyes."

Who leaves the island, and on what night?

==========================
Bananas and a Hungry Camel
==========================
A farmer grows 3000 bananas, and wants to take them to market to sell. The market, however, is 1000 miles away, and the only way he can get there is by means of a hungry camel, who can carry a maximum of 1000 bananas at a time, but needs to eat a banana to refuel for every mile he walks.

What is the maximum number of bananas that the farmer can successfully get all the way to market?

Note: We are talking entirely in discrete bananas here, although it may be useful to model the problem treating them as continuous and then go back to thinking in discrete terms the end.

===================
Smurfs and Gargamel
===================
Gargamel has captured 100 Smurfs. Feeling confident he proposes the following game:

He will exchange the white hats of an undefined number of smurfs with red hats. No smurf knows his own color. The smurfs are to be positioned in a long queue such that each Smurf can only see the hats of the Smurfs in front of him, but they have no other means of communication. Then, each Smurf, starting from the back and moving forward, should say the color of his hat (loudly so that everyone can hear it). If it is correct, then he lives, otherwise he dies.

The smurfs can discuss their strategy before the game begins. How can the Smurfs maximize the number of guaranteed survivors?

===============
Sum and Product
===============
A teacher announces to her students, "I have picked two integers a and b that are both greater than 1 whose sum is less or equal to 100. I will tell Rod their product and Sue their sum."

After the teacher gives the two students, who are both perfect mathematicians, the information, they have this conversation:

Rod: I do not know the values of a and b.
Sue: I already knew that.
Rod: I now know the values of a and b.
Sue: I now also know the values of a and b.

What are the values of a and b?

========================
Interrogation Room Light
========================
100 people are being held prisoner in a jail. They are told that in one hour, they will all be taken to separate windowless, soundproof cells. One at a time, and in a random order, they will be taken from their cells, interrogated, and then sent back to their cells. All interrogations will take place in the same room, which contains one light bulb and the switch that operates it. The light is initially off, but the inmates are free to toggle the switch as often as they want, whenever they are in the interrogation room, and the prison guards will not toggle the switch at all. The light can only be seen from inside the interrogation room. Only one prisoner is interrogated at a time, each prisoner can be interrogated multiple times, and they have no way of communicating besides the light switch. The length and amount of time between interrogations is random, so no help there.

At any time, any prisoner under interrogation may state, "Everyone has been interrogated at least once." If this statement is true, everyone will be released. If it is false, all of the prisoners will be executed.

The prisoners have one hour to work out their strategy before they're isolated for good. How do they get released?

Note: The selection process for interrogations is random and fair; some prisoners may be interviewed multiple times before another prisoner is interrogated at all, and after any point in time, every prisoner will be interrogated an infinite number of times more.

==================
Boxes with Numbers
==================
A certain prison has 101 prisoners. The warden offers the following deal: Each prisoner has a unique number from 0 to 100. In one room, 100 boxes stand in a row. Into each box is placed a scrap of paper containing a number from 1 to 100. Each number appears exactly once, in unknown order. Prisoner 0 will first enter the room, and will be allowed to view the contents of all boxes, and can choose to select two boxes to have their papers switched. Prisoner 0 will then leave the room.

After that, the remaining 100 prisoners will be allowed to enter the room one at a time, and open boxes one at a time, up to 50 boxes. They may only look in the box to see what number is there, they may not move the scraps of paper or the boxes. All boxes will be closed after the prisoner leaves the room, before the next prisoner is brought in. If any prisoner fails to open the box containing their own number, all the prisoners will be put to death. If each of the 100 prisoners finds their own number, then all prisoners will go free. Once the process begins, prisoners will not be allowed to communicate with each other in any fashion. By what strategy can the prisoners guarantee their survival?

===============
Circular Prison
===============
You, together with a finite number n-1 of other ideal mathematicians, have been arrested on a whim by a generic evil dictator and are about to be locked up in a prison. The prison is circular, with n identical windowless cells arranged in a ring around a central court. There are some problems with the lighting system - the light switch in each cell controls the light in the next cell clockwise around the ring. Even worse, electric power is only provided to the lights for one tenth of a second each night, just after midnight.

The warden is worried that you might use the lights to communicate (very slowly), so he will very often rearrange the prisoners, moving them about between the cells in any way he chooses and having all the cells cleaned to prevent prisoners leaving messages for one another. He might do this every day. This will all be done in such a way as to keep you all in ignorance; you will never see each other or any part of the prison except the inside of the cells. You do not even know how many other mathematicians are to be locked up with you.

The warden visits you in your cell, and explains that if you are able to communicate despite these precautions he will consider you all worthy of release. At any time, any prisoner who believes he has discovered how many prisoners there are may petition the warden for release. That prisoner will be allowed one guess at the number of prisoners; if they guess correctly, then all the prisoners will be released, but if they guess incorrectly then all the prisoners will be executed.

You have been chosen to devise a strategy by means of which you will be able to discover the number of prisoners. You may compose a single email outlining your strategy, which will be passed to all the prisoners. However, your strategy must be foolproof, as the warden (who has a deep hatred of ideal mathematicians) will also read your email. What strategy will guarantee your release?

=====================
Magic Chessboard Tile
=====================
There are two prisoners, and a warden. The warden explains a way for them to go free. He has in his room an 8x8 chessboard, and 64 quarters. He proposes this challenge: He will go into his room, and randomly flip the quarters, either heads or tails, and place each quarter on one of the tiles in the chessboard. Then, one of the prisoners will go into the room. The warden will point to one of the tiles, which is the Magic Tile. This prisoner must then flip exactly one of the coins on the chessboard, and then leaves. The second prisoner will then come into the room, without ever seeing the board before the change. If the second prisoner can correctly point out the Magic Tile, then they will both go free. What is the strategy that the first prisoner should use to make sure they both go free?