Get the latest tech news

Sixteen bottles of wine riddle

Imagine the typical everyday scenario in which you have been imprisoned in the wine cellar of an evil combinatorialist. She promises to let you go, but only if you can solve her riddle.

I don’t actually know what the optimal strategy is, but I threw together a greedy approach that always performs the measurement with the higest expected information gain which outperforms the divide and conquer approach in the eight bottle case (computing the expected information gain with sixteen bottles is tricky due to the sheer size of the state space). Figuring out the actual optimal strategy (in terms of number of measurements needed across all possible permutations) in the eight and sixteen bottle case is left as an exercise to the reader ;) I deliberately chose 16 wine bottles for this writeup since its just past the threshold where brute force searching through state space becomes intractable for the average mortal, and requires some pen and paper analysis.

Get the Android app