Q.1. Data
Structure and Algorithms
In a box there are random number of white and black marbles. At
a time two marbles are taken out at random and if
A) Both Black: Discard both and insert a white
B) Both White: Discard one and retain one
C) One Black and One White: Discard White and retain Black.
If initially there are nb black and nw white marbles then determine
the color of the only marble remaining at the end.
Options
1. white if nb is even
2. white if nw is odd
3. black if nb is even
4. black if nw is odd
Ans: 1
Explanation:
Here parity of black is preserved and the parity of white is neglected.
Lets consider each case
A) Both Black: Discard both and insert a white Parity of back is
preserved by discarding both, i.e if there are nb marbles then nb-2
remain. Thus if nb is even, nb-2 is also even. For nw, it becomes
nw+1 and hence parity is changed(or is not conserved).
B) Both White: Discard one and retain one Again no change to nb
and nw parity is neglected.
C) One Black and One White: Discard White and retain Black. Same
applies here also.
Thus, the color of last marble depends on nb and not on nw.
Hence, we get the following table:
| nb |
nw |
remaining |
| even |
even |
white |
| even |
odd |
white |
| odd |
even |
black |
| odd |
odd |
black |
which can be further reduce to :
| nb |
nw |
remaining |
| even |
X |
white |
| odd |
X |
black |
|