A compendium of conundrums

Link post

Logic puzzles

None of the puz­zles be­low have trick an­swers—they can all be solved us­ing logic and a bit of maths. When­ever a group of peo­ple need to achieve a task, as­sume they’re al­lowed to con­fer and come up with a strat­egy be­fore­hand. They’re listed roughly in or­der of difficulty. Let me know of any other good ones you find!

Two ropes

I have two ropes which each, if lighted at one end, takes 1 hour to burn all the way to the other end. How­ever, they burn at vari­able rates (e.g. the first might take 55 min­utes to burn 14 of the way, then 5 min­utes to burn all the rest; the sec­ond might be the op­po­site). How do I use them to time 45 min­utes?

25 horses

I have 25 horses, and am try­ing to find the 3 fastest. I have no timer, but can race 5 at a time against each other; I know that a faster horse will always beat a slower horse. How many races do I need to find the 3 fastest, in or­der?

Monty hall prob­lem (ex­pla­na­tion taken from here)

The set of Monty Hall’s game show Let’s Make a Deal has three closed doors. Be­hind one of these doors is a car; be­hind the other two are goats. The con­tes­tant does not know where the car is, but Monty Hall does. The con­tes­tant picks a door and Monty opens one of the re­main­ing doors, one he knows doesn’t hide the car. If the con­tes­tant has already cho­sen the cor­rect door, Monty is equally likely to open ei­ther of the two re­main­ing doors. After Monty has shown a goat be­hind the door that he opens, the con­tes­tant is always given the op­tion to switch doors. Is it ad­van­ta­geous to do so, or dis­ad­van­ta­geous, or does it make no differ­ence?

Four-way duel

A, B, C and D are in a duel. In turn (start­ing with A) they each choose one per­son to shoot at, un­til all but one have been elimi­nated. They hit their cho­sen tar­get 0%, 33%, 66% and 100% of the time, re­spec­tively. A goes first, and of course misses. It’s now B’s turn. Who should B aim at, to max­imise their prob­a­bil­ity of win­ning?

Duck in pond

A duck is in a cir­cu­lar pond with a men­ac­ing cat out­side. The cat runs four times as fast as the duck can swim, and always runs around the edge of the pond in whichever di­rec­tion will bring it clos­est to the duck, but can­not en­ter the wa­ter. As soon as the duck reaches the shore it can fly away, un­less the cat is already right there. Can the duck es­cape?

Non-tran­si­tive dice

Say that a die A beats an­other die B if, when both rol­led, the num­ber on A is greater than the num­ber on B more than 50% of the time. Is it pos­si­ble to de­sign three dice A, B and C such that A beats B, B beats C and C beats A?

Wine tasting

A king has 100 bot­tles of wine, ex­actly one of which is poi­soned. He de­cides to figure out which it is by feed­ing the wines to some of his ser­vants, and see­ing which ones drop dead. He wants to find out be­fore the poi­soner has a chance to get away, and so he doesn’t have enough time to do this se­quen­tially—in­stead he plans to give each ser­vant some com­bi­na­tion of the wines tonight, and see which are still al­ive to­mor­row morn­ing.

a) How many ser­vants does he need?

b) Sup­pose he had 100 ser­vants—then how many wines could he test?

Crawl­ing on the planet’s face

Two peo­ple are dropped at ran­dom places on a fea­ture­less spher­i­cal planet (by fea­ture­less I also mean that there are no priv­ileged lo­ca­tions like poles). As­sume that each per­son can leave mes­sages which the other might stum­ble across if they come close enough (within a cer­tain fixed dis­tance).

a) How can they find each other for cer­tain?

b) How can they find each other in an amount of time which scales lin­early with the planet’s ra­dius?

Drop­ping coconuts

I have two iden­ti­cal co­conuts, and am in a 100-floor build­ing; I want to figure out the high­est floor I can drop them from with­out them break­ing. As­sume that the co­conuts aren’t dam­aged at all by re­peated drops from be­low that floor—but once one is bro­ken, I can’t use it again.

a) What’s the small­est num­ber of drops I need, in the worst case, to figure that out?

b) Can you figure out an equa­tion for the gen­eral case, in terms of num­ber of co­conuts and num­ber of floors?

