Logic Puzzles

I started on this topic as part of my study on interview questions back when I was job hunting. Having puzzles like these in an interview is kind of controversial; I get them but rarely. If the interviewer is skilled, perhaps the challenge can tell him something about composure and communication skills. Generally I think it is a waste of time.

For fun, however, they can be thoroughly enjoying! They have fun and often surprising solutions, they make us pay attention to details and think in unconventional directions. Beyond that, I’ve been told, puzzles of various kinds can be beneficial in maintaining a good mental health as we age – that is assuming they don’t drive us crazy, of course!


Canonical logic puzzles

Let’s start of with some canonical classics each of which there are many variations. My versions will not be precisely the same as any originals and the archetypes I select for “canonical” will not necessarily be the chronologically first of their kind. Rather I will try to present reasonably compact forms that appeal to me.

(These puzzles may [or may not] be tricky in a mathematical sense, but they are not based on puns, ambiguities or wordplay. Natural language has limitations that make it near impossible to write completely unambiguous text, but I will do my best to write clearly. Most people will agree that there is a distinct and genuine solution to each puzzle below.)



p1. Prisoners and Hats:

Four criminals are arrested but the prison is currently full! The sadistic jailer presents them with the following “game”: Each is blindfolded and has a hat put on her – there are in total two red and two blue hats, a fact made known to them. One of the criminals is left in a holding cell while the three others have to go outside and line up with each facing the front of the line. As their blindfolds are removed, each woman can see the hats of the women in front of her but not her own nor anyone elses. The prisoner in the holding cell can neither see nor be seen by anyone.

The prisoners are not allowed to move, look around or communicate with each other. If any one of them, however, can figure out the color of her own hat they will all go free. If they fail, i.e. if anyone makes a wrong guess or breaks the rules, they will all be decapitated. How can the four women safely get out of this dilemma with their necks intact?


p2. Knights and Knaves:

It appears you have died and are making your way towards the afterlife. You come to a room from which there are two ways forward, represented by two doors; by each door there stands a guard. The rules appear to you in a vision: One door leads to heaven and one to hell. One guard is an angel who always tell the truth but one guard is a daemon who always lie. There is no telling which is which between either doors or guards – it may or may not be that the daemon is guarding the door to heaven. You are allowed to ask one of the guards any one question that can be answered with a “yes” or a “no”; upon hearing the answer you must choose and pass through one of the doors, and may never again come back. Failure to comply with the rules will land you in oblivion for eternity.

So how can you get into heaven?


p3. Pirates’ Treasure:

Five pirates with a strict hierarchy, #1 through #5 with #5 being the captain, have plundered a treasure of 1000 gold coins. Their peculiar custom is to let the captain suggest a division of the bounty and then let every pirate vote for or against the suggestion. If strictly more than half of the pirates vote “for”, the treasure will be divided as suggested but if not, the leader walks the plank. In the latter case, the second man in line (#4 after #5) then assumes the now vacant role of captain and the process starts over with one pirate less.

Assume that each pirate is very clever, completely rational and has the following priorities (in order): (i) to live, (ii) to get as much gold as possible, and (iii) to advance in rank. How will pirate #5 suggest to divide the 1000 gold coins?


p4. Caribbean Shipping:

Two hermits, let’s call them #1 and #2, live each on his own isolated little island in the Caribbean. One day #1 finds a beautiful diamond, which he decides to give to hermit #2 as a gift. Now although the islands are very remote, they both get periodic visits from a certain pirate ship. The captain, if asked, will gladly undertake to deliver any message or object from one island to the other. The pirates are not altogether unfriendly as a group, but being what they are you can be assured that there’s always some in the crew who will instantly steal any small objects they can get their hands on. Hermit #1 would like to send the diamond to hermit #2, but of course it is out of the question that either of them should leave his respective island.

Each of the Hermits has at his disposal a large sturdy chest, which would certainly not be stolen. Furthermore they each have a padlock and with each padlock a unique key. If something is put in a chest, the chest is locked with a padlock and sent, then both chest, lock and contents will arrive safely to their destination. But if anything else, key, padlock or diamond, is sent without being locked in or onto a chest, it will assuredly vanish among the scoundrels in the crew. How can hermit #1 and #2 arrange it so that the diamond is sent (and accessible) from #1 to #2?


p5. Dropping Eggs

