Puzzles

From XKCD Wiki
Jump to: navigation, search

This is a page for problems/puzzles which appear simple but are fiendishly counterintuitive. Try to keep a nice balance and add quality puzzles. Perhaps solutions can be discussed on the talk page. We can think of some way to organize it as we add more puzzles.

Note: If you don't think a particular problem is interesting enough to be included here, don't hesitate to say so on the talk page and, if others agree, remove it. Every problem on this page should be subtle, interesting, and worthwhile to people who like puzzles.

Contents

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?

Dice Rolls

(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).

Note #2: To all the people claiming this puzzle is poorly-stated or ambiguous, or that the answer given is wrong, before posting with your analysis, try writing a short program to simulate the game as you understand it. Count the percentage of Bob's wins that come on his second turn. Now that you have an empirically correct answer, feel free to discuss.

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?

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 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 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."

The Monty Hall Problem

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.

Before going on you pre-determine that you will say "yes" to changing the door. Have you gained any advantage from doing this? What is the probability of your winning? More importantly, why, and why are the above assumptions required?

This fooled many intellectuals when it was first proposed (although it was not explicit about some of the above assumptions).

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.

The Bridge

4 people need to traverse a bridge. The bridge is old and only two people 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.

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".

Variation: What if the pot increases exponentially, rather than linearly? Let's say the pot starts at 1 dollar and doubles each time Bob tosses a head. So if Bob tosses head three times in a row before tossing tails, Sue will win 1 * 2 * 2 * 2 = 2^3 = 8 dollars. Question is the same: how much money should Sue be willing to pay to enter the game?

Note to variation: this game is known as the St. Petersburg paradox, so don't think too hard. Check it out on Wikipedia.:)

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...

Alternative 1: Suppose that instead of just red and white hats, Gargamel randomly distributes n different hat colors (including white) among the smurfs, where the number of colors n is less than 100, the number of smurfs. Assume the smurfs know all the possible hat colors. How many smurfs must be put at risk of death before the rest are guaranteed to survive?

Alternative 2: what if the Smurfs are positioned in a long queue such that each Smurf can only see the hats of the Smurfs in front of him? Assume Gargamel always starts at the back of the queue and works forward.

Alternative 3: Suppose there are infinitely many Smurfs (perhaps uncountably many) and all at once each must say the color of his own hat. Again, the Smurfs formulate a plan (perhaps using a bit of Smurf magic) and accept, knowing that a finite number may die but the rest will live. How?

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. No prisoner can see the light from his cell. 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.

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 who 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?

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 ...).


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 both beagles are male?
(The birth ratio of beagles is exactly 50/50 for the purpose of this problem)

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.

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?

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?

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.

Extra Credit (requires Calc): What is the minimum speed of the monster (relative to your boat) such that escape becomes impossible?

The Spinning Log

A physicist builds a large room, then divides it in two by building a wall in the middle. He then replaces the middle section of the wall with a wooden log, mounted on pegs at the ringed ends such that it can spin. He places seals between the log and the wall such that it remains airtight. He then fills one of the two sections of the room with water. Since buoyancy will push upwards on only half the log, he figures the log will start spinning, and he will have a perpetual motion machine. Why doesn't this work?

Ball and Balance

You have a traditional balance scale, as well 12 coins. One of these coins is counterfeit, so it's heavier or lighter than the rest - but you don't know which. Using only 3 weighings, you must figure out which coin is the counterfeit AND whether it's heavier or lighter than usual. How can you do this?

Addendum 1: Fortunately, you've brought your Lucky Coin along, which you know to be legitimate. You can use it in the weighings if you'd like. However, you must now sort through 13 coins instead of 12, still given only 3 weighings. How can you do this?

Addendum 2: You still have your Lucky Coin, and you now have W weighings to sort through a pile of coins. What's the maximum number of coins (as a function of W) that you can process?

Addendum 3: Given W weighings and and the maximum possible number of coins, devise an algorithm that will always solve the problem.

Tally Game

The gameboard begins like this: III IIIII IIIIIII (groups of three, five, and seven). The players then take turns removing any number of sticks from the gameboard that don't have a space between them (for example, after the first player's turn, the board could look like this: III IIIII II III , since player one removed two from the middle of the group of seven). The person who takes the last stick from the board loses. If both players play perfectly, who will win the game?