Pirate treasure

There are 5 pirates di­vid­ing up 100 gold coins in the fol­low­ing man­ner. The most se­nior pirate pro­poses a di­vi­sion (e.g. “99 for me, 1 for the next pirate, none for the rest of you”). All pirates then vote on this di­vi­sion. If a ma­jor­ity vote no, then the most se­nior pirate is thrown over­board, and the next most se­nior pirate pro­poses a di­vi­sion. Other­wise (in­clud­ing in the case of ties) the coins are split up as pro­posed. Each pirate’s pri­ori­ties are firstly to stay al­ive, sec­ondly to get as much gold as pos­si­ble, and thirdly to throw as many other pirates over­board as pos­si­ble (they only pay at­ten­tion to later pri­ori­ties when all ear­lier pri­ori­ties are tied). They have com­mon knowl­edge of each other’s perfect ra­tio­nal­ity.

a) What will the most se­nior pirate pro­pose?

b) What about if there are 205 pirates?

c) Can you figure out a solu­tion for the gen­eral case, in terms of num­ber of coins and num­ber of pirates?

Self-sorting

There are n peo­ple, all wear­ing black or white hats. Each can see ev­ery­one else’s hat colour, but not their own. They have to sort them­selves into a line with all the white hats on one end and all the black hats on the other, but are not al­lowed to com­mu­ni­cate about hat colours in any way. How can they do it?

Knights and knaves

You are trav­el­ling along a road and come to a fork, where a guardian stands in front of each path. A sign tells you that one guardian only speaks the truth, and one only speaks lies; also, one road goes to Heaven, and ones goes to Hell. You are able to ask yes/​no ques­tions (each di­rected to only one of the guardians) to figure out which is which.

a) Can you figure it out us­ing two ques­tions?

b) How about one?

What is the name of this god? (ex­pla­na­tion taken from here)

Three gods A, B, and C are called, in no par­tic­u­lar or­der, True, False, and Ran­dom. True always speaks truly, False always speaks falsely, but whether Ran­dom speaks truly or falsely is a com­pletely ran­dom mat­ter. Your task is to de­ter­mine the iden­tities of A, B, and C by ask­ing three yes/​no ques­tions; each ques­tion must be put to ex­actly one god. The gods un­der­stand English, but will an­swer all ques­tions in their own lan­guage, in which the words for yes and no are da and ja, in some or­der. You do not know which word means which.

A game of greed

You have a pile of n chips, and play the fol­low­ing two-player game. The first player takes some chips, but not all of them. After that play­ers al­ter­nate tak­ing chips; the only rule is that you can­not take more than the pre­vi­ous player did. The per­son who takes the last chip wins. Is it the first player or the sec­ond player who has a win­ning strat­egy, and what is it?

Heat-seek­ing missiles

Four heat-seek­ing mis­siles are placed at the cor­ners of a square with side length 1. Each of them flies di­rectly to­wards the mis­sile on its left at a con­stant speed. How far does each travel be­fore col­li­sion? (As­sume they’re ideal points which only “col­lide” when right on top of each other).

Blind maze

You’re lo­cated within a finite square maze. You do not know how large it is, where you are, or where the walls or exit are. At each step you can move left, right, up or down; if there’s a wall in the given di­rec­tion, then you don’t go any­where (but you don’t get any feed­back tel­ling you that you bumped into it). Is there a se­quence of steps you can take to en­sure that you will even­tu­ally find the exit?

Hats in lines

There are 100 pris­on­ers in a line, fac­ing for­wards. Each is wear­ing a black or white hat, and can see the hat colour of ev­ery­one in front of them, but not their own or that of any­one be­hind them; also, they don’t know the to­tal num­ber of hats of each colour. Start­ing from the back of the line, each per­son is al­lowed to say ei­ther “black” or “white”, and is set free if they cor­rectly say the colour of their hat, but shot oth­er­wise. Every­one in the line can hear ev­ery an­swer, and whether or not they were shot af­ter­wards.

a) How many peo­ple can be saved for cer­tain, and us­ing what strat­egy?

b) (Very difficult, re­quires the ax­iom of choice). Sup­pose that the num­ber of pris­on­ers is countably in­finite (i.e. in cor­re­spon­dence with the nat­u­ral num­bers, with num­ber 1 be­ing at the back). How can they save all but one?

