This is a linkpost for http://thinkingcomplete.blogspot.com/2018/09/a-compendium-of-conundrums.html
Two-piece pyramid: This is a puzzle? A funner version is to have three of those pieces — actual, physical pieces — and show someone a pyramid made from two of them. They should be made accurately enough that you can't see the join. Then sweep the pyramid apart while releasing the third piece palmed in your hand and challenge the other person to make it again.
I recognize some of these from my math competition days. Fun stuff!
But I’ve always felt somewhat unsatisfied/annoyed at certain sorts of such problems. I’ll refrain from commenting on the “real” (i.e., expected by the problem-writers) solutions, but here are some “joke” solutions, which express my views on this matter in an oblique way…
Safe sex
The definition of what constitutes “sex” has changed! Penetrative intercourse is not the only sex act that is, among the enlightened, accepted as constituting “sex”. Therefore, to solve this problem, let the man engage in a mutually satisfactory non-penetrative sex act of his choice with each woman. This requires the use of zero condoms, and avoids STD transmission.
Wristcuffs
It is not unheard of for people who find that they are immobilized by a trapped limb to sever that limb in exchange for freedom. Such a remedy will suit the two people in this problem. Note that out of the four extremities involved, only one must be severed in order to free both individuals (and the choice of hand is entirely arbitrary).
Going postal
Despite invoking the infamously-unreliable Russian postal service to construct the scenario, the author of this problem displays a sadly insufficient degree of pessimism about said institution’s performance and sanity. The problem relies on the presumptive fact that while a ring sent by Russian post will get stolen en route (true), a lockbox sent by Russian post will be delivered intact (false).
Sent by Russian post, a box will be stolen. A key will be stolen. A locked box will be pried open, its contents stolen, and the box also stolen. There is no solution. There is no recourse. There is no hope.
An even trickier puzzle, can the duck get to safety if the cat can go at 4.6033387 X as fast? 4.6033388? 4.6033389? If those long numbers make you suspect that I worked out the max cat speed, correct.
if
then the ducks position in polar coords should be
(this makes a good calculus puzzle)
I disagree. EDIT: I'm no longer sure I disagree
Sbe n svkrq fcrrq $z$, gur bcgvzny fbyhgvba sbe gur qhpx vf gb svefg tb gb (gur vafvqr bs) gur pvepyr jvgu enqvhf $1/z$ naq pvepyr guvf hagvy vg unf ernpurq bccbfvgr cunfr bs gur png - juvpu nterrf jvgu lbhe fbyhgvba. Gur erznvavat dhrfgvba vf ubj gb ernpu gur rqtr sebz guvf arj fgnegvat cbfvgvba.
N sevraq bs zvar cbvagrq bhg gung nsgre guvf cbvag gur png jvyy or pvepyvat gur bhgfvqr bs gur pvepyr ng znkvzhz fcrrq va n fvatyr qverpgvba (nf bccbfrq gb gheavat nebhaq rirel abj naq ntnva). Guvf qverpgvba vf qrgrezvarq ol gur genwrpgbel bs gur qhpx vzzrqvngryl nsgre oernxvat $e = 1/z$, ohg nsgre gung vf svkrq fvapr gur nathyne fcrrq bs gur qhpx vf ybjre guna gung bs gur png. Gurersber sbe nal tvira cbvag ba gur havg pvepyr, ertneqyrff bs gur pheir jr pubbfr gb trg gurer, gur png jvyy or geniryvat gb gung cbvag ng znkvzhz fcrrq bire gur ybatre nep (juvpu jr pna rafher ol gnxvat na neovgenel fznyy qrgbhe) bs gur havg pvepyr. Va bgure jbeqf: gur qhpx'f genwrpgbel qbrf abg vasyhrapr gur png nalzber. Gurersber gur bcgvzny cngu gb gnxr sebz urer ba bhg vf fvzcyl gur fubegrfg cngu, v.r. n fgenvtug yvar. Nyy gung erznvaf gb or qrgrezvarq vf juvpu fgenvtug yvar gb gnxr.
Gelvat gb fbyir sbe juvpu natyr vf bcgvzny yrnqf gb n flfgrz bs gjb genaprqragny rdhngvbaf va gjb inevnoyrf (nf vf bsgra gur pnfr jvgu gurfr tbavbzrgevp ceboyrzf), ohg ertneqyrff gurl ner abg pbzcngvoyr jvgu lbhe qrfpevcgvba bs enqvhf naq natyr nf n shapgvba bs gvzr.
I solved this problem as a differential equation. I've just realized that the equations above describe a straight line. A tangent to the 1/m circle. The duck moves in a straight line. I found a more complicated way of solving what could have been a simple problem.
V'z abg fher vs jr'er raqvat hc jvgu gur fnzr fgenvtug yvar gubhtu? Znlor zl frg bs genafpraqragny rdhngvbaf unf gur fvzcyr fbyhgvba bs gur gnatrag, juvpu V'ir bireybbxrq, ohg V guvax gur natyr bs gur yvar j.e.g. gur pvepyr bs enqvhf 1/z fubhyq qrcraq ba gur png'f fcrrq.
Ahh, I love puzzles like these! I knew some, but not all of them, so thank you for posting this here! Some thoughts:
25 Horses:
Does anybody have a short proof of optimality, i.e. that if you claim the solution is $n$ races, it cannot be accomplished in $n-1$?
Pirate treasure:
I think some sort of tie-break information is required: if a pirate knows that their vote has no infuence on the number of coins they will obtain, will they vote 'no' out of spite? Or 'yes' to preserve the crew?
Knights and knaves, and What is the name of this god:
If you're willing to spend considerable time you can find a fully general solution to puzzles of this type, although the answers will be long logical constructions.
Blind maze:
Is there some short elegant solution to this? The shortest answer I have is some concatenation of solutions that works but is ugly.
Prisoners and boxes:
Am I confused, or is there a 100% guaranteed strategy to save all prisoners? There is a similar but related problem where the problem is not `made easier' and the prisoners are just sent in (one by one) without warning, and if they all find their own piece of paper they are all set free but if at least one fails then they are all kept in prison. Can you find the optimal solution (along with its expected success rate) now?
Nine dots puzzle:
There are actually two different solutions to this one!
And lastly a contribution of my own:
Having become bored with the classical game of Battleship, you and a friend decide to upgrade the rules a bit. Instead of playing on an nxn-square you will play on the entire planar lattice. Furthermore, you always found it unrealistic that these ships are just sitting there while they are getting bombed, so now at the start of the game you pick a movement vector (with integer components) for each ship, and at the start of each of your turns each ship moves by its movement vector. For simplicity we assume ships can occupy the same square at the same time. To clarify: you still only command the standard fleet of the original Battleship game.
Find a shooting strategy which is guaranteed to sink all your friend's ships.
Hint: Svefg pbafvqre gur pnfr jvgu bayl bar 1k1-fvmrq fuvc cynlvat ba gur yvar bs vagrtref, vafgrnq bs gur 2Q ynggvpr.
Pirate treasure: you're right that tiebreak information is needed. I've added it in now - assume the pirates are spiteful.
Blind maze: nope, it's a fairly ugly solution.
Prisoners and boxes: yes, you can save all of them. Is the solution to your variant the same as my variant?
Battleships: I've found an ugly solution, and I expect it's the one you intended, but is there anything nicer? Sbe rirel fdhner, pbafvqre rirel cbffvoyr zbirzrag irpgbe, juvpu tvirf hf n ghcyr bs yratgu 4. Gura jr vgrengr guebhtu rirel fhpu ghcyr hfvat qvntbanyvfngvba, naq ng rnpu gvzrfgrc jr pna pnyphyngr jurer n fuvc juvpu fgnegrq ba gung fdhner jbhyq unir raqrq hc ol gur pheerag gvzrfgrc, naq fubbg vg.
Prisoners and boxes: yeah, we are probably thinking of the same solution. Vg vaibyirf gur cebonovyvgl bs svaqvat n x-plpyr va na neovgenel ryrzrag bs gur crezhgngvba tebhc ba a ryrzragf.
Battleships: that's the intended solution, yes. I don't know of any nicer one
25 Horses. When you race 5 horses, you know that any horse that doesn't win isn't the fastest. Every horse needs to be raced at least once, or you will have no idea how good it is. Each race rules 4 horses out of the running for fastest, so you need 6 races to find the fastest horse.
However you arrange it, you can't guarantee that the best horse only runs once, so sometimes you will have 2 horses that only lost to the best. Either could be second.
There is no strategy that always finds the first and second in 6 races.
There is a strategy that always finds the best three in 7 races. 5 groups, winners race, those which were directly beaten by at most 2 horses race. (
There is a strategy that always finds the best three in a variable number of races that is sometimes as low as 6.
Joining chains: 6. Cut three links completely in half (2 cuts per link), then use the six half-size links to link everything together. Is this problem a test to see if you actually read the question?
Nope, some people get stuck on which links to cut. The standard answer is 3, which is the same as yours but with the assumption that you can detatch a link from its neighbours after 1 cut, which wasn't made explicit.
The thing is, the illustration shows a ring of 12 links, not the 15 asked for. For a 12-link chain you make 3 cuts in the links of one chain and use them to join the others in a ring. That is how I would expect the problem to be formluated. To get a 15-link chain from the 12 links available you have to cut 3 of them in half (6 cuts) in order to get 15 links.
No, actually you can do better if the links are large enough: cut one link with 4 cuts into 4 pieces and use them to join the remaining four chains.
Oh man, that was a stupid typo. I was very confused, mostly because I myself hadn't properly read the question. Edited now; yours is a clever solution though.
Similar puzzles to this one sometimes allow `out-of-the-box' thinking, where you use a single cut (as in: cleaving action) to cut vertically through all links in a single chain, producing 6 half-links at once.
Logic puzzles
None of the puzzles below have trick answers - they can all be solved using logic and a bit of maths. Whenever a group of people need to achieve a task, assume they're allowed to confer and come up with a strategy beforehand. They're listed roughly in order 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. However, they burn at variable rates (e.g. the first might take 55 minutes to burn 1/4 of the way, then 5 minutes to burn all the rest; the second might be the opposite). How do I use them to time 45 minutes?
25 horses
I have 25 horses, and am trying 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 order?
Monty hall problem (explanation taken from here)
The set of Monty Hall's game show Let's Make a Deal has three closed doors. Behind one of these doors is a car; behind the other two are goats. The contestant does not know where the car is, but Monty Hall does. The contestant picks a door and Monty opens one of the remaining doors, one he knows doesn't hide the car. If the contestant has already chosen the correct door, Monty is equally likely to open either of the two remaining doors. After Monty has shown a goat behind the door that he opens, the contestant is always given the option to switch doors. Is it advantageous to do so, or disadvantageous, or does it make no difference?
Four-way duel
A, B, C and D are in a duel. In turn (starting with A) they each choose one person to shoot at, until all but one have been eliminated. They hit their chosen target 0%, 33%, 66% and 100% of the time, respectively. A goes first, and of course misses. It's now B's turn. Who should B aim at, to maximise their probability of winning?
Duck in pond
A duck is in a circular pond with a menacing cat outside. The cat runs four times as fast as the duck can swim, and always runs around the edge of the pond in whichever direction will bring it closest to the duck, but cannot enter the water. As soon as the duck reaches the shore it can fly away, unless the cat is already right there. Can the duck escape?
Non-transitive dice
Say that a die A beats another die B if, when both rolled, the number on A is greater than the number on B more than 50% of the time. Is it possible to design three dice A, B and C such that A beats B, B beats C and C beats A?
Wine tasting
A king has 100 bottles of wine, exactly one of which is poisoned. He decides to figure out which it is by feeding the wines to some of his servants, and seeing which ones drop dead. He wants to find out before the poisoner has a chance to get away, and so he doesn't have enough time to do this sequentially - instead he plans to give each servant some combination of the wines tonight, and see which are still alive tomorrow morning.
a) How many servants does he need?
b) Suppose he had 100 servants - then how many wines could he test?
Crawling on the planet's face
Two people are dropped at random places on a featureless spherical planet (by featureless I also mean that there are no privileged locations like poles). Assume that each person can leave messages which the other might stumble across if they come close enough (within a certain fixed distance).
a) How can they find each other for certain?
b) How can they find each other in an amount of time which scales linearly with the planet's radius?
Dropping coconuts
I have two identical coconuts, and am in a 100-floor building; I want to figure out the highest floor I can drop them from without them breaking. Assume that the coconuts aren't damaged at all by repeated drops from below that floor - but once one is broken, I can't use it again.
a) What's the smallest number of drops I need, in the worst case, to figure that out?
b) Can you figure out an equation for the general case, in terms of number of coconuts and number of floors?
Pirate treasure
There are 5 pirates dividing up 100 gold coins in the following manner. The most senior pirate proposes a division (e.g. "99 for me, 1 for the next pirate, none for the rest of you"). All pirates then vote on this division. If a majority vote no, then the most senior pirate is thrown overboard, and the next most senior pirate proposes a division. Otherwise (including in the case of ties) the coins are split up as proposed. Each pirate's priorities are firstly to stay alive, secondly to get as much gold as possible, and thirdly to throw as many other pirates overboard as possible (they only pay attention to later priorities when all earlier priorities are tied). They have common knowledge of each other's perfect rationality.
a) What will the most senior pirate propose?
b) What about if there are 205 pirates?
c) Can you figure out a solution for the general case, in terms of number of coins and number of pirates?
Self-sorting
There are n people, all wearing black or white hats. Each can see everyone else's hat colour, but not their own. They have to sort themselves into a line with all the white hats on one end and all the black hats on the other, but are not allowed to communicate about hat colours in any way. How can they do it?
Knights and knaves
You are travelling 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 questions (each directed to only one of the guardians) to figure out which is which.
a) Can you figure it out using two questions?
b) How about one?
What is the name of this god? (explanation taken from here)
Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes/no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are da and ja, in some order. You do not know which word means which.
A game of greed
You have a pile of n chips, and play the following two-player game. The first player takes some chips, but not all of them. After that players alternate taking chips; the only rule is that you cannot take more than the previous player did. The person who takes the last chip wins. Is it the first player or the second player who has a winning strategy, and what is it?
Heat-seeking missiles
Four heat-seeking missiles are placed at the corners of a square with side length 1. Each of them flies directly towards the missile on its left at a constant speed. How far does each travel before collision? (Assume they're ideal points which only "collide" when right on top of each other).
Blind maze
You're located 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 direction, then you don't go anywhere (but you don't get any feedback telling you that you bumped into it). Is there a sequence of steps you can take to ensure that you will eventually find the exit?
Hats in lines
There are 100 prisoners in a line, facing forwards. Each is wearing a black or white hat, and can see the hat colour of everyone in front of them, but not their own or that of anyone behind them; also, they don't know the total number of hats of each colour. Starting from the back of the line, each person is allowed to say either "black" or "white", and is set free if they correctly say the colour of their hat, but shot otherwise. Everyone in the line can hear every answer, and whether or not they were shot afterwards.
a) How many people can be saved for certain, and using what strategy?
b) (Very difficult, requires the axiom of choice). Suppose that the number of prisoners is countably infinite (i.e. in correspondence with the natural numbers, with number 1 being at the back). How can they save all but one?
c) Suppose that the number of prisoners is countably infinite, and none of them can hear the answers of the other prisoners. How can they save all but finitely many?
Prisoners and hats
Seven prisoners are given the chance to be set free tomorrow. An executioner will put a hat on each prisoner's head. Each hat can be one of the seven colors of the rainbow and the hat colors are assigned completely at the executioner's discretion. Every prisoner can see the hat colors of the other six prisoners, but not his own. They cannot communicate with others in any form, or else they are immediately executed. Then each prisoner writes down his guess of his own hat color. If at least one prisoner correctly guesses the color of his hat, they all will be set free immediately; otherwise they will be executed. Is there a strategy that they can use which guarantees that they will be set free?
Prisoners and switch
There are 100 immortal prisoners in solitary confinement, whose warden decides to play a game with them. Each day, one will be chosen at random and taken into an empty room with a switch on the wall. The switch can be in the up position or the down position, but isn't connected to anything. The prisoner is allowed to change the switch position if they want, and is then taken back to their cell; the switch will then remained unchanged until the next prisoner comes in. The other prisoners don't know who is chosen each day, and cannot communicate in any other way.
At any point, any prisoner can declare to the warden "I know that every single prisoner has been in this room already". If they are correct, all the prisoners will be set free; if not, they will all be executed.
a) What's a strategy that's guaranteed to work?
b) Does it still work if the warden is allowed to take prisoners into the room as often as he wants, without the other prisoners knowing? If not, find one that does.
Prisoners and boxes
Another 100 prisoners are in another game. They are each given a piece of paper on which they can write whatever they like. The papers are then taken by the warden, shuffled, and placed into boxes labelled 1 to 100 (one per box). One by one, each prisoner will be taken into the room with the boxes, and must find their own piece of paper by opening at most 50 boxes. If they do so, they're set free. To make things easier for them, before anyone else goes inside, the warden allows one prisoner to look inside all the boxes and, if they choose, to swap the contents of any two boxes (the other prisoners aren't allowed to move anything). Find the strategy which saves the greatest number of prisoners for certain.
Blue eyes (explanation taken from here)
A group of people with assorted eye colors live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their 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?
Quine
Can you write a quine: a program that, when executed, prints its own source code?
Cheating on a string theory exam (puzzle taken from here)
You have to take a 90-minute string theory exam consisting of 23 true-false questions, but unfortunately you know absolutely nothing about the subject. You have a friend who will be writing the exam at the same time as you, is able to answer all of the questions in a fraction of the allotted time, and is willing to help you cheat — but the proctors are alert and will throw you out if they suspect him of communicating any information to you. You and your friend have watches which are synchronized to the second, and the proctors are used to him often finishing exams quickly and won't be suspicious if he leaves early.
a) What is the largest value N such that you can guarantee that you answer at least N out of the 23 questions correctly?
b) (Easier). The obvious answer is 12, but in fact you can do better than that, even though it seems like 12 is the information-theoretic limit. How come?
The hydra game (explanation taken from here)
A hydra is a finite tree, with a root at the bottom. The object of the game is to cut down the hydra to its root. At each step, you can cut off one of the heads, after which the hydra grows new heads according to the following rules:
What strategy can you use to eventually kill the hydra?
Physical puzzles
Balancing nails
Picture a nail hammered vertically into the floor (with most of it still sticking out). You're trying to balance as many other nails on it as you can, such that none of them touch the ground. How do you do so?
Hanging pictures
Consider a picture hanging by a string draped over some nails in the wall, in a way such that if any single nail is removed, the picture will fall to the ground.
a) Is it possible for 2 nails?
b) How about n nails?
Two-piece pyramid
Consider the two identical shapes shown below. Each has two planes of symmetry, and a square base. Is it possible to put them together to create a regular pyramid? (For a fun discussion of this problem in the context of machine learning, see a few minutes into this video).
Plane on a treadmill
Suppose that a plane were on a gigantic treadmill, which was programmed to roll backwards just as fast as the plane was moving forwards. Could the plane ever take off?
Pennies game
Two players take turns to place pennies flat on a circular table. The first one who can't place a penny loses. Is it the first or the second player who has a winning strategy?
Joining chains
You have four chains, each consisting of three rings. You're able to cut individual rings open and later weld them closed again. How many cuts do you need to make to form one twelve-ring bracelet?
Going postal
Alice and Bob live far apart, but are getting married and want to send each other engagement rings. However, they live in Russia, where all valuable items sent by post are stolen unless they're in a locked box. They each have boxes and locks, but no key for the other person's lock. How do they get the rings to each other?
Nine dots puzzle
Without lifting your pen from the paper, draw four straight lines that go through the centres of all 9 dots.
Mutilated chessboard
Consider a chessboard missing two diagonally opposite corner squares. Is it possible to cover all the remaining squares with dominos (where each domino covers two adjacent squares)?
Safe sex
Suppose a man wants to have safe sex with three women, but only has two condoms. How can he do so, while ensuring that no STD is passed from anyone to anyone else?
Wristcuffs
Two people are tied together as in the following diagram. Without being able to undo or cut the ropes, how can they get free?