Dumbass, M.D.

From http://www.defectiveyeti.com/archives/000339.html

You have Some Terminal Disease, 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 appear 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)?

Note: Counting the remaining pills in both bottles is not the solution.

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 distribute the pearls between two sacks, labeled "Heads" and "Tails." After you distribute the pearls, you flip a fair coin and choose a pearl at random from the corresponding sack. How should you distribute the pearls between the two sacks to maximize your odds of getting a black pearl?

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.

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?

More prisoners

A certain prison has 100 prisoners. The warden offers the following deal: Each prisoner has a unique number from 1 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, and the order is random. The 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 every prisoner 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. Clearly if each prisoner opens 50 boxes at random, the probability that everyone will go free is (1/2)^100, which is not very good. By what strategy can the prisoners improve their chances?

Alternative: Suppose you are the janitor and can talk with the prisoners beforehand. Afterwards, you cannot communicate with them in any manner, but are allowed to inspect all boxes and then, at your choice, switch two papers with each other (you are allowed at maximum one switch). You are then sent out of the prison and the process begins. What should you do to guarantee that all prisoners go free?

2 envelope exchange problem

From wikipedia:

"In a game a player is presented two envelopes containing money. He is told that one envelope contains twice as much money as the other envelope, but he does not know which one contains the larger amount. The player then may pick one envelope at will, and after he has made a decision, he is offered to exchange his envelope with the other envelope.

Assuming that the player wants to maximise his gain, the crucial question is: Should the player swap, that is, exchange the envelopes? Usually the answer to this question is made dependent of two circumstances, namely: Is the player allowed to see what's inside the envelope he has selected at first? How is the money in the envelopes selected, i.e., what is the probability distribution?"

Note: For this problem money is deemed to be continuous (i.e. you can have partial cents) so finding an amount with an odd number of cents is not a guarantee of having the lesser amount. Also, this problem is accepted to be paradoxical: Don't kill yourself for a solution :P

Manhole covers

Why are manhole covers round, and not square, or rectangle, or another shape that would be easier to manufacture?

Traffic Jams 2

Assume there is a one-lane highway with traffic uniformly moving at 65 mph. An accident occurs, causing cars to stop on the highway. After the accident is cleared off the road, the traffic jam persists. Does the traffic jam persist at the same spot where the accident occurred? Why or why not?

Delicious Pi

Its easy to divide a delicious cake between two people using the "I cut, you choose" method. One person cuts the cake, and the other picks which half they would like to eat. If both people would like to maximize their share of the cake, the cake will be divided perfectly evenly.

Describe a similar method for dividing a cake among 3 or more people.

What if different people have different values for different parts of the cake (for example, I love frosting, but you hate it)

What if someone screws up the cake cutting?

A Special Place

There's a special place on the globe. From this place, if you walk South 1 mile, then East 1 mile, then North 1 mile, you are back where you started.

Can you think of such a place? Could there be numerous examples of such a place?

More? (How about a countably infinite set of uncountably infinite sets?)


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

Note 2: With the extreme abundance of solutions, it's really kind of neat that everyone and their mother knows only the solitary outlier...

The Necktie Paradox

Two men are each given a necktie by their respective wives as a Christmas present. Over drinks they start arguing over who has the more expensive necktie, and agree to have a wager over it. They will consult their wives and find out which necktie is the more expensive. The terms of the bet are that the man with the more expensive necktie has to give it to the other as the prize.

The first man reasons as follows: the probability of me winning or losing is 50:50. If I lose, then I lose the value of my necktie. If I win, then I win more than the value of my necktie. In other words, I can bet x and have a 50% chance of winning more than x. Therefore it is definitely in my interest to make the wager. The second man can consider the wager in exactly the same way; therefore, paradoxically, it seems both men have the advantage in the bet.

Is there a problem here?

A Night at the Opera

Balcony seating at the opera is by ticket only, and all the tickets are sold and all the ticketholders are in line to enter. But it turns out that the first person through the door is rather inebriated by the time the hall is open for seating and, instead of taking the properly assigned seat, chooses a chair at random (presumably the one with the lowest-seeming relative velocity to his or her person). The next people come in one at a time—and if their seat is available, they take it. But if someone is already sitting there, rather than disrupt things, they just pick some other random seat. Which raises the question, "what is the probability that the last opera lover ends up in his or her assigned seat?"

