3

A box contains $p$ red balls and $q$ yellow balls. Suppose the following procedure is repeated until a single ball remains in the box:

  1. Remove two balls from the box;
  2. If both have the same color, put a red ball in the box;
  3. Otherwise, put an yellow ball in the box.

In both cases, do not put the removed balls back in the box.

What's the color of the last ball? Prove by induction in the number of balls $p+q$.

Firstly, I thought about the base case: assuming $p+q=1$, either there is a red ball or an yellow ball. What do I do with this? I don't know even how to guess what would be the color of the last ball. Does this problem require knowledge of probability theory?

Lucas Peres
  • 589

1 Answers1

4

Hint: from your recent comment, it seems that the question is asking you to determine the final result as a function of $p$ and $q$ (not any kind of probability). The answer is that the final result is red if $q$ is even and yellow if $q$ is odd. To see this note that the pairs $(p, q)$ transform on each step as follows: $$ (p, q) \mapsto \left\{\begin{array}{ll} (p-1, q) & \quad \mbox{if the selection is red-red}\\ (p-1, q) & \quad \mbox{if the selection is red-yellow}\\ (p+1, q-2) & \quad \mbox{if the selection is yellow-yellow}\\ \end{array}\right. $$ In all three cases, if $q$ is even it stays even and if $q$ is odd it stays odd. So on the last step, when one of $p$ and $q$ is $1$ and the other is $0$, then we will have $q = 0$ if it was originally even (giving a red final result) and we will have $q = 1$ if it was originally odd (giving a yellow final result).

I leave it to you to give a more formal verification of the above argument by an induction, e.g., showing that after step $i$, $q_{i+1}$ is even iff $q_1$ is even and that $p_{i+1} + q_{i+1} = p_i + q_i - 1$ (unless $p_i + q_i = 1$, in which case the procedure terminates).

Rob Arthan
  • 48,577
  • Wow, thank you so much for the insight! So I failed to understand the problem in the first place, I missed the "as a function of $p$ and $q$". – Lucas Peres Apr 26 '21 at 23:17
  • Let me add one last thing so that the solution is crystal clear. I could rephrase your answer in function of $p$ just reversing the parities like so: red if $p$ is odd and yellow if $p$ is even. Which one to use is a matter of preference, right? Thanks again for the help! – Lucas Peres Apr 26 '21 at 23:34
  • 2
    No that isn't right. The final result does not depend on the initial value of $p$. The rules aren't symmetric in $p$ and $q$. – Rob Arthan Apr 26 '21 at 23:38
  • I don't see yet why is that the case... I'll analyze the solution more thoroughly. Glad you corrected me right away. – Lucas Peres Apr 26 '21 at 23:44
  • 1
    No, because the transformation of $(p, q)$ shown above does not preserve the parity of $p$. It only preserves the parity of $q$. For example, if we start with two red balls and zero yellow balls we end with one red ball and if we start with three red balls and zero yellow balls we also end up with one red ball despite the former beginning with even number of red balls and the latter beginning with an odd number. – Adam Zalcman Apr 26 '21 at 23:45
  • 2
    As a supplement to Adam's comment: looking at small examples is very helpful in this kind of problem. In this case, it only takes a few minutes to look at all the cases with $p + q \le 3$ say and the results are very instructive. – Rob Arthan Apr 26 '21 at 23:48
  • I see!! Thank you @AdamZalcman! :) – Lucas Peres Apr 26 '21 at 23:48