Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Sixteen bottles of wine riddle

chriskw.xyz

Post reply on HN
Print view View original

31–36 of 36 posts

Re: Sixteen bottles of wine riddle

#31

Post by Jtsummers »

badFEengineer wrote: post #30

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,…

\* or ** to (reliably) put * into your text.

  (4**8) + (4**3) + (2**2) + (2**1) = ...
(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.

Re: Sixteen bottles of wine riddle

#32

Post by netsharc »

rmunn wrote: post #13

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…

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".

Re: Sixteen bottles of wine riddle

#33

Post by ahazred8ta »

chrisshroba wrote: post #15

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, ..."

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

Re: Sixteen bottles of wine riddle

#34

Post by sfink »

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

    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.

Re: Sixteen bottles of wine riddle

#36

Post by rmunn »

netsharc wrote: post #32
rmunn wrote: post #13

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…

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 late for me to edit my comment, but you're correct; thanks for catching that.
Post reply on HN