Sixteen Bottles of Wine Riddle

Summary

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. “Is it the one where there are 1000 barrels of wine and one of them is poisoned?” “Uh, maybe? Do you already know the answer to that one?” “…” You’re lead past a conspicuous amount of barrels and into a new room where you’re given a bottle of wine and four measuring devices. The combinatorialist explains that the wine is from one of sixteen possible years, however the label is missing. Each measuring device will output either a 0 or a 1 depending on what year the wine is from. Your goal is to identify the year while doing as few measurements as possible. The combinatorialist explains what each device outputs using a table: Year Device 3 Device 2 Device 1 Device 0 0 0 0 0 0 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 10 1 0 1 0 11 1 0 1 1 12 1 1 0 0 13 1 1 0 1 14 1 1 1 0 15 1 1 1 1 You briefly wonder how she managed to procure wine from over 2000 years ago before recalling that the wine cellar was built deep inside of a hypothetical scenario. Looking closely, you notice that each device tells you one bit of information about the year. For example, 1101 in binary can be converted to 13 in decimal. You measure the wine with devices 3, 2, 1 and 0 which output 0, 1, 1 and 0 respectively. Converting 0110 from binary to a decimal you arrive at the answer of 6. The combinatorialist nods. “So, can I leave now?” “Hahaha – no. That was just an apéritif.” The combinatorialist reveals 16 new unlabeled bottles and explains that each wine is from a different year from 0 to 15. Once again your task is to identify the year of each bottle of wine. “Am I allowed to mix samples from different bottles to try to measure them simultaneously?” “No, the measuring devices explode instantly if they’re used on any mix of wines.” Before you have a chance to question ...