Here's a collection of XKCD puzzles.
One more probability puzzle
Given a set X with N elements, and sets A and B which are subsets of X, what is the probability of A being a subset of B.
[edit] Coin tosses
(
From here)
Sue and Bob take turns rolling a 6-sided die. Once either person rolls a 6 the game is over. Sue rolls first, if she doesn't roll a 6, Bob rolls the die, if he doesn't roll a 6, Sue rolls again. They continue taking turns until one of them rolls a 6.
Bob rolls a 6 before Sue.
What is the probability Bob rolled the 6 on his second turn?
Note: it is not (5/6)*(1/6).
[edit] Ants
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?
[edit] Blue Eyes Puzzle
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 it instantly. No one knows the color of their 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 tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he 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?
There are no mirrors or reflecting surfaces, nothing dumb. It is not a trick question, and the answer is logical. It doesn't depend on tricky wording or anyone lying or guessing, and it doesn't involve people doing something silly like creating a sign language or doing genetics. The Guru is not making eye contact with anyone in particular; she's simply saying "I count at least one blue-eyed person on this island who isn't me."
Note: The answer is not "no one leaves."
[edit] The Monty Hall Problem
Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat (At this point in the show, he always opens a door to show a goat regardless of what you picked.) He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?
Note: It is assumed you would rather win a car over a goat.
Note: Assume h = 6.626 068 96×10^{−34} Js
[edit] Resistor Grid
Given an infinite rectangular lattice of 1-ohm resistors, what is the equivalent resistance between two nodes a knight's-move away?
Note: This one is not so much counterintuitive as just mathematically difficult.
[edit] The Bridge
4 people need to traverse a bridge. The bridge is old and only two persons can use it at the same time. It is night and to traverse the bridge a flashlight is needed.
The group only has one flashlight. Each person traverses the bridge at different speeds and when 2 go together the faster one needs to adapt for the slower one (otherwise they can't share the light).
The first person (A) needs 10 minutes to cross the bridge. The second (B) 5; the third (C) 2 and the fastest one (D) only 1 minute.
How long does it take the group to cross the bridge.
Example (not the most efficient one):
A+D -> // 10 min (let's assume the slowest and the fastest go first)
D <- // 1 min (D needs to bring back the flashlight)
B+D -> // 5 min
D <- // 1 min
C+D -> // 2 min (and the group has crossed the bridge)
--
totals 19 minutes.
There is a better way.
Note: A computer program would find the solution. So no tricks involved.
[edit] Coin tosses 2
Sue and Bob are playing the following game:
Sue pays Bob $2 to start the game. Then Bob starts tossing coins. If the coin falls on head Bob pays Sue $1 and continues tossing the coin. If however the coin falls on tails then the game is finished.
Example 1: Sue pays Bob $2. Bob tosses head three times in a row before finally tossing a tails. For each head Bob pays Sue $1 and Sue thus wins $1.
Example 2: Sue pays Bob $2. Bob starts by tossing tails and Sue thus loses her $2.
Clearly Sue has a disadvantage here. The question is: what is the correct initial amount, so that neither Sue nor Bob have an advantage.
Note 1: the difficulty lies in the fact, that Sue could potentially win an infinite amount of money if there is an infinite number of head-tosses.
Note 2: there is a way to easily get the correct amount without getting into "infinity".
[edit] 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. All smurfs can see each other, but they have no other means of communication. Then, each Smurf (order selected by Gargamel) should say the color of his hat (loudly so that everyone can hear it). If it is correct, then he lives, otherwise he dies.
After a short discussion the smurfs accept. They know that the first Smurf to be chosen might die, but all 99 other smurfs will survive.
How?
Note: as usual no trick. Nothing time-related...
[edit] Prisoners
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. 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.
Note2: For bonus points, what is their strategy if they don't know the initial state of the light switch?
Alternative: suppose there is one interrogation per day. In this case there exist different more efficient solutions.
[edit] Pirates
100 pirates (p1, p2, ... p100) are dividing up a treasure consisting of 50 indivisible gold coins of equal worth. The pirates have a total-order hierarchy, i.e. pirate p1 is the head pirate, p2 is a rank lower in the order, p3 lower still, ... The process works like this: The highest ranking pirate which is still alive proposes how he would like to divide the treasure. Then all living pirates (including him) vote on the proposal. If at least half of the pirates alive vote for the proposal, then it is accepted, otherwise the pirate who made the proposal is killed and the process is repeated. The pirates are perfectly intelligent, logical and rational (see Blue Eyed Puzzle). Each pirate's priorities are, in this order: Survival, wealth (getting the highest number of coins possible), bloodthirstiness (seeing as many pirates killed as possible, other than himself). In other words a pirate will always choose an outcome in which he lives over one in which he dies. Given two outcomes in which he lives, he will choose the one where he gets more coins. And given two outcomes in which he lives and gets the same number of coins he will choose the one in which the highest number of other pirates die. How will the gold coins be divided?
Note: For bonus points, how will the gold coins be divided if there are 200 pirates?
[edit] Cyclic List Algorithms
Not really "puzzles" per se, but still very interesting.
Find an algorithm that determines if a list is cyclic. The algorithm should be in O(n) for speed (where 'n' is the number of distinct elements of the list) and in O(1) for space.
The list does not necessarily start with a cycle.
For Schemers, the following would be a cyclic list:
(let ((l (list 1 2 3)))
(set-cdr! (cddr l) (cdr l)))
Once that's done: if the list is cyclic find (same complexities) the first element that is within the cycle. In the example above that would be 2 of the sub-list '(2 3 ...).
[edit] Two Beagles
A shopkeeper says she has two new baby beagles to show you, but she doesn't know whether they're male, female, or a pair.
You tell her that you want only a male, and she telephones the fellow who's giving them a bath.
"Is at least one a male?" she asks him. "Yes!" she informs you with a smile.
What is the probability that the other one is a male?
(The birth ratio of beagles is exactly 50/50 for the purpose of this problem)
[edit] String-burning
You have 2 pieces of string of different, unspecified length, and some matches. Each piece of string takes one 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.
[edit] Magic Watch
You have a very nice, shiny watch. But this is no ordinary watch. This watch can answer two yes or no questions 100% accurately per day. You ask, and either a blue or yellow light will flash. Unfortunately, you don't know which light means yes and which light means no, and you can never find out because there's a 50-50 chance of the lights switching every night.
You happen to be on a game show. The rules are simple. There are three doors. Behind two are goats. Behind one is a shiny red car. Obviously, you want the car. You can choose any door, after asking the watch two questions.
What are the two yes/no questions you can ask so that you will have a 100% guaranteed chance of getting the car?
[edit] Light Bulbs
There are 100 light bulbs lined up in a row in a long room. Each bulb has its own switch and is currently switched off. The room has an entry door and an exit door. There are 100 people lined up outside the entry door. Each bulb is numbered consecutively from 1 to 100. So is each person.
Person No. 1 enters the room, switches on every bulb, and exits. Person No. 2 enters and flips the switch on every second bulb (turning off bulbs 2, 4, 6, ...). Person No. 3 enters and flips the switch on every third bulb (changing the state on bulbs 3, 6, 9, ...). This continues until all 100 people have passed through the room.
How many of the light bulbs are illuminated after the 100th person has passed through the room? More specifically, which light bulbs are still illuminated, and why?
[edit] Dumbass, M.D.
From
defective yeti: Dumbass, M.D.
You have Some Terminal Condition, which necessitates taking two pills a day: one Pill A and one Pill B. If you neglect to take either pill, you die; if you take more than one A or more than one B, you die. If you don't take them at exactly the same time, you die.
This morning you are going through your usual routine. You pick up your bottle of A Pills and gently tap one into your palm. Then you pick up your bottle of B Pills and tap it, but two pills accidentally fall into your hand. You now hold three pills (one A and two Bs), you don't know which are which, and they are completely indistinguishable from each other. The A Pills are the same color as the B Pills, they are the same shape, same size -- they are identical in every respect. Man, your doctor is a dumbass. But he's a rich dumbass, because he's charging you $10,000,000 a pill! So you dare not throw any away.
Thus, the puzzle: what can you do to ensure that you take only one A Pill and only one B Pill today, without wasting any pills (either today or in the future)?
[edit] PEARLS!
Yragle the pirate has 100 white pearls and 100 black pearls. The white pearls are worthless, the black pearls are priceless. He will let you arrange the pearls in two sacks, and then after he mixes up the pearls in each bag and shuffles the bags he will let you pick a pearl from one of the two bags. How should you distribute the pearls between the two sacks to maximize your odds of getting a black pearl?
[edit] Bit Algorithm
Apparently the following algorithmic problem has been given during Google interviews.
Propose an algorithm that counts the number of bits that are 1 in a given number n.
Your algorithm should not rely on any assumptions on the number's size (nb of bits) and should be in O(i) where i is the number of 1-bits inside n. We assume that operations (bit-operations and arithmetic operations) can be executed in constant time.
[edit] One-lane Highway
(Another interview question)
You have N cars that are all traveling the same direction on an infinitely long one-lane highway. Unfortunately, they are all going different speeds, and cannot pass each other. Eventually the cars will clump up in one or more traffic jams.
In terms of N, what is the expected number of clumps of cars?
