A word problem involving induction

Question

The P & W Manufacturing Company makes bubblegum dispensers, and their machines dispense bubblegum balls in pairs (that is, for a nickel, each customer gets two bubblegum balls). The machines are of different sizes and capacities, so the number of bubblegum balls in a given machine is not known. However, it is known that each machine contains an odd number of green bubblegum balls and an odd number of red bubblegum balls.

QUESTION:

Prove by induction that before a dispenser is empty, at least one pair will be dispensed that consists of one green bubblegum ball and one red bubblegum ball.

Answer 1

We prove the following statement by induction on $n$:

For any $n\ge 1$, any gum machine with $2n$ total gumballs, an odd number which are red and an odd number which are green, will at some point output a red and green ball when it is used $n$ times.

Base case: When $n=1$, we have a machine with $1$ red and $1$ green gumball. Obviously, it will dispense a red and green ball when it is used.

Inductive step: Assume that the given statement is true when $n$ is set to $k$. Given a machine with $2(k+1)$ gumballs satisfying the conditions, consider what happens when two gumballs are dispensed. There are three cases...

• One gumballs is red and the other is green. In this case, we are done, because what we wanted to prove will happen has happened.

• Both gumballs are green. We now are left with a machine with $2k$ gumballs. Furthermore, this machine still has an odd number of red and green gumballs (place more justification here if necessary). Therefore, by the inductive hypothesis, when we use this machine $k$ times, it will at some point dispense one gumball in each color, as desired.

• Both gumballs are red. This case is similar to the previous.

Answer 2

I'm not sure why you would use induction on this. If there are an odd number, 2n+ 1, of red gumballs there exist at most n red pairs with one left over. If there are an odd number, 2m+ 1, of green gumballs there exist at most m green pairs with one left over. Those two left over gumballs must come out together.

Answer 3

I'd rather say that the problem is solved using an invariant, which says:

"As long as no mixed pair has been dispensed, the number of green and red are both odd".

This is obvious as taking out a pair of the same color does not change the parities. Then if no mixed pair is taken earlier, the last pair will be mixed.