c) Sup­pose that the num­ber of pris­on­ers is countably in­finite, and none of them can hear the an­swers of the other pris­on­ers. How can they save all but finitely many?

Pri­son­ers and hats

Seven pris­on­ers are given the chance to be set free to­mor­row. An ex­e­cu­tioner will put a hat on each pris­oner’s head. Each hat can be one of the seven col­ors of the rain­bow and the hat col­ors are as­signed com­pletely at the ex­e­cu­tioner’s dis­cre­tion. Every pris­oner can see the hat col­ors of the other six pris­on­ers, but not his own. They can­not com­mu­ni­cate with oth­ers in any form, or else they are im­me­di­ately ex­e­cuted. Then each pris­oner writes down his guess of his own hat color. If at least one pris­oner cor­rectly guesses the color of his hat, they all will be set free im­me­di­ately; oth­er­wise they will be ex­e­cuted. Is there a strat­egy that they can use which guaran­tees that they will be set free?

Pri­son­ers and switch

There are 100 im­mor­tal pris­on­ers in soli­tary con­fine­ment, whose war­den de­cides to play a game with them. Each day, one will be cho­sen at ran­dom and taken into an empty room with a switch on the wall. The switch can be in the up po­si­tion or the down po­si­tion, but isn’t con­nected to any­thing. The pris­oner is al­lowed to change the switch po­si­tion if they want, and is then taken back to their cell; the switch will then re­mained un­changed un­til the next pris­oner comes in. The other pris­on­ers don’t know who is cho­sen each day, and can­not com­mu­ni­cate in any other way.

At any point, any pris­oner can de­clare to the war­den “I know that ev­ery sin­gle pris­oner has been in this room already”. If they are cor­rect, all the pris­on­ers will be set free; if not, they will all be ex­e­cuted.

a) What’s a strat­egy that’s guaran­teed to work?

b) Does it still work if the war­den is al­lowed to take pris­on­ers into the room as of­ten as he wants, with­out the other pris­on­ers know­ing? If not, find one that does.

Pri­son­ers and boxes

Another 100 pris­on­ers are in an­other game. They are each given a piece of pa­per on which they can write what­ever they like. The pa­pers are then taken by the war­den, shuffled, and placed into boxes la­bel­led 1 to 100 (one per box). One by one, each pris­oner will be taken into the room with the boxes, and must find their own piece of pa­per by open­ing at most 50 boxes. If they do so, they’re set free. To make things eas­ier for them, be­fore any­one else goes in­side, the war­den al­lows one pris­oner to look in­side all the boxes and, if they choose, to swap the con­tents of any two boxes (the other pris­on­ers aren’t al­lowed to move any­thing). Find the strat­egy which saves the great­est num­ber of pris­on­ers for cer­tain.

Blue eyes (ex­pla­na­tion taken from here)

A group of peo­ple with as­sorted eye col­ors live on an is­land. They are all perfect lo­gi­ci­ans—if a con­clu­sion can be log­i­cally de­duced, they will do it in­stantly. No one knows the color of their own eyes. Every night at mid­night, a ferry stops at the is­land. Any is­lan­ders who have figured out the color of their own eyes then leave the is­land, and the rest stay. Every­one can see ev­ery­one else at all times and keeps a count of the num­ber of peo­ple they see with each eye color (ex­clud­ing them­selves), but they can­not oth­er­wise com­mu­ni­cate. Every­one on the is­land knows all the rules in this para­graph.

On this is­land there are 100 blue-eyed peo­ple, 100 brown-eyed peo­ple, and the Guru (she hap­pens to have green eyes). So any given blue-eyed per­son can see 100 peo­ple with brown eyes and 99 peo­ple with blue eyes (and one with green), but that does not tell him his own eye color; as far as he knows the to­tals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes.

The Guru is al­lowed to speak once (let’s say at noon), on one day in all their end­less years on the is­land. Stand­ing be­fore the is­lan­ders, she says the fol­low­ing:

“I can see some­one who has blue eyes.”

Who leaves the is­land, and on what night?

Quine

Can you write a quine: a pro­gram that, when ex­e­cuted, prints its own source code?

