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.
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).
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?
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
> 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.
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.
reply