Riddles
Liars and Truthtellers
Better known as Knights and Knaves in the works of Raymond Smullyan, this page has an exhaustive writeup on how these types of puzzles work and has a few devious examples at the end.
Weighing Gold Coins
You've been informed that a counterfeiter slipped a fake coin into a pile of genuine gold coins. You know that the metal the fake coin is made from is significantly lighter than gold, so you decide use a set of balancing scales to track down the offending coin. There are only 27 coins total, so you figure that you could weigh one coin against another 26 times until you find the light one, but since you can stack coins on both sides of the scale, you figure it makes more sense to weigh a bunch at a time.
You could start by weighing five coins against five, and if one side comes up light, you know the coin is part of that five. Find a way to find the coin you want in just three weighings.
As a bit of an intellectual exercise, you could also figure out how many weighings it would take for an arbitrarily sized pile of coins.
Weighing Gold Coins Revisited
Your skills at counterfeit detection are called upon again, as a pile of 12 gold coins has a phony in it somewhere. You know that this coin is either significantly heavier or lighter than gold-but you're not sure which. Your job this time is to figure out which coin is light or heavy in only three weighings.
Poison problem
An assassin was discovered slipping a dangerous poison into one of the king's barrels of wine, but unfortunately, after he was captured, no one could remember which barrel he had been poisoning.
It's known that the poison is a slow acting one, which kills its victims within a week, and there are thirty possible barrels which might contain the poison. The king, eager to restore his wine supply, has decided that the poisons should be tested out on the 5 prisoners arrested in connection with the incident.
Your job is to figure out the best way to test all 30 barrels of wine by giving samples of them to the prisoners and observing the results. For example, you could give each of the prisoners a sample of one of the first five wines, wait a week to see the results, and give them the next 5 wines and so on, but that could take 6 weeks to do in the worst case.
It shouldn't take you too long to figure out a way to do it in three weeks. From there it's not too much harder to figure out how to do it in two. And if you're really smart, you might be able to get the entire job done in the space of one week.
The only question is, how?
One Thousand Greedy Pirates
A thousand pirates just stumbled across an enormous horde of treasure
and need to decide how to split it between them. There's some dispute
over whether they should split the treasure evenly or split it among
the higher ranking pirates.
To resolve this dispute, the pirates all agree to have a vote each day
until the issue is resolved. Each day, they'll vote on whether to
split the treasure evenly, or whether to kill off the lowest ranking
pirate. They'll repeat this process until at least half of the
remaining pirates vote to split the treasure.
All the pirates are perfect mathematical geniuses, and they're all
incredibly greedy too, they want as much of the treasure as possible
while still saving their own necks.
So the question you need to figure out, is at what point will the
pirates agree to split the treasure, and what will the vote be?
Just a few hints, the answer is not that they would split the treasure
when there's only one or two pirates left. The 999 pirates ranked
above that guy would never let that happen, and would never vote to
kill a pirate if it would lead to their own death.
And the answer is not that it would split immediately either, with
1000 pirates remaining. The top ranking pirate is obviously never
going to agree to split the treasure since he has nothing to lose, and
if you're pirate number 300 or something, you'll want to kill off a
lot of the other pirates before you get worried about yourself.
So the question is to find the logical point at which the treasure
would split, assuming they're all logical pirates.
And if you're really feeling masochistic, resolve the problem for what
would happen if the treasure was split, not if there was 50% or more
of the pirates who agreed, but a simple majority of pirates who agreed.
Greedy Pirates, now with wenches!
Five pirates come across a forgotten and cursed treasure horde... a pile of 100 wenches!
The pirates began to debate who should take what share of the treasure, and they decide to settle it democratically. Each pirate in turn will be allowed to make a proposal to each of the other pirates as to how many of the wenches each pirate should be entitled to. If the proposal is accepted by a majority of the pirates, that distribution is made. If it is rejected, the pirate who made the proposal has to walk the plank and the next pirate makes a proposal.
So for example, the first and second pirates who make a proposal need two other pirates to accept their proposal, whereas the third and fourth pirates need one other pirate.
For example, the first pirate may offer the second and third pirate 33 wenches each while keeping 34 for himself, in the hopes that they wouldn't expect to get a better offer later and that those two would be enough to have a majority.
Assuming that these pirates are all perfectly logical (and greedy) fellows, what offer should the first pirate make?
Monks -red/blue eyes
There is an island filled with monks, some of whom have brown eyes,
and some of whom have red eyes. All the red-eyed monks are cursed, so
that if they ever able to discover that they have red eyes, they have
to kill themselves on midnight of the day on which they discover that
fact.
To avoid this taking place, all the monks vow never to tell another
monk his eye color, and they keep all reflective surfaces and mirrors
from the island so no monk can ever find out his own eye color.
However, each monk can see the eye color of every other monk.
For example, if you were a monk on this island, you might know that
there were 15 brown eyed monks, and 8 red eyed monks or something
similar, but you wouldn't know your own eye color, and you'd never
have any occassion to find out since no one would be allowed to
discuss eye color, so you'd be safe. However, if someone ever told you
that you had red eyes, and you knew they were telling the truth, you'd
have to kill yourself at midnight.
Suppose a stranger came to this island who knew none of the above
facts, but who happened to find all the monks gathered together and
commented on their eye color. Suppose also that all monks knew that
this person was telling the truth. What would happen if that person
said each of the following statements:
A. "Exactly 12 of you have red eyes."
B. "An even number of you have brown eyes"
C. "The number of brown eyed and red-eyed monks together is 26."
D. "At least one of you has red eyes."
Keep in mind the result of what happens may be all the red eyed monks
killing themselves at the end of the day, at the end of some number of
days, or not at all.
Also keep in mind that all the monks are perfectly logical and that if any
of them are capable of figuring out what their eye color is, they
would do so.
James/John- three words
One lies, one doesn't, find out who's who and who lies.
There are two identical twin brothers, one of whom is named James, the other one is named John. Also, one of them always lies, and one of them always tells the truth, but you don't know which one is which.
You run into one of the brothers on the street one day, and you want to find out whether he is John or James. The problem is, you don't know whether the brother you see is a liar or not, and you don't know whether John or James is the liar.
Your problem is to come up with a three word question which, if posed to either of the brothers regardless of who lies, will let you know for sure if the person you asked it of was John. So you want to figure out a three word question that will let you know whether the person who answers is John or not. How do you do it?
Suppose instead you run into one of the brothers, not knowing which one, and you decide that you want to figure out whether John is the one who always lies or James is the one who always lies. How could you
find the answer to that with one three word question, which will work no matter what?
The Dragon and the Seven Wells
On a certain mountain, there are seven enchanted wells. Each well is numbered so that each well is higher in number and elevation than the last one, making well one the lowest well, well two the next lowest, and well seven the highest. The wells are also enchanted so that if you drink water from any well, you'll be poisoned and can only be cured by drinking water from some higher well. For example, if you drink water from well three you'll be poisoned, but if you go on to drink some water from well four or above, you'll no longer be poisoned.
A knight and a dragon both live on this mountain and they decide that the mountain ain't big enough for the two of them. So they agree to have a duel of sorts, they're each going to bring the other party a goblet full of water, which the other person will have to drink, then they'll go their separate ways and see who lives.
The dragon readily agrees to this since he knows that because he can fly, he's the only one of the pair who can reach well seven, which is the highest well, so he's convinced he can give the knight a poison which he won't be able to cure, and he'll be able to cure anything the knight throws at him.
The dragon and the knight both bring each other a goblet of water, and they both drink the goblet the other person brought. Neither party cheats, and they both have to drink what the other person prepared for them. They then go their separate ways to drink from the wells or do whatever they feel is neccessary, although they can't vomit up the poison or anything similar.
However, even though the knight can only reach the lowest six wells, and only the dragon can reach the seventh well, the knihgt still manages to live, and the dragon dies. How?
Essentially, how could the knight guarantee that he would live no matter what the dragon brought him?
Two blue hats, three red
You're at a job interview with two other people. Your prospective boss
shows you a box containing two blue hats and three red hats. He tells
you that he's going to put a hat on each of your heads, and you'll be
able to see the color of the hats on the other people's heads, but not
your own.
He places a hat on each of your heads. The first candidate looks
around, and says flatly that he can't figure out the color of the hat
on his head. The second candidate looks around and says the same
thing. You look around and you see two red hats.
Based upon this, you can figure out the color of the hat on your own
head beyond a shadow of a doubt. Assume the other candidates are
logical and would have been able to figure out the color of their own
hat if it were possible to do so. How can you do so?
Not only that, but you would have been able to figure out your own hat
color without ever looking around, just based upon what the other two
said. How?
A line of hats, arbitrarily long
A group of gentlemen are all standing in a line wearing red and blue hats. None of the gentlemen are allowed to see the color of their own hats, but they can see the color of everyone in front of them. Starting with the person at the very back of the line, who can see the hats of everyone in front of him, they are required to guess the color of their own hat. What strategy should they use to see that the most number of them get it correct?
Four hats
Four hats are placed onto the heads of four gentlemen. Each of them can see the hats of the other gentlemen, but not their own, and each of them know that the hats are colored red, white, and blue, with one color appearing twice. The four of them, from the first person to the fourth, are all able to figure out their own hat color. How, and which pair had the same color?
And just for fun, you can prove that no matter how the hats are put on everyone's heads, at most one person will be unable to deduce his hat color.
Three missionaries/three natives
Similar to this game, only a bit simpler. Three missionaries and three natives need to cross a river, using a boat that can only carry two of them at a time. The catch is that the natives can never be allowed to outnumber the missionaries on either side of the river, or the natives will overpower the missionaries and do unspeakable things to them; however, the missionaries can leave the natives alone on one side of the river.
Only the three missionaries and one of the natives are able to row the boat. Knowing all this how can you get all the missionaries and natives across?
1000 cells
A jailer is guarding over a thousand cells, but he gets bored one night and decides to play a little game. He starts out by going past every cell and flipping its lock. Then he starts over, and flips the lock on every other cell. Then he starts over again and flips the lock on every third cell, every fourth cell, and so on until he does it for every 1000th cell.
Assuming that all the cells start out locked, can you find 5 cells above 700 that will be unlocked at the end of the night?
Alice, Bob, Charlie: keys and locks
Alice and Bob both like sending each other packages in the mail, but their nosy neighbor Charlie likes sneaking into their mailboxes and opening all their packages if he can. To get around this Alice and Bob have a large number of locks and keys they can put on their packages.
Bob wants to send Alice a personal note without Charlie having the chance to read it. He can put any number of locks around the package, but Alice doesn't have any of his keys, and he has no way to get anything to her without sending it through the mail. What can Bob do to ensure that she gets it?
The LightBulb Problem
You are one of a hundred prisoners who are about to be thrown in jail for life. However, you have one escape clause: there's a single cell in the dungeon you will be held in which has a light switch and a bulb in it. The prisoners will be rotated between the cells randomly. If one of you goes to the warden and claims that you have all been in the cell with the light bulb before, you'll all be killed if that person was wrong, and you'll all be freed if that person was right.
Unfortunately, once you're thrown in prison, you'll have no way to communicate with each other. The cells are all scrubbed and washed clean to remove any identifying marks or scratches you might try to leave, and you can't communicate across cells, and no one can
see inside anyone else's cell. The one thing you do know is that in the one cell with the lightbulb has a special provision. If a prisoner leaves the light switch on, it will remain on until another prisoner turns it off. And if a prisoner leaves it off, it will remain that way until another prisoner flips it.
In other words, the prisoners can communicate by leaving the light switch in the one room either on or off. Only they can touch the switch, but whenever any prisoner enters the room all he knows is whether the switch is currently on or off.
Knowing all this, you and all the other prisoners work out a system which guarantees that you will get out eventually, and has no chance of failure.
You can assume the light switch is off to begin with, and leaving the switch on or off for the next prisoner to see is the only way you have to communicate, you can't unscrew the bulb, measure how warm it is, or
turn it on partway or anything similar. Keep in mind all anyone knows when they enter the room is whether the switch is currently on or off, they have no way of knowing what happened before.
How do you do it? Incidentally, this problem can basically work the same if you only have three prisoners.
As an extra bonus, suppose you find out that the one cell you need to all have visited has 7 light switches and bulbs in it. You and the other prisoners are able to work out a method which guarantees that
you will be able to go free as soon as all of you have been in the one room, and you won't have to wait any longer then absolutely necessary, unlike the other method. How would you do it?
Simple Games
Basic two player games that are puzzle-like in nature. These are all fairly obscure/technical, I remember them since they're interesting puzzles, not because any of them would be any good to play.
Take 1 to 4 pennies
Start out with a pile of twenty-one pennies, each player takes turns taking away 1 to 4 pennies. Whoever takes the last penny loses. What strategy should you use, and should you go first or second?
5 rows, take any number of sticks
A more complex game that still has an optimal strategy, consider the following rows of sticks:
| |
| | | |
| | | | | |
Your goal is to avoid taking the last stick. The rule is that you can take any number of sticks from any individual row, and you always have to take at least one stick. For example, you can take all the sticks on the second row, two of the sticks on the second row, one of the sticks on the third row, etc.
Take turns picking numbers from 1 to 9
From the following set of numbers:
1, 2, 3, 4, 5, 6, 7, 8, 9
Both players take turns picking a number that hasn't been picked yet. The goal is to have picked three numbers that add up to 15. This one's worth mentioning just because it happens to be equivalent to a game of tic-tac-toe.
Paradoxes/Puzzlers
Two boxes, foreknowledge
| $10,000
|
|
$100,000 |
Unexpected Drill
An officer in the military announces that there will be a surprise drill at some point during the next week, such that no one will be able to know for sure when it takes place. The privates all discuss this with themselves, and reach the conclusion that the drill can never take place.
Their reasoning:
The drill can't take place on the last day of the week, Saturday, since at that point there's only one possibility for what day the drill could be on, and it wouldn't be a surprise at that point.
The drill also can't take place on Friday, since if you reach Friday and the drill hasn't taken place yet, you know they can't have it on Saturday so they've have to do it then.
Similarly, the drill can't take place on Thursday since we've already established it can't happen at a later date, which would leave only one possibility.
And similarly, the drill can't happen on Sunday, thus meaning it can't happen at all.
Does their logic make sense at all?
This statement is impossible to prove true
Is that statement true or false? Or is it a paradox, which would of course make it true.