Three Men and a Bellboy

(Read some time ago in The Times)

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?

Note - I found this in the children's section of the times. Also, there is really a solution.

Four Numbers

(found in a geocache puzzle)

I have four positive numbers, a, b, c and d (not necessarily integers).

Obviously, there are six ways to multiply pairs of them, yielding the products a*b, a*c, a*d, b*c, b*d and c*d.

I tell you what five of these products are (but not which product is what):

2, 3, 4, 5 and 6

What's the sixth product?

Hint: There's a quick and elegant way to answer that question without actually needing to know what the numbers are.

The Six 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.

Is it possible for either the knight or the dragon to ensure it will survive this duel?

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.

A Very Good Predictor (Newcomb's Paradox)

Five years ago, your rich uncle secretly commissioned the construction of a supercomputer! The purpose of this binary behemoth (the "Very Good Predictor") was to predict, as accurately as possible, every action you would take over the course of these five years. It has managed to do so with 100% accuracy for its entire runtime. Now, your uncle has approached you with this information, and an offer to participate in a game involving the supercomputer's final prediction.

He has placed two envelopes in a room: Envelope A and Envelope B. As your action within the game, you're allowed to open and then keep the contents of either just Envelope A, or both Envelopes. Envelope B contains a check for $1,000, says your uncle. He also tells you that the monetary content of Envelope A is contingent upon the prediction of the Very Good Predictor. If it predicted that you would only open Envelope A, then Envelope A contains a check for $1,000,000. However, if it predicted you would open both envelopes, then Envelope A only contains a check-sized piece of paper which reads, "Sorry, Champ, you're out of your league."

Please note that you cannot change your mind based on the contents of an envelope: reaching for Envelope B after opening Envelope A will result in your uncle's other computer, the Very Good Destroyer, melting your brain.

Do you only open Envelope A, or do you open both Envelopes?

If the former, can you justify not taking an Envelope which definitely contains $1,000?

If the latter, do you object to being called "Champ?"

Bonus: If you chose to only open Envelope A, what if the Very Good Predictor only had 99% accuracy, or, for that matter, 51% accuracy?

The bartender

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.)

The father

A mother is 21 years older than her child. The mother's age in six years will be exactly five times the child's age in six years. Where is the father?

Note: Solve the obvious part before complaining that it's impossible.

The mutilated chessboard and dominoes

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

Variation: Given another mutilated chessboard, this one with only one corner missing, and 21 tiles that measure 3x1, is it possible to cover the entire chessboard with tiles?

For bonus points: You have a whole chessboard that you want to tile with 21 of the 3x1 tiles. Exactly which square(s) can you knock out to allow such a tiling?

Two Dice

I roll two six-sided dice. At least one of them turns out to be a six. What is the probability that they are both sixes? (It is not 1⁄6.)

A Single Toss

A confused-looking man on the street asks if you want to play a game of chance. The rules are simple: He flips his coin, and if it lands on heads, you get $1. If it lands on tails, you get nothing. His coin, however, is very strangely shaped - it's bent all over, and you have no idea if it's even remotely fair. The man flips the coin once, and it lands on heads.

What is the maximum price you should be willing to pay to play this game now? You can assume that you know nothing about the true probability of heads for the coin before you saw the first head, and that probability is not going to change over time.

To further generalize, assuming any prior sequence of flips for the coin, what price is it worth to you to play the game? Also, what if the true probability of heads can only be one of a discrete set of values?

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)

Probability, and a barrel of balls

You have in front of you, a barrel of N ping pong balls, each labeled with a unique number. You pull a ball from the barrel, make a note of the label, and then put the ball back. After pulling K balls from the barrel, what is the probability that you've seen all of the balls?

Birthdays

This one is well known: "How many people do we need to have a probability of 1/2 that 2 people have the same birthday ?" but the reverse problem is not : "How many people do we need to have a probability of 1/2 that each day of the year is a birthday ?"

Note that the latter question is the same problem as the previous problem (barrel of balls) where N=365, except that you are given the probability and must solve for K

The Bee Problem

A bicycle is riding towards a brick wall 20 meters away at a constant 2 meters per second. A bee is initially touching the very front of the front wheel, and is flying towards the wall at a constant 5 m/s. When she touches the wall, she turns around instantly and flies back at 5 m/s, until she touches the wheel again, and flies back and forth repeatedly until her untimely demise between the wheel and brick wall. What total distance does the bee travel? Ignore things like acceleration; this is a math problem, not a physics problem.

