-1
$\begingroup$

You have a bag that contains $b$ black balls and $w$ white balls. ($b+w>2$) You put your hand into the bag and pull out a pair of balls.

  • If both balls are black, you throw away one and return one to the bag.
  • If both balls are white, you throw them both away.
  • If the balls are of different colours, you throw away the black ball and return the white ball to the bag.

You repeat this process $N$ times. At the end, you end up with exactly one ball in the bag.

For what all values of $b$ and $w$ is the maximum possible $N$ different from the minimum possible $N$?

$\endgroup$
  • $\begingroup$ I'm not sure if I should tag this under (a) combinatorics (b) reachability also? $\endgroup$ – ghosts_in_the_code Oct 27 '15 at 11:55
  • $\begingroup$ What should N be for combinations where you never end up with exactly one ball left, such as b=0, w=4? $\endgroup$ – Kevin Oct 27 '15 at 12:01
  • $\begingroup$ @Kevin Assume that $b$ and $w$ are given such that it is possible to end up with a single ball. $\endgroup$ – ghosts_in_the_code Oct 27 '15 at 12:02
  • $\begingroup$ You should think about that again. Whenever w is even it is possible to end up with no balls left. You just need to eliminate all blacks first with (1) or (3) and can then eliminate all whites with (2). $\endgroup$ – The Dark Truth Oct 27 '15 at 12:55
  • $\begingroup$ @TheDarkTruth The question doesn't say it's not possible to remove all balls. It only limits the scope to a subset of possible cases, namely the ones with one ball in the bag at the end. $\endgroup$ – Sleafar Oct 27 '15 at 17:17
10
$\begingroup$

The conditions can be reduced to effectively the following 2 cases:

  • remove 2 white balls
  • remove 1 black ball

If $w$ is even then the last ball must be black and then $N=\frac{w}{2}+(b-1)$.

If $w$ is odd then the last ball must be white and then $N=\frac{w-1}{2}+b$.

In both cases the value of $N$ is fixed, so the minimum and maximum are equal.

$\endgroup$
2
$\begingroup$

The maximum and minimum $N$ are different, when $w$ is even and $b$ is not zero.

Whenever $w$ is uneven we will, at the end, be left with a single white ball. In this case $N=\frac{w-1}{2}+b$.

Whenever $w$ is even and $b$ equals zero we will be left with zero balls. In this case $N=\frac{w}{2}$.

Whenever $w$ is even and $b$ is not zero we have two possible outcomes:

  • If we remove the last black ball before the last two white balls we will be left with zero balls in the end. In this case $N=\frac{w}{2}+b$

  • If we remove the last two white balls before the last black ball we will be left with one black ball in the end. In this case $N=\frac{w}{2}+b-1$

Our maximum with first case is exactly one step more than our minimum with the second case.

$\endgroup$
  • $\begingroup$ You've gone wrong as well. See @Sleafar 's answer. $\endgroup$ – ghosts_in_the_code Oct 27 '15 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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