Can you keep your marbles?
Logic ; Difficulty: Easy
Can you keep your marbles?
This week’s Riddler Classic is an easy logic problem about 4 bags of marbles whose solution is easily generalized to n bags. Here’s the question reproduced:
At the Riddler Marble Shop, there are four enormous bags of marbles for you to acquire. They are labeled “red,” “green,” “blue” and “assorted.” Being the purist that you are, you want to select two bags of marbles that are not assorted, and you’d settle for some combination of red, green or blue.
However, noticing your interest in the bags, the shopkeeper alerts you. “Buyer beware,” she warns. “Some jerk switched around the labels on all four bags. Right now, every single bag is incorrectly labeled.” To give you a chance of properly identifying the bags you would like, she has kindly allowed you to take two — and only two — marbles out of any of the bags, one at a time.
How can you guarantee that neither of the two bags you take is assorted?
*spoiler alert* solution and answer follow below
Solution: Follow the trail from the bag labeled "Assorted"
Consider the case of \(n\) bags ( \(n \geq 3\)), where there are
- \(n-1\) distinct colored marbles (call the colors 1,2,..\(n-1\) )
- \(n-1\) pure bags with these distinct colors
- 1 bag with assorted colored marbles and
- every one of the \(n\) bags is mislabeled i.e. no bag reads their true content.
The following solution guarantees you will be able to pick 2 pure bags after examining at most \(n-2\) marbles from the bags one at a time.
- Start with the bag labeled assorted. This bag is clearly one of the two pure bags you are looking for. To find the other bag:
- Pick a marble out of the pure bag that is labeled assorted. Let this color be \(k\). Add this color to a set called Picked Colors you maintain on a sheet of paper.
- Now go to whatever bag is (mis) labeled \(k\) and pick a marble from that bag:
- If this marble is one of the colors in your Picked Colors list, you know that the assorted bag is among the bags you have picked from. Just select any one of other unselected bags and you are done!
- If this marble is a diff color from those in the Picked Colors list AND you have not yet sampled \(n-2\) bags, add it to the list. Now go back to step 3 above, replacing \(k\) with this new color.
- Repeat the process till you have sampled a max of \(n-2\) of the bags.
- At this time if you have a new color not in your Picked Colors list, just select the bag labeled with this color as your second pure bag. If on the other hand you have a repeat color, then just select any one of the remaining bags.
Why this works:
We know that the assorted bag has to be a pure colored bag since it is mislabeled. Following the trail of colors from this bag at most \(n-2\) times necessarily has to lead to one of the following:
- You encounter a repeat color at some point during the \(n-2\) picks . This means the one assorted bag has to be one of the bags you have already encountered, thereby allowing you to pick one from the remaining as your second pure bag.
- You don’t encounter a repeat, but your trail passes through the assorted bag. In this case picking the bag labeled with the marble color after \(n-2\) tries has to get you a pure bag since you’ve already passed through the one assorted bag.
- You don’t encounter a repeat and you haven’t picked from the assorted bag yet in your \(n-2\) picks. In this case, realize that the bag that your \(n-2\) choice points to, cannot be the assorted bag. If it was, then the last remaining bag cannot be mislabeled as the question demands. Think about it!
Q.E.D.
Edit:
And if you don’t want to think about 3 above here’s an explanation: In an unbroken trail starting from the assorted, the penultimate bag cannot be the assorted one because that would close the mislabeling loop, forcing the last bag to be labeled correctly! The question clearly states this is not the case.
5 thoughts on “Can you keep your marbles?”
Hmmm. Seems to me this solution requires picking n-1 marbles instead of n-2. Unless you get lucky.
Not sure why you say that, could you elaborate? The solution describes sampling no more than n-2 bags.
Let’s assume four bags. I pick one marble in step two and a second marble in step 3. In step 4, I only have one color in my picked color list. So unless I got lucky, I have to go back to step 3 and pick again.
Ah! Thanks. Once you’ve picked n-2 you’re done. So in the case of 4 bags, you’d be done with the second pick and go to the bag color of your pick. I’ve modified step 5 to call out that out more clearly.
Got it now. This method was my first inclination in solving it but as I mapped it out I didn’t catch that the second color (if not a repeat) made for a safe label to choose.
Thanks!