(Note: The answer isn't 20 meters, that would be the total displacement.)

Cereal Box Game

As paraphrased from the back of a cereal box: Suppose you have a box of multi-colored cereal. The cereal comes in six colors: red, orange, yellow, green, blue, and purple. You also have a game board that has five rows. Each row contains a subset of the colors found in the box.

  • Row 1: Yellow, blue, green, purple, red.
  • Row 2: Yellow, blue, green, purple.
  • Row 3: Yellow, blue, green.
  • Row 4: Yellow, blue.
  • Row 5: Yellow.

The game is played by picking a piece of cereal out of the box. Beginning with row 1, you pick out pieces until you have collected all of the colors shown on that row, at which point you advance to the next row and start over. Picking the same color twice in a single row is allowed, but if you pick a piece that does not appear in that row, you lose and the game is over. You win the game by advancing past row 5.

What is the probability of winning this game?

Note: You may assume you have an infinite quantity of cereal equally distributed among each color (i.e. your odds of picking each color is exactly 1/6 at any time).

0=6

Original puzzle:Using one zero (and no other numbers) and mathematical (including trigonometric and advanced) operations, how can you achieve a final result of 6?

Advanced one: Using only trigonometric functions and a single instance of the number zero, derive a forumula to calculate any positive integer n.

Truth, lies and switching

You come across a road junction. One path leads to your destination, the other to certain doom. Three men are guarding the junction: one always tells the truth, one always lies and one alternates between truth and lies. But of course, you don't know which man is which.

You may ask two questions to find out which path to take (a question is directed at one man). What do you ask?


the hardest interview puzzle question ever

A hundred prisoners are each locked in a room with three pirates, one of whom will walk the plank in the morning. Each prisoner has 10 bottles of wine, one of which has been poisoned; and each pirate has 12 coins, one of which is counterfeit and weighs either more or less than a genuine coin. In the room is a single switch, which the prisoner may either leave as it is, or flip. Before being led into the rooms, the prisoners are all made to wear either a red hat or a blue hat; they can see all the other prisoners' hats, but not their own. Meanwhile, a six-digit prime number of monkeys multiply until their digits reverse, then all have to get across a river using a canoe that can hold at most two monkeys at a time. But half the monkeys always lie and the other half always tell the truth. Given that the Nth prisoner knows that one of the monkeys doesn't know that a pirate doesn't know the product of two numbers between 1 and 100 without knowing that the N+1th prisoner has flipped the switch in his room or not after having determined which bottle of wine was poisoned and what color his hat is, what is the solution to this puzzle?

Coaster Game

I propose a game: You and I take turns placing identical circular coasters on a circular table. The coasters cannot overlap. Whoever places the last coaster wins the game.

You can pick who goes first.

There is a simple strategy which ensures you will always win the game regardless of the table size and coaster size. What is it?

(The table can hold at least one coaster. We have plenty of coasters.)

In three ways

(From here)

Find three ways to make the program below print exactly 20 copies of the dash character '-' by changing or adding one character:

int i, n = 20;
for (i = 0; i < n; i--)
{
    printf("-");
}

Variations (using the same restrictions):

  • Find a way to get it to print exactly 21 dashes.
  • Find a way to get it to print exactly 1 dash.
  • Find many ways to print infinitely many dashes.
  • Find many ways to print 0 dashes.
  • Print 20 dashes with the given code, without changing it at all, but you are allowed to add some preceding code.
  • Print 1 dash with the given code, without changing it at all, but you are allowed to add some preceding code.

Defective Clock

James has a defective clock in his room. The clock is digital, and some of the seven bars on its units digit are broken. A bar that works is on when it should be and off when it should be, whereas a broken bar is off regardless of the time.

a) James enters his room and glances at his clock. He knows how many bars are broken but he doesn't know which ones they are. He immediately knows for sure what the time is.

b) James enters his room and glances at his clock. He knows which bars are broken and immediately knows for sure what the time is.

c) James enters his room and knows which bars are broken. He stares at his clock for 60 seconds. Now he knows for sure what time it is.

d) James enters his room. He knows how many bars are broken but he doesn't know which ones they are. He stares at his clock for 60 seconds. Now he knows for sure what time it is.

