The Last Bean Puzzle

[obs20]

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!]

Spoiler:

I don't see how the pot will be depleted but the ratio of black beans to white beans is increasing.

[pdurrant]

Originally Posted by obs20

Spoiler:

I don't see how the pot will be depleted but the ratio of black beans to white beans is increasing.

I think you may have misunderstood the question. The pot has one fewer beans it it every time through his procedure.

[obs20]

Originally Posted by pdurrant

I think you may have misunderstood the question. The pot has one fewer beans it it every time through his procedure.

Spoiler:

Okay what happens if the last 2 picked are white beans. The they are thrown away and 1 black bean is put back in the pot. Then you have a single black bean left.
Wait....
The last two were white that means the last was white. I get it, I get it

[pdurrant]

Originally Posted by obs20

Spoiler:

Okay what happens if the last 2 picked are white beans. The they are thrown away and 1 black bean is put back in the pot. Then you have a single black bean left.
Wait....
The last two were white that means the last was white. I get it, I get it

No, it's not a trick question. It's really asking what the colour is of the last bean in the pot after doing the described actions 224 (= 150+75-1) times. You have to stop then, because there's only one bean left in the pot, and the rules say to take out two beans.

Answer:

Spoiler:

The last bean in the pot is always white.

Black beans are removed from the pot one at a time. (Either one black and one white are removed, and only the white one put back, or two black beans are removed and one of them is put back)
White beans are only removed in pairs. (White beans are only discarded when a pair of white beans is removed.)

We start with an odd number of white beans. White beans are only removed in pairs. The number of beans in the pot goes down by one every time.

Since the number of beans goes down by one every time, eventually there must be only one bean in the pot. Since white beans are only removed in pairs, we started with an odd number, and white beans are never added to the pot, the last bean in the pot must be white. There's no point in considering the case where the last two beans in the pot are white — that cannot happen. There are never an even number of beans in the pot.

[ShortNCuddlyAm]

Spoiler:

White - there's an odd number of white beans and the way the beans are being removed means there will always be an odd number of white beans

Although it's probably not white any more, but a murky shade of grey-brown from having picked up dirt from the chef's hands through all the hadling... unless of course the beans are cooking in the pot, in which case it will probably be a sort-of purply-grey colour.

[zelda_pinwheel]

Originally Posted by ShortNCuddlyAm

Spoiler:

White - there's an odd number of white beans and the way the beans are being removed means there will always be an odd number of white beans

Although it's probably not white any more, but a murky shade of grey-brown from having picked up dirt from the chef's hands through all the hadling... unless of course the beans are cooking in the pot, in which case it will probably be a sort-of purply-grey colour.

[pdurrant]

Originally Posted by ShortNCuddlyAm

Spoiler:

White - there's an odd number of white beans and the way the beans are being removed means there will always be an odd number of white beans

Although it's probably not white any more, but a murky shade of grey-brown from having picked up dirt from the chef's hands through all the hadling... unless of course the beans are cooking in the pot, in which case it will probably be a sort-of purply-grey colour.

Yes, the right answer with the right explanation. Congratulations!

[LazyScot]

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...

You would need to get complete coverage of the data, which you'd need to prove you'd done....

Also, for some problems (less so for this one), complete coverage may not be practically computable. And for some problems a single "run" may not be computationally tractable (is that the right term? I mean that the algorithms that don't have a polynomial time solution). Unless you are the NSA or some such

From memory, there was a silicon design case, an FPU I think -- the details are hazy in my aged mind -- where most of the design was based on formal proofs, apart from one small step handled by a little bit of code... Guess what? The code was wrong and the result was a bug in the design...

Though, to be fair, such approaches can be handy for a quick test to try and verify or disprove a hypothesis. (I have some memory of this also being used, when combined with statistics and distributions to give a confidence value on an otherwise unproven hypothesis, but I can't remember the details.)

[draghetto]

Sorry ofr the spoiler guys, i didn't know i could use the spoiler tag

[zelda_pinwheel]

Originally Posted by draghetto

Sorry ofr the spoiler guys, i didn't know i could use the spoiler tag

don't worry draghetto, you'll know next time. to use it, click on "go advanced" ; the spoiler button is the one with the eye and the red X : just select the text you want to hide and then click the button.

[pdurrant]

Originally Posted by draghetto

Sorry ofr the spoiler guys, i didn't know i could use the spoiler tag

Not to worry! As you didn't explain your answer, it was not much of a spoiler, and everyone seems to have got on fine. Do join in on the next one — once I decide on a puzzle to post.

[pdurrant]

Originally Posted by pdurrant

once I decide on a puzzle to post.

And here's the next puzzle. An old chestnut, but it's probably new to some of you. It's been a while since I came across it.

https://www.mobileread.com/forums/showthread.php?t=88949