I found the bits-of-entropy analysis hard to follow, so here's how I explained the solution to my wife (who's not a programmer).
SPOILERS FOLLOW as I will be discussing the answer.
Looking at the table, device 3 obviously tells you if the bottle is from the "high" group (8-15) or the "low" group (0-7). So you line up the bottles and start using device 3 on them, and move them into two groups, 0-7 on the left and 8-15 on the right, as you get the results of each test.
Also, once you've found all eight bottles of one group, you can stop testing because all the remaining bottles will be in the other group. If you're lucky this might happen as soon as test 8, but worst case you must test 15 bottles, then you'll know which group the 16th belongs to without needing to check it.
Worst case: 15 tests done so far.
Now look at what device 2 does. For each group, 0-7 and 8-15, it tells you whether that bottle belongs to the "low" half of the group (0-3 or 8-11) or the "high" half of the group (4-7 or 12-15). Furthermore, in each group of eight, once you've identified four "highs" or four "lows" you can skip testing the rest. Worst case, you have to test 7 bottles of each group before you find four of a kind, and can skip at most 1 bottle per group. 2 skips total, 14 tests.
Worst case: 15+14 = 29 tests done so far.
Now you have four groups, 0-3, 4-7, 8-11, 12-15. You use device 2 which will tell you whether each bottle is in the "high" or "low" pair for each group (0-1 or 2-3, 4-5 or 6-7, and so on). Worst case you have to test three bottles from each group before you are guaranteed to find a pair and be able to skip the fourth bottle. So worst case here is 12 tests.
Worst case: 15+14+12 = 41 tests done so far.
Now you have eight pairs that are 0-1, 2-3, 4-5 and so on. The final device, device 0, will tell you whether the bottle you tested is the "low" or "high" bottle of that pair, so you can arrange each pair in correctly-sorted order after testing one bottle. Guaranteed to need 8 tests, with no possibility of luck of the draw changing that number.
Worst case: 15+14+12+8 = 49 tests done and you've arranged the bottles in order from 0 to 15, so you now know the year of every bottle.
Yeah, I really like the sorting formulation! I didn't notice until after I'd written out the intended solution, but it's basically radix sort going from most significant to least significant bit.
I spotted a typo in your explanation though, after the paragraph "Worst case: 15+14 = 29 tests done so far." you need to use device 1, but you wrote in the next paragraph "device 2".
couldnt you link the devices together in parallel, call your captor into the room under pretense of solving the riddle, and then shock them with your cowboy stun gun?
Obviously 1000 rats is a wrong solution, you could remove one and still get the answer.
But we could get better than that when you think about a thousand as three dimensional cube (10^3). Treating a rat with just one layer of the cube we could optimize to 30 rats.
At this point I looked the answer they suggested and it was 10 (binary representation). Obviously one can construct a mulitdimensional cube with just two as a base - 2^10 and then its 20 rats. But know I realized I forgot the very first optimization I mentioned here that you could just use 1000-1 rat in the first place. So it will be fine with just (2-1)x10 rats (and 30-3=27 rats in the case of plain 3-dimensional cube).
But to move the spoiler down a little, my initial solution was to pour all the bottles out into a barrel, mix them together, and refill the bottles. Nothing explodes since you never measure anything, but you know the exact set of years in each bottle.
SPOILER:
T(n) is the number of measurements required for n bits.
If you measure the first bit (of n) of all the bottles, you'll never need to measure the last bottle. At that point, you have grouped the bottles into 2 groups, and need to figure out the remaining n-1 bits. So T(n) = (2^n)-1 + 2T(n-1).
T(1) = 1 (if you have 2 bottles, you only need to measure one.)
T(2) = 2^2-1 + 2*1 = 5
T(3) = 2^3-1 + 2*5 = 17
T(4) = 2^4-1 + 2*17 = 49
In practice, you'd require many fewer measurements. The maximum is only required when your measurements are in the order (01|10)*... and you can stop a bit position early anytime you have found all of the 0s or 1s.
I've no idea how to do better than 49 in the worst case, though. Hm... is it necessarily the case that 45 is possible? (log2(16!))? It seems like that is only true if each measurement can divide the total set of possibilities in half, and I'm not sure why that would be the case.
nice! an alternative solution I came up with (it's the same intuition as divide and conquer, just a flattened out version, same value of 49):
Just go left to right on each bottle, and keep track of how often each prefix has appeared (i.e. on the first bottle, if you get 1, 0, 0, 1), we'd keep track of: {"1": 1, "10": 1, "100": 1}. Now, if a prefix of length 1 appears 7 times, or a prefix of length 2 appears 3 times, we stop measuring (because there's only 1 left).
In all cases, for 8 bottles you will need 4 measurements, for 4 bottles you will need 3 measurements, 2 bottles will require 2 measurements, and 2 bottles will require 1 measurement. (4 * 8) + (4 * 3) + (2 * 2) + (2 * 1) = 32 + 12 + 4 + 2 = 50. But for the very last bottle, you can just do 0 measurements, by way of process of elimination. so 50 - 1 = 49.
How about this (choices are random):
1) Choose two bottles and one device
2) Measure the two. If they're the same, choose another device, if they're different, choose another bottle
When bottles appear identical, make more measurements with different detectors on them (there's no way around doing that)
When a device has accumulated n/2 0 or 1 measurements, the remainder are the opposite number (call this column constraint as per your table)
When selecting the next detector, prefer the one that is closest to meeting the column constraint (otherwise choose randomly)
Sorry about the poor formatting of the algorithm but I'm typing on my phone and don't want to submit something AI generated
I was trying to figure out the runtime of this…it captures your best case scenario, and I think the worst as well, but what about the average?
Has anyone found any good collections of these? Whenever I try to search for riddles online, I end up with mostly results containing wordplay riddles like "what has a mouth but doesn't eat, ..."
Teh Guardian used to (?) publish puzzles by Chris Maslanka which were like this, and, as i recall, pretty good. There are a couple of books collecting them:
Before publishing I found this while trying to see if there was a already a riddle like it out there (closest I could find was the 1000 barrels of wine riddle mentioned at the beginning): https://puzzles.nigelcoldwell.co.uk/
You can also think of this riddle as a very symmetric version of Wordle, where instead of trying to solve for a permutation of letters you're solving for a permutation of years.
> 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.
I originally set it up like that, but felt having to explain that you need to subtract 2000 before doing the binary conversion was unnecessary and kind of distracting
Another bottle-of-wine riddle I have been interested in recently: Say you have B number of tastings and can use each to taste any mix of wines, and you know that exactly zero, one or two of the wines are bad/poisoned/whatever. How many bottles of wine (N) can you cover in those B tastings?
Optimal solutions are known for B <= 13 only, and some asymptotic bounds are known; the rest is conjecture. It is essentially modifying the “standard” wine riddle to allow two poisoned bottles as a possibility.
The wines are from different years
If you apply an arbitrary order to the bottles, the number of possible year-arrangements of the bottles is 16!
Each test gives you one bit of information
Since 2^50 is only greater than 16! by about 50x < 2^6, you only have about 5 tests to spare.
There's probably some clever way to express the solution beyond just the brute force the above implies, but I haven't thought about it past this point
I found the bits-of-entropy analysis hard to follow, so here's how I explained the solution to my wife (who's not a programmer).
SPOILERS FOLLOW as I will be discussing the answer.
Looking at the table, device 3 obviously tells you if the bottle is from the "high" group (8-15) or the "low" group (0-7). So you line up the bottles and start using device 3 on them, and move them into two groups, 0-7 on the left and 8-15 on the right, as you get the results of each test.
Also, once you've found all eight bottles of one group, you can stop testing because all the remaining bottles will be in the other group. If you're lucky this might happen as soon as test 8, but worst case you must test 15 bottles, then you'll know which group the 16th belongs to without needing to check it.
Worst case: 15 tests done so far.
Now look at what device 2 does. For each group, 0-7 and 8-15, it tells you whether that bottle belongs to the "low" half of the group (0-3 or 8-11) or the "high" half of the group (4-7 or 12-15). Furthermore, in each group of eight, once you've identified four "highs" or four "lows" you can skip testing the rest. Worst case, you have to test 7 bottles of each group before you find four of a kind, and can skip at most 1 bottle per group. 2 skips total, 14 tests.
Worst case: 15+14 = 29 tests done so far.
Now you have four groups, 0-3, 4-7, 8-11, 12-15. You use device 2 which will tell you whether each bottle is in the "high" or "low" pair for each group (0-1 or 2-3, 4-5 or 6-7, and so on). Worst case you have to test three bottles from each group before you are guaranteed to find a pair and be able to skip the fourth bottle. So worst case here is 12 tests.
Worst case: 15+14+12 = 41 tests done so far.
Now you have eight pairs that are 0-1, 2-3, 4-5 and so on. The final device, device 0, will tell you whether the bottle you tested is the "low" or "high" bottle of that pair, so you can arrange each pair in correctly-sorted order after testing one bottle. Guaranteed to need 8 tests, with no possibility of luck of the draw changing that number.
Worst case: 15+14+12+8 = 49 tests done and you've arranged the bottles in order from 0 to 15, so you now know the year of every bottle.
Yeah, I really like the sorting formulation! I didn't notice until after I'd written out the intended solution, but it's basically radix sort going from most significant to least significant bit.
I figured it out like you did as well.
I spotted a typo in your explanation though, after the paragraph "Worst case: 15+14 = 29 tests done so far." you need to use device 1, but you wrote in the next paragraph "device 2".
Too easy. You just mix all 16 together, chuck them into the machine, take cover, then walk out through the now exploded door/hole.
Bonus points if you convince her to leave, and rig it up right above the door for when she comes back, home alone style.
Better yet, mix fifteen of the bottles together to do this, then pocket the other one. It's free wine!
Noted down for the next RPG campaign.
couldnt you link the devices together in parallel, call your captor into the room under pretense of solving the riddle, and then shock them with your cowboy stun gun?
I wasn't familiar with 'Poison and Rat' puzzle that the post mentions as an inspiration of the title riddle.
Without looking at the answer I came up with a geometric interpretation of it (explained below as this is a spoiler to the Poison and Rat puzzle).
Obviously 1000 rats is a wrong solution, you could remove one and still get the answer. But we could get better than that when you think about a thousand as three dimensional cube (10^3). Treating a rat with just one layer of the cube we could optimize to 30 rats. At this point I looked the answer they suggested and it was 10 (binary representation). Obviously one can construct a mulitdimensional cube with just two as a base - 2^10 and then its 20 rats. But know I realized I forgot the very first optimization I mentioned here that you could just use 1000-1 rat in the first place. So it will be fine with just (2-1)x10 rats (and 30-3=27 rats in the case of plain 3-dimensional cube).
https://www.geeksforgeeks.org/aptitude/puzzle-19-poison-and-...
I solved it on my dog walk as a recurrence.
But to move the spoiler down a little, my initial solution was to pour all the bottles out into a barrel, mix them together, and refill the bottles. Nothing explodes since you never measure anything, but you know the exact set of years in each bottle.
SPOILER:
T(n) is the number of measurements required for n bits.
If you measure the first bit (of n) of all the bottles, you'll never need to measure the last bottle. At that point, you have grouped the bottles into 2 groups, and need to figure out the remaining n-1 bits. So T(n) = (2^n)-1 + 2T(n-1).
In practice, you'd require many fewer measurements. The maximum is only required when your measurements are in the order (01|10)*... and you can stop a bit position early anytime you have found all of the 0s or 1s.I've no idea how to do better than 49 in the worst case, though. Hm... is it necessarily the case that 45 is possible? (log2(16!))? It seems like that is only true if each measurement can divide the total set of possibilities in half, and I'm not sure why that would be the case.
nice! an alternative solution I came up with (it's the same intuition as divide and conquer, just a flattened out version, same value of 49):
Just go left to right on each bottle, and keep track of how often each prefix has appeared (i.e. on the first bottle, if you get 1, 0, 0, 1), we'd keep track of: {"1": 1, "10": 1, "100": 1}. Now, if a prefix of length 1 appears 7 times, or a prefix of length 2 appears 3 times, we stop measuring (because there's only 1 left).
In all cases, for 8 bottles you will need 4 measurements, for 4 bottles you will need 3 measurements, 2 bottles will require 2 measurements, and 2 bottles will require 1 measurement. (4 * 8) + (4 * 3) + (2 * 2) + (2 * 1) = 32 + 12 + 4 + 2 = 50. But for the very last bottle, you can just do 0 measurements, by way of process of elimination. so 50 - 1 = 49.
\* or ** to (reliably) put * into your text.
(4*8) + (4*3) + (2*2) + (2*1) = ...If you have an * surrounded by whitespace it's left alone but then you have to remember to always surround * by whitespace.
How about this (choices are random): 1) Choose two bottles and one device 2) Measure the two. If they're the same, choose another device, if they're different, choose another bottle When bottles appear identical, make more measurements with different detectors on them (there's no way around doing that) When a device has accumulated n/2 0 or 1 measurements, the remainder are the opposite number (call this column constraint as per your table) When selecting the next detector, prefer the one that is closest to meeting the column constraint (otherwise choose randomly)
Sorry about the poor formatting of the algorithm but I'm typing on my phone and don't want to submit something AI generated
I was trying to figure out the runtime of this…it captures your best case scenario, and I think the worst as well, but what about the average?
I wish author mentioned the worst case of "more optimal" strategy...
"What's the best average value with worst result being no worse than" seems like the perfect question, tho
I love riddles like this.
Has anyone found any good collections of these? Whenever I try to search for riddles online, I end up with mostly results containing wordplay riddles like "what has a mouth but doesn't eat, ..."
Teh Guardian used to (?) publish puzzles by Chris Maslanka which were like this, and, as i recall, pretty good. There are a couple of books collecting them:
https://www.worldofbooks.com/en-gb/products/the-pyrgic-puzzl...
https://www.worldofbooks.com/en-gb/products/pyrgic-puzzles-b...
This should be more of the same:
https://uk.bookshop.org/p/books/university-of-the-mind-fiend...
The GCHQ Christmas Challenges might be worth a look too.
I maintain my personal collection of pure logic riddles here: https://www.oliverhill.xyz/riddles
Before publishing I found this while trying to see if there was a already a riddle like it out there (closest I could find was the 1000 barrels of wine riddle mentioned at the beginning): https://puzzles.nigelcoldwell.co.uk/
You can also think of this riddle as a very symmetric version of Wordle, where instead of trying to solve for a permutation of letters you're solving for a permutation of years.
Raymond Smullyan had many logic puzzles, including the idol that always lies and the idol that always tells the truth. https://duckduckgo.com/?q=raymond+smullyan+puzzles&ia=web
https://www.explainxkcd.com/wiki/index.php/246:_Labyrinth_Pu...
There is a funny story about the idols. https://astralcodexten.substack.com/p/idol-words
> 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.
Lol
Yeah, imagine if hypothetical scenarios didn't exist…then what?
the reader disappears in a puff of logic
Could just label the years 2000 - 2015. It just says "sixteen possible years", not where these years are on the timeline.
I originally set it up like that, but felt having to explain that you need to subtract 2000 before doing the binary conversion was unnecessary and kind of distracting
You could have them be Cambodian wines, dated according to the Kampuchean revolutionary calendar. That way, you even get a year zero.
instead of subtraction, the true reason is that every year was marked by N-gon - and we have no idea which year is represented by each shape
Can't read it on my phone. Ok I guess I have to enable desktop site grumble.
Another bottle-of-wine riddle I have been interested in recently: Say you have B number of tastings and can use each to taste any mix of wines, and you know that exactly zero, one or two of the wines are bad/poisoned/whatever. How many bottles of wine (N) can you cover in those B tastings?
Optimal solutions are known for B <= 13 only, and some asymptotic bounds are known; the rest is conjecture. It is essentially modifying the “standard” wine riddle to allow two poisoned bottles as a possibility.
(This is OEIS A286874 / A303977; https://oeis.org/A286874 https://oeis.org/A303977)
You need at least 45 guesses since 2^44 < 16!
[dead]