In each of these four scenarios, what is the maximum number of broken bars, and which might it/they be?

Pizza Paradox Puzzle

The king of the universe has decided to play a game. To start, he selects 1 person. He then flips two fair coins - if they both come up heads, the person gets a free pizza and the game is over. For any other result, he sends the person home and selects 2 new people, where he does the same 2-coin flip to decide if they each get a pizza. If they don’t, he picks 4 people at random, then 8, and so on, doubling each round. If you are selected but don’t win, you can’t be selected again – and you can assume the population is extremely large so there’s no chance of running out of contestants.

You are sitting at home when you get a call – you have been selected to play the game. What is the chance that you will get a free pizza?

You don't know which round number it is, but if you ask, the king will tell you. Does it matter?

The Hardest Logic Puzzle Ever

(Inspired by a very similar and slightly easier puzzle from George Boolos)

Three gods guard three doors in an unknown order. The three doors lead to Hell, Heaven, and Limbo, respectively; the three gods are Truth, who always tells the truth, False, who always lies, and Random, who answers randomly. The gods understand English (and other languages for that matter), but will only speak a two-word language in which Ja and Da mean 'yes' and 'no,' but you do not know which means which. The 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 god (though any god can be questioned more than once). Which three questions should you ask to determine which door leads to Heaven (you do not need to determine any other information).

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

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

The Sam and Polly Problem

Sam and Polly are perfectly logical mathematicians. A student walks in and says:

"I'm thinking of two numbers x and y, with 3 <= x <= y <= 97. I'll tell their sum to Sam, and their product to Polly."

She does so, then leaves, and the following conversation takes place:

Sam (to Polly): You can't know what x and y are.
Polly (to Sam): That was true, but now I do.
Sam (to Polly): Now I do too.

Find x and y. (I first heard this puzzle from Prof. Art Benjamin at Harvey Mudd College, and it took me the better part of Easter break to solve it.)

401 Circles

In a rectangle that's 2 by 200 units long, it's trivial to draw 400 non-overlapping unit-diameter circles.

But in the same rectangle, can you draw 401 circles? (non-overlapping, unit-diameter.)

Note that the usual approach to this type of problem (triangular stacking) only yields 399 circles.

"Eckenbrechen" (Chomp)

I will try to describe the game to the best of my abilities (English is not my native language).

Imagine a rectangular lattice a*b; a and b must be integers greater than 1. Two players take turns. When it is your turn, you choose and delete one box. Then, every box that is beneath the chosen box but not to the left and every box that is to the right but not above the chosen box will be deleted too. End of turn.

E.g.: This field, where x marks the chosen box:

□ □ □ □ □ □

□ □ x □ □ □

□ □ □ □

becomes this field:

□ □ □ □ □ □

□ □

□ □

Whoever has to take the last box loses.

1. Prove that you can win every rectangular field that is greater than 1*1 if you start, even against a perfect opponent. Holds this true if the field is a*infinity or infinity*infinity?

2. Can a field with exactly one row OR one column that is infinitely long be a losing position?

12 cubes

You have 11 cubes which are all exactly the same in every way; size, color, weight, texture, etc. There is an additional cube which is also exactly the same, except that it has a different weight from the rest (may be heavier OR lighter).

The only way you can measure the cubes is through a standard balance scale, which can hold any number of cubes on any side. In three measurements, can you identify the odd cube out, AND whether it is heavier or lighter?

Note: You can keep track of which cube is which between measurements. If it helps, assume that they're numbered 1-12, and that the numbering doesn't effect the weight.

Four fours

The task of this puzzle is to build terms that result in natural numbers using exactly four fours and any of these operations:

Operation Penalty Example
Composition 0 44
Brackets 0 (4+4)*4
Sum/Difference 1 4+4
Product/Quotient 2 4*4
Power/Square root 3 4^4, -/4
Factorial 4 4!

Example: 44 * (4 + 4) is a term for 352 with a total penalty of 3.

For each number from 0 to 100, find the term with the lowest penalty.

Addendum: If it is not possible to find a solution using only the operations above, you may also use some of these:

Operation Penalty
0.4 or 0.4... (= 0.4 period 4) 4
Floor/Ceil/Round/Percent 6
Any trigonometric function 8
ln x, log x , e^x 10

Sequence

