> I also got this riddle, in 2015. I couldn't solve it. Tbh, I think it's a terrible question. There isn't really a step-by-step problem solving process, but you just need to have a "leap" to realize you can weight the marbles in groups of 3.

It’s an information theory question similar to the “how far can you drop the egg before it breaks” puzzle. You don’t need a leap of intuition, just remember the right theorems and formulae from college.

I probably would’ve failed the interview. At best I could write an algorithm that empirically arrives at the answer, which may or may not impress the interviewer enough to pass.

Stuff like this is why I dropped out of coding competitions some time in high school. You can always brute force the easy version, then the next tiers drop numbers that cannot be solved unless you know (or can invent) that one weird maths trick.

▲

44 minutes ago | parent | next [-]

[deleted]

▲

krackers 4 hours ago | parent | prev [-]

>It’s an information theory question similar

How would you approach it from an information theoretic sense?

	▲	judofyr 2 hours ago \| parent [-]
		In the initial state there's 24 (12 * 2) different possibilities: The marble you're looking for is one of 12 and it's either lighter or heavier. By using a balance scale there's 3 possible outcomes (left side is heavier; right side is heavier; same weight). This means that for your last (third) weighing you'll have to have reduced the problem down to 3 (or fewer) different possibilities. If there's 4 or more there's no way to reduce it down to a single possibility. Before the second weighing you should have reduced it down to 9 (33) different possibilities. Once you know this, you can start making educated guesses for the first weighing and quickly eliminate those which makes it impossible to continue. For instance: Splitting the marbles into two. This gives two possible outcomes: Left side is heaver or right side is heavier. For the first outcome it means that either the target marble is lighter and part of the left group (6 marbles) or heavier and part of the right group (6 marbles). That's 12 different possibilities (more than 9) and therefore we know that it's impossible* to determine the marble with just two more weighings. There's still guessing to be done, but at every part of the decision tree you can at the very least quickly avoid exploring paths which are guaranteed to not work.