It 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 wor

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