The Urn of Destiny Part 2

Destiny is for people who are too lazy to create alternate timelines.
R. Stevens, Diesel Sweeties, 10-05-11

Okay, kids, if you remember from last time when we had that whole bean counting thing? Here’s where we break down the play-by-play and figure out just what was going on there.
So, our goal today is to PROVE that the last bean will always be white and along the way we’ll be able to figure out just what’s going on with that urn.
Remember the rules?

An urn is filled with 75 white beans and 150 black ones. Next to the urn is a large pile of black beans. The beans are removed from the urn according to certain rules.
Remove two beans from the urn at random.
If at least one of the beans is black, place it on the pile and drop the other bean, whether white or black, back into the urn.
But if both of the removed beans are white, discard both of them and take one black bean from the pile and drop it into the urn.

So we can summarize the rules like so, one for each possible pair of beans:

black black -> remove one black bean
white white -> remove two white beans
black white -> remove one black bean
white black -> remove one black bean

Do you see it yet?

The only way we can remove white beans is two at a time. Since there are an odd number of white beans (75), the last bean will ALWAYS be a white bean.
This is what math nerds call a rewrite system. A rewrite system consists of one or more objects (in this case, the beans and the urn) with a set of rewrite rules which take the object(s) from one state to the next. Eventually we will stop with one bean left, so this system is classified as terminating.

How many of you got it right?

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s