32
$\begingroup$

A bag contains 7 red discs, 8 blue discs and 9 yellow discs. Two discs are drawn at random from the bag. If the discs are the same colour then they are put back into the bag. However, if the discs are different colours then they are removed from the bag and a disc of the third colour is placed in the bag. This procedure is repeated until there is only one disc left in the bag or the only remaining discs in the bag have the same colour. What colour is the last disc (or discs) left in the bag?

Clarification:

If, for example, in the first drawing a red disc and a blue disc are picked then these two discs will no longer be in the bag but a new yellow disc is put into the bag. Now the bag contains 6 red discs, 7 blue discs and 10 yellow discs.

Attribution: Intermediate Mathematical Olympiad Cayley paper 2023

Improve this question
$\endgroup$
7
  • $\begingroup$ I thought this question had been asked before, but I only found a version with 2 colours. Maybe I was also reminded of this MathSE post. $\endgroup$
    – Jaap Scherphuis
    Commented Aug 1 at 8:13
  • $\begingroup$ @JaapScherphuis it's definitely a riff on an early TedEd puzzle $\endgroup$
    – No Name
    Commented Aug 1 at 9:06
  • $\begingroup$ Very cool puzzle! Now I wonder which of the starting triples of numbers lead to a unique answer? Can we define them in some way? $\endgroup$
    – Dmitry Kamenetsky
    Commented Aug 1 at 13:43
  • 1
    $\begingroup$ @DmitryKamenetsky I am glad you like it. You could post a new question about it. Cheers! $\endgroup$
    – Will.Octagon.Gibson
    Commented Aug 1 at 17:51
  • 1
    $\begingroup$ @DmitryKamenetsky When you consider the solution, I think that 75% of random positive integer triples yield an unique answer. $\endgroup$
    – Oliphaunt
    Commented Aug 2 at 7:51

2 Answers 2

Reset to default
32
$\begingroup$

Note that there are two cases

- two colours are the same -> nothing changes
- two colours are different -> each colour increases or decreases by 1

So what happens as time increases?

At the start we have 7 red, 8 blue and 9 yellow.

In the first scenario nothing changes.

In the second scenario, we will have 6/8 red, 7/9 blue and 8/10 yellow. The numbers themselves don't actually matter, what matters is that each colour has changed from even to odd, or odd to even.

And because of this

Every time two colours are different, the colours change their parity.

This means at the 'end' (and at every state of this game), either:

- Red and yellow are odd and blue is even
- Red and yellow are even and blue is odd

But

The game ends when there is either 1 disc, or only 1 colour. If both red and yellow are odd, neither can be 0 - so this can not be the end scenario

So at the end, red and yellow are even and blue is odd. In which case, red and yellow are both 0 for the game to end, so the final disc(s) must be blue!

Improve this answer
$\endgroup$
1
  • $\begingroup$ This (nicely !) proves that any end state must be an odd number of blue discs. I would add that an end state will be reached almost surely because each non-static move decreases the number of discs, and for each non-end state we have over 1/(i-1) chance of making a non-static move with i the number of discs at that stage (chance that the second disc is different from the first). We can even put a quick bound on the expectation of the number of moves, it is lower than $\sum (i-1) = n(n-1)/2$. (not really a tight bound here but pretty good for the generalisation of this problem) $\endgroup$
    – Vincent
    Commented Aug 2 at 7:34
5
$\begingroup$

Since we know the puzzle has an answer (or else it couldn't be asked here), the answer must be

blue

Under the assumption there is a unique answer, we can choose our moves rather than picking randomly, since any set of moves must lead to the same result. Simply pull each pair of colors sequentially (YB, RY, RB), reducing the number of all colored discs by 1 after each round of pairs (since each round removes two of each disc and puts one back in). After 1 round we have {5R, 6Y, 7B}, then {4R, 5Y, 6B}, and so on. Eventually, we get to {0R, 1B, 2Y}. From here, our only move is to {1R, 0B, 1Y}, which finally leads us to {0R, 1B, 0Y} and the end of the game.

We can also leverage the existence of an answer by observing that this is

at its core, a parity problem. Since R and Y have equal parity there isn't really any way to distinguish them - if R could be the answer, so too could Y. B has different parity and is unique in this regard, and can be the only unique solution. As an extension of this, we can see that when all three colors have equal parity, there is no unique solution - starting from {1R, 1B, 1Y}, we could finish with any of the three colors in the bag, as we can remove any two discs and finish the game in one move.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I don't think the second argument is compelling, because the assertion in the first words of the spoiler can't be justified without actually solving the problem. One could just as easily say “since B and Y both have a composite number of discs there's no way to distinguish them”. $\endgroup$
    – Greg Martin
    Commented Aug 2 at 5:45
  • 1
    $\begingroup$ I don't think your existence argument works for this puzzle. My first (wrong) guess for an answer was that the final disk is any of the 3 colors with equal probability. Any answer that gives some probability distribution for the 3 colors could be a possible answer. $\endgroup$
    – quarague
    Commented Aug 2 at 8:04
  • 1
    $\begingroup$ "Since R and Y have equal parity there isn't really any way to distinguish them" Yes there is; one of them has 7 discs and the other 9. I can distinguish 7 from 9. And why is this *"at its core, a parity problem"? And what exactly do you mean by that? $\endgroup$
    – user90442
    Commented Aug 3 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.