" A coffee can contains some black beans and
white beans. The following process is to be repeated as long as possible.
Randomly select two beans from the can. If they are the
same color, throw them out, but put another black bean
in. (Enough extra black beans are available to do this.)
If they are different colors, place the white one back into
the can and throw the black one away.
Execution of this process reduces the number of beans in the can by one.
Repetition of the process must terminate with exactly one bean in the can,
for then two beans cannot be selected. The question is: what, if anything,
can be said about the color of the final bean based on the number of
white beans and the number of black beans initially in the can?"
When I came across this problem in 1984, I reasoned as follows:
If the can has (1b, 1w) then final bean is white.
If the can has (2b, 1w) then final bean is white because after the first draw the state is (1b, 1w).
If the can has (3b, 1w) then final bean is white because after the first draw the state is (2b, 1w).
I stopped and looked at it and said to myself maybe I can prove something here by mathematical induction.
If the can has (nb, 1w) then final bean is white because after the first draw the state is ((n-1)b, 1w).
By similar reasoning I could prove
If the can has (nb, 0w) then final bean is black because after the first draw the state is ((n-1)b, 0w).
That is nice. Becoming a bit bold,
Starting from (0b, 2w) first draw results in (1b, 0w) i.e black in the end.
Starting from (1b, 2w) first draw results in either (2b, 0w) or (0b, 2w) resulting in black in the end.
Starting from (2b, 2w) first draw results in either (3b, 0w) or (1b, 2w) resulting in black in the end.
Starting from (3b, 2w) first draw results in either (4b, 0w) or (2b, 2w) resulting in black in the end.
By mathematical induction I could prove
If the can has (nb, 2w) first draw results in either ((n+1)b, 0w) or ((n-1)b, 2w) resulting in black in the end.
These three results together form the theorem of irrelevance of number of black beans. I noticed another regularity. Starting with even (odd) number of white beans results in black (white) in the end.
By mathematical induction I could prove for any even number
Starting from (1b, (2*n)w) first draw results in either (2b, (2*n-2)w) or (0b, (2*n)w) resulting in black in the end.
Similarly for any odd number
Starting from (1b, (2*n+1)w) first draw results in either (2b, (2*n-1)w) or (0b, (2*n+1)w) resulting in black in the end.
I satisfied myself this is mathematically correct and test cases helped to get the feel for the result.
Gries differs.
"It doesn't help much to try test cases! It doesn't help to see what happens
when there are initially I black bean and I white bean, and then to see
what happens when there are initially 2 black beans and one white bean,
etc. I have seen people waste 30 minutes with this approach.
Instead, proceed as follows. Perhaps there is a simple property of the
beans in the can that remains true as beans are removed and that,
together with the fact that only one bean remains, can give the answer.
Since the property will always be true, we will call it an invariant. Well,
suppose upon termination there is one black bean and no white beans.
What property is true upon termination, which could generalize, perhaps,
to be our invariant? One is an odd number, so perhaps the oddness of the
number of black beans remains true. No, this is not the case, in fact the
number of black beans changes from even to odd or odd to even with
each move. But, there are also zero white beans upon termination
-perhaps the evenness of the number of white beans remains true. And,
indeed, yes, each possible move either takes out two white beans or leaves
the number of white beans the same. Thus, the last bean is black if ini-
tially there is an even number of white beans; otherwise it is white."
That was the first time I heard of importance of invariant. It is definitely helpful if we can find such properties. Test cases do help us in getting the feel. Is not Gries himself doing the sort of reasoning he discounts in the previous paragraph?
I leave it to the readers to comment on this.
white beans. The following process is to be repeated as long as possible.
Randomly select two beans from the can. If they are the
same color, throw them out, but put another black bean
in. (Enough extra black beans are available to do this.)
If they are different colors, place the white one back into
the can and throw the black one away.
Execution of this process reduces the number of beans in the can by one.
Repetition of the process must terminate with exactly one bean in the can,
for then two beans cannot be selected. The question is: what, if anything,
can be said about the color of the final bean based on the number of
white beans and the number of black beans initially in the can?"
When I came across this problem in 1984, I reasoned as follows:
If the can has (1b, 1w) then final bean is white.
If the can has (2b, 1w) then final bean is white because after the first draw the state is (1b, 1w).
If the can has (3b, 1w) then final bean is white because after the first draw the state is (2b, 1w).
I stopped and looked at it and said to myself maybe I can prove something here by mathematical induction.
If the can has (nb, 1w) then final bean is white because after the first draw the state is ((n-1)b, 1w).
By similar reasoning I could prove
If the can has (nb, 0w) then final bean is black because after the first draw the state is ((n-1)b, 0w).
That is nice. Becoming a bit bold,
Starting from (0b, 2w) first draw results in (1b, 0w) i.e black in the end.
Starting from (1b, 2w) first draw results in either (2b, 0w) or (0b, 2w) resulting in black in the end.
Starting from (2b, 2w) first draw results in either (3b, 0w) or (1b, 2w) resulting in black in the end.
Starting from (3b, 2w) first draw results in either (4b, 0w) or (2b, 2w) resulting in black in the end.
By mathematical induction I could prove
If the can has (nb, 2w) first draw results in either ((n+1)b, 0w) or ((n-1)b, 2w) resulting in black in the end.
These three results together form the theorem of irrelevance of number of black beans. I noticed another regularity. Starting with even (odd) number of white beans results in black (white) in the end.
By mathematical induction I could prove for any even number
Starting from (1b, (2*n)w) first draw results in either (2b, (2*n-2)w) or (0b, (2*n)w) resulting in black in the end.
Similarly for any odd number
Starting from (1b, (2*n+1)w) first draw results in either (2b, (2*n-1)w) or (0b, (2*n+1)w) resulting in black in the end.
I satisfied myself this is mathematically correct and test cases helped to get the feel for the result.
Gries differs.
"It doesn't help much to try test cases! It doesn't help to see what happens
when there are initially I black bean and I white bean, and then to see
what happens when there are initially 2 black beans and one white bean,
etc. I have seen people waste 30 minutes with this approach.
Instead, proceed as follows. Perhaps there is a simple property of the
beans in the can that remains true as beans are removed and that,
together with the fact that only one bean remains, can give the answer.
Since the property will always be true, we will call it an invariant. Well,
suppose upon termination there is one black bean and no white beans.
What property is true upon termination, which could generalize, perhaps,
to be our invariant? One is an odd number, so perhaps the oddness of the
number of black beans remains true. No, this is not the case, in fact the
number of black beans changes from even to odd or odd to even with
each move. But, there are also zero white beans upon termination
-perhaps the evenness of the number of white beans remains true. And,
indeed, yes, each possible move either takes out two white beans or leaves
the number of white beans the same. Thus, the last bean is black if ini-
tially there is an even number of white beans; otherwise it is white."
That was the first time I heard of importance of invariant. It is definitely helpful if we can find such properties. Test cases do help us in getting the feel. Is not Gries himself doing the sort of reasoning he discounts in the previous paragraph?
I leave it to the readers to comment on this.
Beautiful explanation :)
ReplyDeleteVery interesting
ReplyDelete