Cheat­ing on a string the­ory exam (puz­zle taken from here)

You have to take a 90-minute string the­ory exam con­sist­ing of 23 true-false ques­tions, but un­for­tu­nately you know ab­solutely noth­ing about the sub­ject. You have a friend who will be writ­ing the exam at the same time as you, is able to an­swer all of the ques­tions in a frac­tion of the al­lot­ted time, and is will­ing to help you cheat — but the proc­tors are alert and will throw you out if they sus­pect him of com­mu­ni­cat­ing any in­for­ma­tion to you. You and your friend have watches which are syn­chro­nized to the sec­ond, and the proc­tors are used to him of­ten finish­ing ex­ams quickly and won’t be sus­pi­cious if he leaves early.

a) What is the largest value N such that you can guaran­tee that you an­swer at least N out of the 23 ques­tions cor­rectly?

b) (Easier). The ob­vi­ous an­swer is 12, but in fact you can do bet­ter than that, even though it seems like 12 is the in­for­ma­tion-the­o­retic limit. How come?

The hy­dra game (ex­pla­na­tion taken from here)

A hy­dra is a finite tree, with a root at the bot­tom. The ob­ject of the game is to cut down the hy­dra to its root. At each step, you can cut off one of the heads, af­ter which the hy­dra grows new heads ac­cord­ing to the fol­low­ing rules:

  • If you cut off a head grow­ing out of the root, the hy­dra does not grow any new heads.

  • Other­wise, re­move that head and then make n copies of its grand­father sub­tree (as in the di­a­gram be­low), where n is the num­ber of the step you’re on

What strat­egy can you use to even­tu­ally kill the hy­dra?

Phys­i­cal puzzles

Balanc­ing nails

Pic­ture a nail ham­mered ver­ti­cally into the floor (with most of it still stick­ing out). You’re try­ing to bal­ance as many other nails on it as you can, such that none of them touch the ground. How do you do so?

Hang­ing pictures

Con­sider a pic­ture hang­ing by a string draped over some nails in the wall, in a way such that if any sin­gle nail is re­moved, the pic­ture will fall to the ground.

a) Is it pos­si­ble for 2 nails?

b) How about n nails?

Two-piece pyramid

Con­sider the two iden­ti­cal shapes shown be­low. Each has two planes of sym­me­try, and a square base. Is it pos­si­ble to put them to­gether to cre­ate a reg­u­lar pyra­mid? (For a fun dis­cus­sion of this prob­lem in the con­text of ma­chine learn­ing, see a few min­utes into this video).

Plane on a treadmill

Sup­pose that a plane were on a gi­gan­tic tread­mill, which was pro­grammed to roll back­wards just as fast as the plane was mov­ing for­wards. Could the plane ever take off?

Pen­nies game

Two play­ers take turns to place pen­nies flat on a cir­cu­lar table. The first one who can’t place a penny loses. Is it the first or the sec­ond player who has a win­ning strat­egy?

Join­ing chains

You have four chains, each con­sist­ing of three rings. You’re able to cut in­di­vi­d­ual rings open and later weld them closed again. How many cuts do you need to make to form one twelve-ring bracelet?

Go­ing postal

Alice and Bob live far apart, but are get­ting mar­ried and want to send each other en­gage­ment rings. How­ever, they live in Rus­sia, where all valuable items sent by post are stolen un­less they’re in a locked box. They each have boxes and locks, but no key for the other per­son’s lock. How do they get the rings to each other?

Nine dots puzzle

Without lift­ing your pen from the pa­per, draw four straight lines that go through the cen­tres of all 9 dots.

Mu­tilated chessboard

Con­sider a chess­board miss­ing two di­ag­o­nally op­po­site cor­ner squares. Is it pos­si­ble to cover all the re­main­ing squares with dom­inos (where each dom­ino cov­ers two ad­ja­cent squares)?

Safe sex

Sup­pose a man wants to have safe sex with three women, but only has two con­doms. How can he do so, while en­sur­ing that no STD is passed from any­one to any­one else?

Wristcuffs

Two peo­ple are tied to­gether as in the fol­low­ing di­a­gram. Without be­ing able to undo or cut the ropes, how can they get free?

No nominations.
No reviews.