The Last Bean Puzzle

[pdurrant]

An easy one! At least, that's how it's classified where I found it over at http://www.folj.com/puzzles/easy.htm.

A pot contains 75 white beans and 150 black ones. Next to the pot is a pile of 300 black beans.

A somewhat demented chef takes the beans from the pot in the following manner:

• He takes two beans at random from the pot.
• If one of the beans is black, he places it in the pile of black beans and puts the other one (white or black) back in the pot.
• Otherwise, he throws both beans away and takes a black bean from the pile and puts it into the pot.

Note that two beans have been taken out and only one put back. He repeats the procedure, reducing the number of beans in the pot by one each time, until there is only one bean in the pot.

What colour bean is the last one in the pot?

[Oh - and please enclose answers in spoiler tags as usual. Thanks!]

[draghetto]

Originally Posted by pdurrant

An easy one! At least, that's how it's classified where I found it over at http://www.folj.com/puzzles/easy.htm.

A pot contains 75 white beans and 150 black ones. Next to the pot is a pile of 300 black beans.

A somewhat demented chef takes the beans from the pot in the following manner:

• He takes two beans at random from the pot.
• If one of the beans is black, he places it in the pile of black beans and puts the other one (white or black) back in the pot.
• Otherwise, he throws both beans away and takes a black bean from the pile and puts it into the pot.

Note that two beans have been taken out and only one put back. He repeats the procedure, reducing the number of beans in the pot by one each time, until there is only one bean in the pot.

What colour bean is the last one in the pot?

Spoiler:

White

[omk3]

Spoiler:

White.

If you pick two black -> black in pot -1, white the same
If you pick one black one white -> black in pot -1, white the same
If you pick two white -> white -2, black in pot +1

Whatever you do, white beans either stay the same or are reduced by 2. Since their number is odd, there will always be 1 left.

(@draghetto: edit to add spoiler tags, please)

[clarknova]

Spoiler:

I dunno why, but my 'puter tells me it's white every time.

#!/usr/bin/perl
use List::Util 'shuffle';

my (@pot,@pile);

for (my $i=0; $i<300; $i++) {   # Add 300 black beans to the pile
  push (@pile,'B');
}

for (my $i=0; $i<150; $i++) {   # Add 150 black beans to te pot
  push (@pot,'B');
}

for (my $i=0; $i<75; $i++) {    # Add 75 white beans to the pot
  push (@pot,'W');
}


while (scalar(@pot) > 1) {      # Loop until one bean remains in the pot.
  @pot = shuffle(@pot);         # Stir the pot.
  my $b1 = pop(@pot);           # Grab Bean 1 from the pot
  my $b2 = shift(@pot);         # Grab Bean 2 from the pot
  if ($b1 eq 'B') {             # Bean 1 = Black Bean
    push(@pile,$b1);            # Put it in the Pile
    push(@pot,$b2);             # Throw the other in the pot (could be w or b)
  } elsif ($b2 eq 'B') {        # Bean 2 = Black Bean
    push(@pile,$b2);            # Put it in the Pile
    push(@pot,$b1);             # Throw the other in the pot (it's white)
  } else {                      # Both are White, discard them.
    $b1 = pop(@pile);           # Grab one from the pile.
    push(@pot,$b1);             # Put it in the pot.
  }
}                               # Rinse, Wash, Repeat.

print "Last Bean: $pot[0].\n";

[pdurrant]

Originally Posted by clarknova

Spoiler:

I dunno why, but my 'puter tells me it's white every time.

#!/usr/bin/perl
use List::Util 'shuffle';

my (@pot,@pile);

for (my $i=0; $i<300; $i++) {   # Add 300 black beans to the pile
  push (@pile,'B');
}

for (my $i=0; $i<150; $i++) {   # Add 150 black beans to te pot
  push (@pot,'B');
}

for (my $i=0; $i<75; $i++) {    # Add 75 white beans to the pot
  push (@pot,'W');
}


while (scalar(@pot) > 1) {      # Loop until one bean remains in the pot.
  @pot = shuffle(@pot);         # Stir the pot.
  my $b1 = pop(@pot);           # Grab Bean 1 from the pot
  my $b2 = shift(@pot);         # Grab Bean 2 from the pot
  if ($b1 eq 'B') {             # Bean 1 = Black Bean
    push(@pile,$b1);            # Put it in the Pile
    push(@pot,$b2);             # Throw the other in the pot (could be w or b)
  } elsif ($b2 eq 'B') {        # Bean 2 = Black Bean
    push(@pile,$b2);            # Put it in the Pile
    push(@pot,$b1);             # Throw the other in the pot (it's white)
  } else {                      # Both are White, discard them.
    $b1 = pop(@pile);           # Grab one from the pile.
    push(@pot,$b1);             # Put it in the pot.
  }
}                               # Rinse, Wash, Repeat.

print "Last Bean: $pot[0].\n";

I admire the coding effort, but it is possible to solve this without the the use of a computer. Even if you do have the right answer.

[pdurrant]

Originally Posted by draghetto

Spoiler:

White

An explanation is needed before I'll say whether your answer is right or not — after all, you have a fifty-fifty chance of being right if you just chose a colour at random!

