5 ms·
Anyone who's studied information theory would destroy that puzzle though. I understand this comment in a general sense--the scale's behavior represents two pos
by achompas 14y ago
Anyone who's studied information theory would destroy that puzzle though.
I understand this comment in a general sense--the scale's behavior represents two possible states, so you can use it to filter the answer space in O(log_2 N) ala binary search, and you can get away with O[(log_2 N) - 1] if you partition the answer space the right way.
But what's the information theoretic interpretation of the problem?
- mturmon 14y agoIt is a source coding problem. Kind of like a Huffman code. Depending on how theoretical or applied your information theory coursework was, you might have worked out simple codes like these in class, and that might be an advantage. It's actually very similar to your tree reasoning above. The information theoretic outlook uses the probabilities of each of the N states to make a more efficient code, but since there are no probabilities in this case, the two approaches pretty much coincide. Incidentally, there are three possibilities with each weighing -- scale tips right, scale tips left, scale stays balanced. So your logs should be base 3. In coding language, you are transmitting ternary valued symbols. And, you should dispense with the O() notation, because the lead constant matters very much in this puzzle, and it happens to be 1.