6

There are $2000$ white balls in a box. There are also sufficiently many white, green and red balls outside the box. The following operations are allowed

  1. Replacement of two white balls with a green ball,
  2. Replacement of two red balls with a green ball,
  3. Replacement of two green balls with a white ball and a red ball,
  4. Replacement of a white ball and a green ball with a red ball,
  5. Replacement of a green ball and a red ball with a white ball.

After finitely many of the above operations there are three balls left in the box. Prove that at least one of them is green.

I have been trying to figure this one out, but can't break into the problem. I do not think there is a parity argument here since initally I thought that there should be something to do with the fact that $2000$ is even.

Another thing I thought that I could do is see if there is some property persisting when considering the amount of balls in the box modulo $m$, but I can't figure this out either. What approaches can be taken in this problem?

Danlo
  • 735
  • 6
    One parity observation: the sum of the number of red and white balls is always even. You can just check this from the rules. This immediately shows there must be a green ball, since if it were only white and red balls then the sum would be even so couldn't be $3$. – Brevan Ellefsen Jul 09 '23 at 21:54
  • 2
    As motivation for how to get the above trick, I just looked through the rules and saw they're symmetric under interchanging red and white. We can thus build a symmetrized invariant by considering their sum. – Brevan Ellefsen Jul 09 '23 at 21:59

1 Answers1

6

We note that the moves $1, 2, 4, 5$ decrease the total number of balls in the box by one. The move $3$ leaves it unchanged. So we need to do exactly $1997$ operations of type either $1$ or $2$ or $4$ or $5$. We can do any number of operations of type $3$. Now note that moves $1,2,4,5$ increase or decrease $1$ green balls. The $3$ move instead decreases the number of green balls by $2$ and therefore keeps the parity unchanged. So the parity is determined by the $1997$ moves of the other types and is therefore odd (because the algebraic sum of $1997$ odd numbers is odd). So the number of green ball can't be $0$. Sorry for my bad English

StCS
  • 349
  • 1
  • 8