Mislabeled Bins
You have three bins of rubber balls. One bin has only yellow balls, one has only red balls, and one has a mix of both. Someone has stuck labels on the bins — "Yellow," "Red," and "Mixed" — but every single label is wrong.
You can draw one ball at a time from any bin you choose.
- What is the fewest number of draws you need to figure out which bin is which? From which bin should you draw?
- Follow-up: Suppose you have $n$ bins, each containing balls of a single color or some mix, and all $n$ labels are wrong. How does your strategy generalize?
Hints
- Think about what the constraint "every label is wrong" actually rules out. How many possible configurations remain?
- The bin labeled "Mixed" cannot actually be mixed. So it must be a single-color bin -- which means a single draw from it reveals its true contents.
- Once you know the true contents of $B_{\text{Mixed}}$, use the constraint that $B_{\text{Yellow}} \neq \text{Yellow}$ and $B_{\text{Red}} \neq \text{Red}$ to force the remaining assignments.
Worked Solution
How to Think About It: The key constraint is that *every* label is wrong. That is not just noise -- it is a hard constraint that eliminates possibilities. When you hear "all labels are wrong," your first instinct should be to figure out how much information you actually need. Three bins with three possible contents feels like you might need multiple draws, but the mislabeling constraint is so strong that a single draw can unravel the whole thing.
Quick Estimate: Three bins, three labels, all wrong. There are only $3! = 6$ possible assignments of contents to bins, and the constraint "no label is correct" means we are looking at derangements. The number of derangements of 3 items is $D_3 = 2$. So before drawing anything, there are only two possible configurations. A single draw that distinguishes between those two configurations is enough. The answer is $1$.
Approach: Use the mislabeling constraint to do logical elimination after one carefully chosen draw.
Formal Solution:
Label the bins by their (incorrect) labels: $B_{\text{Yellow}}$, $B_{\text{Red}}$, $B_{\text{Mixed}}$.
Since every label is wrong: - $B_{\text{Yellow}}$ does not contain only yellow balls. - $B_{\text{Red}}$ does not contain only red balls. - $B_{\text{Mixed}}$ does not contain mixed balls.
The critical observation: $B_{\text{Mixed}}$ is labeled "Mixed" but is *not* mixed. So it must contain either all yellow or all red balls. Draw one ball from $B_{\text{Mixed}}$.
Case 1: You draw a yellow ball from $B_{\text{Mixed}}$. - $B_{\text{Mixed}}$ actually contains only yellow balls. - $B_{\text{Yellow}}$ cannot be yellow (wrong label) and cannot be mixed (that slot is already taken by... wait, mixed is still unassigned). Actually: $B_{\text{Yellow}}$ is not yellow, and $B_{\text{Red}}$ is not red. The remaining contents to assign are {Red, Mixed}. - $B_{\text{Yellow}}$ can be Red or Mixed. But $B_{\text{Red}}$ cannot be Red, so $B_{\text{Red}}$ must be Mixed, and $B_{\text{Yellow}}$ must be Red.
Case 2: You draw a red ball from $B_{\text{Mixed}}$. - $B_{\text{Mixed}}$ actually contains only red balls. - By symmetric reasoning: $B_{\text{Red}}$ must be the mixed bin, and $B_{\text{Yellow}}$ must be the yellow bin... but wait, $B_{\text{Yellow}}$ cannot be yellow (it is mislabeled). So $B_{\text{Yellow}}$ must be Mixed, and $B_{\text{Red}}$ must be Yellow.
In both cases, one draw uniquely determines all three bins.
Answer: The minimum number of draws is $1$. Draw from the bin labeled "Mixed." Since it is mislabeled, it contains only one color. Whichever color you draw tells you what that bin actually holds, and the mislabeling constraint forces the other two bins into their only valid assignment.
Intuition
This problem is really about how much information is already embedded in constraints before you take any action. With three bins and all labels wrong, the number of possible configurations is the number of derangements of three items, which is just 2. A single observation that distinguishes between two possibilities is always sufficient -- that is one bit of information. The trick is choosing *where* to draw: the bin labeled "Mixed" is the only one where a single ball is guaranteed to reveal the bin's identity (since it must be a single-color bin). Drawing from a single-color-labeled bin could give you a ball of the "wrong" color, but you would not know if the bin is mixed or purely the other color.
This kind of reasoning -- counting how many configurations survive your constraints, then figuring out the minimum number of observations to distinguish among them -- shows up constantly in quant interviews. It is the same logic behind information-theoretic arguments in coding theory and optimal experiment design. The lesson: before you start drawing or computing, always ask how many possibilities you are actually choosing between.