what's the next number in the sequence: 1,1,2,720,? ( Of course you could interpolate any polinomial and any numbers could be, but there is an elgant solution out there, find it! )

Sequence b) (same task) 1, 11, 21, 1211, 111221, ?

God of Math

The god of math can do anything what you can ever do in any field ot mathematics. For example, he know the answer to the Riemann hypothesis, but he can't construct the set of every sets. He can form exactly 10 equilateral triangles with only 10 matches. How can he do it?


Burried Cable

An underground cable containing thousands of wires has been run between two buildings. None of the wires are labeled, and all of the wires look identical. Your job is to label the wires on each end such that each wire can be uniquely identified. You have a battery, a light bulb, a bunch of labels, and a marker. The wires in the cable are small enough that you can easily connect any number of wires by twisting the ends together. Without anyone to help you, what is the minimum number of trips you must make between buildings?

Note: You can only tell if the light bulb is on or off. There's no way to use the brightness of the bulb as a clever way of measuring resistance in the wire.

Hint: The answer does not depend on the number of wires in the cable (except for trivial cases like a cable with only one wire).

Diabetic Dilemma

You are with some friends at a pool party. Somebody brought a cooler filled with Coke and Diet Coke. You're diabetic, so you open the cooler to grab a Diet Coke when you discover that some prankster has torn the labels off all the bottles. Both are in identical plastic bottles, and as best as you can determine, the cola inside looks identical in every way. Without opening any of the bottles, how can you determine which bottles are filled with Diet Coke?

Note: This requires a bit of knowledge about soda, but there's a simple solution.


Chessboard

Consider an n times n chessboard with all the corners removed (it has nxn-4 places). For what values of n can you cover the board with "L" shaped dominoes? (they cover 4 places, and you can use the mirrored "L"-shaped domino too)


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.


Egg Problem

(From here but with new bonus features)
(original question asked during a software engineering job interview)
you have two eggs - dino eggs, very resiliant
they will absorb a certain amount of force with no negative consequences
but at some point they crack - if they don't crack, they are fine (no cumulative damage).

so you're on a 100 story building, you got 20 trials (you're allowed at most 20 individual egg drops) and 2 eggs,
is it possible to devise a testing algorithm that guarantees to tell you at exactly what floor the eggs will break (or that the eggs will survive from the top floor)?

drop your first egg and it doesnt break -> 19 trials, 2 eggs left
drop your first egg and it does break -> 19 trials, 1 eggs left

Bonus problems:
If you cannot handle 100 stories, how high can you go?
If your algorithm is successful for 100 stories, what is the maximum number of stories that you can test all floors?

I have two teams, one is given a third egg, but still only 20 trials. What is the minimum number of trials needed for a 2-egg team to cover the same number of stories.

If I kept the number of trials at 20, but kept offering you more eggs, at what point do you say "no thanks, more eggs won't let me test any higher".

If you want, you can substitute "inches" for "stories" to keep the puzzle under 6 miles. Feel free to ignore friction/terminal velocity.

Yet more prisoners

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.

Is there a strategy which will guarantee your release? If so, give one. If not, why not?

Robots on a number line

Two robots are parachuted onto a spot of a discrete number line that stretches infinitely in either direction. They are an unknown distance apart. Where they land, they drop their parachute. They begin executing the same set of instructions at the same time. Unfortunately, these are not very good robots, and they only understand commands in character form. There is only room for 10 instructions. Possible instructions are as follows:

  • L: Move left one space
  • R: Move right one space
  • S: Skip the next instruction if and only if there is a parachute at my feet
  • 0-9: Move to this position in the instructions (If the instructions are LRS1, the 1 would move the robot back to the 'R')

Every step takes the same amount of time to execute, including parachute skips and moving through the instructions. There is no variable storage. The robots begin executing from step 0. What set of instructions will result in the two robots ultimately finding each other on the infinite number line in every case? There are multiple possible answers.


Prisoner's Chess

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 squares in the chessboard. Then, one of the prisoners will go into the room. The warden will point to one of the squares, which is the magic square. This prisoner then must flip over 1 of the coins on the chessboard, and then he leaves. He can't skew or move any of the coins, just flip 0 or 1. The second prisoner will then come into the room, without ever seeing the board before the change. If he can correctly point out the magic square they will both go free. What is the strategy that the first prisoner should use to make sure they both go free?