Sorry about not mentioning SPOILER tags in the question - I've updated to include the instruction now. We've been using SPOILER tags in puzzle thread so that people who come to the thread late can also join in.

[pdurrant]

Originally Posted by omk3

Spoiler:

White.

If you pick two black -> black in pot -1, white the same
If you pick one black one white -> black in pot -1, white the same
If you pick two white -> white -2, black in pot +1

Whatever you do, white beans either stay the same or are reduced by 2. Since their number is odd, there will always be 1 left.

Exactly right and the right reason too. Congratulations.

[zelda_pinwheel]

Originally Posted by pdurrant

An easy one! At least, that's how it's classified where I found it over at http://www.folj.com/puzzles/easy.htm.

A pot contains 75 white beans and 150 black ones. Next to the pot is a pile of 300 black beans.

A somewhat demented chef takes the beans from the pot in the following manner:

• He takes two beans at random from the pot.
• If one of the beans is black, he places it in the pile of black beans and puts the other one (white or black) back in the pot.
• Otherwise, he throws both beans away and takes a black bean from the pile and puts it into the pot.

Note that two beans have been taken out and only one put back. He repeats the procedure, reducing the number of beans in the pot by one each time, until there is only one bean in the pot.

What colour bean is the last one in the pot?

[Oh - and please enclose answers in spoiler tags as usual. Thanks!]

this puzzle is hurting my brain. i am not sure i am even close (since at first i thought the opposite, but upon re-reading i realised i had probably misunderstood one detail of the puzzle) but i will try it anyway...

Spoiler:

i think the last bean should be white.

the reason is, whatever the draws, the number of white beans can only be reduced by 2 at a time, but black beans are removed 1 at a time. we start with an odd number of white beans. since it's impossible to divide an odd number by 2, there will be 1 white bean left over.

the results of possible draws is this :

2 black beans : end result, 1 less black bean in the pot, same number of white beans (one put on the pile, other back in the pot)

2 white beans : end result, 2 fewer white beans in the pot but 1 more black bean (both white beans discarded, one black from the pile put in)

1 black, 1 white : end result, 1 less black bean, same number of white beans (black one on the pile, other (white) bean back in the pot)

i've changed my mind about 5 times about my answer so i am now going to go see what other people have replied.

[zelda_pinwheel]

draghetto, i've taken the liberty of adding spoiler tags to your post, so other people playing along won't be influenced by your answer. i hope you don't mind.

i've got the answer and for the same reason as omk, who is right, so i am too, and now i'm feeling very proud of myself after all that thinking.

[LazyScot]

Spoiler:

White.

You can only ever reduce the number of white balls by 2, never by 1 (if you take out one white and one black, the white is always returned). Thus sooner or later you will have a single black ball left in the pot, with an arbitrary number of black balls. At this point you will never throw away the white ball, hence the answer of white.

[pdurrant]

Originally Posted by zelda_pinwheel

this puzzle is hurting my brain. i am not sure i am even close (since at first i thought the opposite, but upon re-reading i realised i had probably misunderstood one detail of the puzzle) but i will try it anyway...

Spoiler:

i think the last bean should be white.

the reason is, whatever the draws, the number of white beans can only be reduced by 2 at a time, but black beans are removed 1 at a time. we start with an odd number of white beans. since it's impossible to divide an odd number by 2, there will be 1 white bean left over.

the results of possible draws is this :

2 black beans : end result, 1 less black bean in the pot, same number of white beans (one put on the pile, other back in the pot)

2 white beans : end result, 2 fewer white beans in the pot but 1 more black bean (both white beans discarded, one black from the pile put in)

1 black, 1 white : end result, 1 less black bean, same number of white beans (black one on the pile, other (white) bean back in the pot)

i've changed my mind about 5 times about my answer so i am now going to go see what other people have replied.

Well done Zelda, exactly right and for the right reasons.

[pdurrant]

Originally Posted by LazyScot

Spoiler:

White.

You can only ever reduce the number of white balls by 2, never by 1 (if you take out one white and one black, the white is always returned). Thus sooner or later you will have a single black ball left in the pot, with an arbitrary number of black balls. At this point you will never throw away the white ball, hence the answer of white.

And another right answer with the correct reasoning.

Spoiler:

(Although at one point in your explanation you've written "black" instead of "white".)

[clarknova]

Originally Posted by pdurrant

I admire the coding effort, but it is possible to solve this without the the use of a computer. Even if you do have the right answer.

But that's what computers are for! It would have taken me well over 20 minutes (possibly forever) by myself, but writing a while loop only took 2 minutes.

Besides, there's no better proof than empirical data. :P

[pdurrant]

Originally Posted by clarknova

Besides, there's no better proof than empirical data. :P

Ah — but only if you get the coding right. It's a lot easier to do a written proof for this puzzle than to prove that a program does what you think it does...

[Bilbo1967]

Originally Posted by pdurrant

Ah — but only if you get the coding right. It's a lot easier to do a written proof for this puzzle than to prove that a program does what you think it does...

As somebody involved in software testing, I'd agree

I couldn't test that program without knowing what the expected result was in advance.