december 2025
while wandering the depths of the internet, you may encounter shadowy figures who will task you with riddles...
i came across vincent conitzer's airline drinks puzzle while looking through professors at carnegie mellon. as it was still june i gave myself the luxury of sitting down for a few hours to solve it. then i found this famous 100 prisoners problem on miklos racz's website while snooping. at this point i was too academically cooked to spend so long thinking about riddles, but the problem kept gnawing at me for months after. between then and now i also found jeff clune's collection and laurent lessard's many blog posts.
the thought of writing a blog about my favorite riddles has been consuming me for months, and now that graduate applications are finally! (finally!) over, i get to sit down to write it! so here are a few i liked from the last few years, approximately sorted in ascending order of difficulty, and my hints, intuitions and solutions for them.
there is a cup of milk and a cup of water. take one teaspoon of milk, put into the water cup; mix well. take one teaspoon of the mixture in the water cup and put into the milk cup then mix well. which is higher: the percentage of water in the milk cup or the percentage of milk in the water cup?
they are the same. the key to solving the problem is that you start and end with the same volume in each cup, and so if some volume of water went into the milk cup, the same volume of milk must have gone into the water cup. no math needed, just object permanence.
excerpt of a question taken from oxford's mathematics undergraduate admissions test (also known as the MAT) (q7 here). james munro writes some truly whimsical problems for these tests, which kept me entertained for a good part of the pandemic. i also really like his alien dancing problem (q6 here), but that one was more mechanical-problem-solving than a true puzzle. i remember tweeting at him telling him he musn't love triangles if he decided to put such a heinous question about triangles on my own year's test, which i of course bombed.
anywho, here it is, paraphrased for clarity.
a \(n\)-fan consists of a column of \(n\) points, the tips, in a straight line, and a hub, which is not on the line. the tips and the hub are joined together by line segments. a \( n \) -span is a subgraph of the \( n \)-fan containing all its nodes, but only \( n \) of its edges such that it forms a minimum spanning tree. the picture below shows a \(6\)-fan (left) and a \(6\)-span (right).
yes i redrew the drawings for the aesthetics
i) draw all 2-spans & 3-spans
ii) let \(z_n\) denote the number of \(n\)-spans. considering the possible sizes of the top group of tips and how the group is connected to the hub, calculate \(z_4\), and derive an expression for \(z_n\) in terms of \( z_k\), where \( 1 \leq k < n \).
so there are 3 possible \(2\)-spans, and 8 possible \(3\)-spans. for the \(2\)-spans, it is fairly obvious that there cannot be more than 3 configurations.
it is a little harder to convince yourself that there are only 8 possible \(3\)-spans. for me, i found it useful to think of picking 3 edges out of the possible 5 in a \(3\)-fan. this gives \( {5 \choose 3} = 10 \) possible configurations, of which 2 are not spanning trees and thus do not make sense. so 8 total.
there is a hint in the question to consider possible sizes of the top group and how it is connected to the hub, which is a bit vague. the way i would describe the strategy, is to break down the problem recursively by picking the size of the top group. here is an illustration:
if the top group has 4 tips, then there are four ways that group can be linked to the hub, as represented by the dashed lines, and we are done with no more recursive cases to consider. if the top group has 3 tips, then there are three ways that group can be linked to the hub, and the last point can be connected to the hub \( z_1 \) number of ways. if the top group has 2 tips, then there are two ways that group can be linked to the hub, and the last two points can be connected to the hub \(z_2\) number of ways, and so on.
in general:
\[ z_n = n + (n - 1) \times z_1 + (n - 2) \times z_2 + \cdots + 1 \times z_{n - 1} \]the problem is long, here it is on vincent conitzer's page.
the original puzzle that inspired this blog, this is in a lot of senses a very "standard" puzzle (the oxford MAT has a lot of questions of this kind, though simpler in set up). you begin with a large set of hypothesis, and the problem structurally yields you more and more information until you rule out all possible hypothesis but one. the crux of this problem is simply deriving the right assumptions.
in this case, the most important bits of information are:
my solution is also long, here it is.
this is the first in a series of problems i did while studying in budapest with gabor lippner, a hungarian professor at my university and graph theorist by trade. these were great puzzles -- the answers never came easy, and usually required some creativity and a leap of faith. but once you had the answer, you had no doubt that you were right.
first we have a termite with a dream.
a termite lives in a large 3x3x3 cube divided into 27 smaller cubes. he has always dreamed of discovering the entire cube by taking an awesome journey. since he does not want to be bored, he wants to visit all small cubes exactly once. starting from the center, he can travel from one small cube to another if they share a face. can he accomplish his dream?
no. to see it, lets demolish his house >:3
in his deconstructed and spraypainted house, there are 13 pink cubes, and 14 blue cubes. any viable path must start with a pink cube and alternate in color until we are out of small cubes. but we are bound to run out of pink cubes before we finish the traversal, and so the termite will never achieve his dreams.
as a side note, i think a proof for why a full traversal cannot be done can also be constructed via some graph theoretic formulation, which is not as elegant as the coloring proof above, but is likely the more "natural" approach to get to.
you are faced with a door that has four switches, each hidden inside a hole. the holes are located at the four corners of a square. each switch is in one of two possible states, say on or off.
can one open the door in a finite number of moves? if so, how. if not, why?
i love this problem. the naive solution is simply to sit there, and place your hands in any two holes randomly at each turn and always flip them to on. as time goes on the probability of opening the door approaches one, but there is no guarantee that the door will open in finite time. the question essentially asks if we can improve on that naive strategy.
i spent a long time thinking about this. and so i have some hints.
is it possible to put all switches in the on state in finite time?
is there a state where we can guarantee that our next move will always open the door?
the answer is yes, we can always open this door in finite time. the problem would be no fun otherwise. given the arbitrary rotations, there is really only two moves at each state. denote across the move where we place hands in holes in opposite corners of the square, and denote adjacent the move where we place hands in holes in adjacent corners of the square. once our hands are in, we can choose to flip both switches, one switch, or no switches.
hint 1 points to the fact that the problem does not ask us to put all buttons in a specific state, but just in the same state. and that therefore two doors with switches in opposite states are equivalent for our purposes. this also means that there are only three possible door configurations, namely:
hint 2 points to the leftmost state above. if we knew our door was in that state, then we can always do an across move, press both buttons, and open the door. our objective is thus to put the door in the leftmost state above within a finite number of steps.
given that information, what remains of the puzzle is mechanical deduction. there are many ways to do this, here is one solution.
at each move, the door either opens, or is left in one of the states in the next column, as indicated by the arrow. after five moves, the door will always open.
the formulation of the problem here is taken from miklos racz's website
the names of 100 prisoners are placed in 100 wooden boxes, one name to a box, and the boxes are lined up on a table in a room. one by one, the prisoners are led into the room, each may go from one box to another and look in it, but may look in at most 50 boxes and must leave the room exactly as he found it and is permitted no further communication with the others.
the prisoners have a chance to plot their strategy in advance, and they're going to need it. unless every single prisoner finds his own name all will be subsequently executed. find a strategy that has probability of success exceeding 30%.
this is by far the hardest problem here, it is hard to get an answer, and it is hard to prove the answer. full disclosure, i did not solve the problem. i spent about ten days thinking about the problem on and off. but never made the leap that took me to anywhere near the correct solution. i do have one hint that would have gotten me closer to an answer.
should the prisoners establish and agree on which boxes they each open before entering the room?
i will leave wikipedia to articulate the answer and the proof of correctness (it is a fascinating strategy), but as a computer person i wanted to run a simulation, particularly for the asymptotic case of \(2n\) prisoners, as \( n \rightarrow \infty \).
given \( n \) prisoners (\( n\) even) and \( \frac{n}{2} \) boxes to look at, and since the problem ultimately comes down to whether the permutation has cycles of length more than \( \frac{n}{2} \), simulating this strategy does not require painstakingly coding the exact behavior of the prisoners to follow the cycles, instead we can simply generate permutations, compute all the disjoint cycles, and check if the largest cycle has a length of over \( \frac{n}{2} \).
the code can be found here.
i simulated the experiment with up to \( 1000 \) prisoners, running \(10{,}000\) simulations for each setting. here is a plot of success rates against # of prisoners, which illustrates the asymptotic behavior, with success rates (incredibly) always exceeding \( 30 \% \) even as \( n \) becomes large.
you may be asking what the distribution of largest cycle lengths as \( n \) increases looks like, and i'm glad you asked! here is a pretty animation.
the start of the animation looks a little wonky, but as \( n \rightarrow \infty \), the distribution stabilizes. the red line here is plotted at \( \frac{n}{2} \), and represents the maximum longest cycle length that will guarantee a success for the prisoners. importantly we see that that probability mass left of the red line stabilizes past \( n = 100\), which means that probability of success does not decay below a threshold as \( n \rightarrow \infty\), which is also consistent with our asymptotic success rate plot above!
and that's all folks, please send me cool puzzles that you like, i'd love to take a crack! :)
aaanddd next blog is likely a fall and end of year reflection. this was definitely my busiest semester ever and hugely significant year in the grand scheme of my college time. i have many thoughts about the past year and many more about this next one, perhaps i will write some of it!
happy new year to everyone, i hope 2025 has treated you well, and 🥂 to a new year :D
