-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$
5
  • $\begingroup$ I'm not sure if I should tag this under (a) combinatorics (b) reachability also? $\endgroup$ Commented Oct 27, 2015 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
    Commented Oct 27, 2015 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$ Commented Oct 27, 2015 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$ Commented Oct 27, 2015 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
    Commented Oct 27, 2015 at 17:17

2 Answers 2

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$
0
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$
1
  • $\begingroup$ You've gone wrong as well. See @Sleafar 's answer. $\endgroup$ Commented Oct 27, 2015 at 16:04

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.