You are presented with two strange looking eggs and a 100 story building. You are told that the eggs are completely identical, but the material and composition of them is unknown. We need to know precisely from which floors of the 100 story building such eggs may be dropped without breaking them. You may assume that there is no randomness or degradation going on, so eggs of this type dropped from a floor x, will either always break or always survive completely unscathed. A broken egg is useless, but if you drop an egg once and it survives then you may drop it again and so on until you do break it. Obviously if an egg survives a drop from floor x it would survive a drop from any lower floor and, conversely, if it breaks when dropped from floor x it could certainly not survive being dropped from a higher floor.

You may break one or both eggs, but once the last egg is broken you must be sure to know precisely from which floors it is safe to drop such eggs and from which floors it is not. A simple minded strategy could be to use only one egg; try the first floor then the second floor and so on until finally the egg breaks. But this could require as much as 100 tries! Since you have two eggs at your disposal, is there perhaps another strategy that can always find the answer in less tries… What is the smallest number of tries we could always be sure to finish in???

(A common version of this problem asks how to do it with at the most 20 tries, you are welcome to solve this first. According to my calculations, however, you can do quite a bit better – but you have to be pretty focused to show that the optimal strategy is optimal, I think!)


p6. The Counterfeit Coin:

An honest merchant has managed to collect 12 gold coins over the day. But woe, one of the customers returns and explains that he thinks he may unwittingly have given the merchant a fake coin! All the real coins must contain precisely the same amount of gold, and thus weight exactly equal but the fake coin might be different… The merchant, as good merchants will, has at his disposal a beam balance scale of the classical type where you put objects on either end and observe which side will sink and which will rise.

Suppose that among the 12, there is exactly one counterfeit coin which is either distinctly heavier or distinctly lighter than a genuine one. Explain to the two men how they can identify the counterfeit coin in only three weightings!

(Assume that they have no other coins than the 12 available. However if you wish, you may also solve the problem while assuming that there are additional coins, both real and known counterfeit – I believe the difficulty of the puzzle is not greatly affected either way.)


p7. Crossing a Narrow Bridge:

Four comrades, let’s call them #1, #2, #3 and #4 are out hiking a dark rugged night. They come to deep ravine over which there is only one way to cross: A rickety suspension bridge. They would normally have crossed it one person at a time, but bad fortune has it that there is only a single working flash light left! Crossing without a flash light is out of the question, but under the circumstances the comrades decide they can risk crossing up to two people at a time. Comrade #1 is young and fast and can easily cross the bridge in one minute. #2 can do it in two minutes but #3 needs five minutes, and #4 being somewhat elderly, requires a full ten minutes. Two comrades crossing together must of course move at the pace of the slower.

What is the shortest possible time until they can all have crossed and appear together, safe, on the far side?



Variations

By a variation I don’t mean an obviously equivalent puzzle using, say, different objects but the same set-up. Rather I will here give puzzles where the logical mechanisms seem quite similar, but have something added, are compounded or just subtly different.

(To be written later…)



Quickies

q1. In a plane (on a plane piece of paper) draw seven distinct points arranged in such a way that out of any triplet of points I can choose, at least a pair in the triplet will be exactly one centimeter apart.

q2. You have a string that is guaranteed to burn from one end to the other in exactly six minutes but at a completely unpredictable rate (one centimeter may burn much faster than the next centimeter etc.). Using only this string and a lighter, how can you measure out exactly three minutes?

q3. I value honesty above all else, and I say you can be sure of the following: I have coins of gold, coins of silver and coins of bronze; you may make one statement and if it is true, I will give you a coin. How can you get a gold coin from me?

q4. You have only a five liter bowl and a three liter bowl, but an unlimited access to water; how can you measure out exactly 4 liters?

q5. A man ran a mile south, then a mile west, then a mile north and lo, he was back where he had started! Where on earth was he?  (Actually there are more than two answers, the follow-up challenge is to explain superficially why/which and how many.)



References

Some of these puzzles I got from friends, but in writing this page I have also scoured the Internet to find interesting formulations and double check my solutions. Though not an exhaustive list, here are a few links that deserve a mention:

Wikipedia: http://en.wikipedia.org/wiki/Category:Logic_puzzles

P. S. Thomas: http://psthomas.com/LogicPuzzles.html

Brainden: http://brainden.com/logic-problems.htm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: