# The Urn of Destiny Part 1

Not without a shudder may the human hand reach into the mysterious urn of destiny.
Friedrich Schiller
Here’s the situation:
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.
(From Dewdney, A. K. (1993). The Tinkertoy computer and other machinations. New York: W.H. Freeman.)
If you read the rules carefully, you’ll notice that the urn loses one bean for each turn. Eventually you will reach the point where you only have one bean left. The question is, what color is that bean?
Since I don’t have an urn handy and the only beans I have are canned, I’m going to see if I can simulate this problem using my computer and find out the color of the last bean. Just like last time, I’ll sketch out the problem using pseudo code to get it into a form that my stupid computer can understand. (Note that although computers are not smart, it turns out that being stupid really, really quickly simulates smartness.)
First we set up our urn.
Bean_wht=75
Bean_blk=150

Now the next bit may seem a little strange for those of you who don’t program computers. However, it turns out that programmers have to dumb down the problem in order to get the computer to understand it, so the code can get a little..metaphorical. Programmers put a lot of time and effort to pick the right metaphor for a particular problem.
(As a side note, computers don’t really do randomness but they can fake it. The explanation is a bit obscure but suffice it to say that if computers were truly random devices then we couldn’t get any real work done on them.)
# Pick two beans at random
Let bean1 = random(black,white)
If (bean1 = white)
then decrement Bean_wht by one
else decrement Bean_blk by one
# (The bean has to be either black or white, right?)
Let bean2 = random(black,white)
If (bean2 = white)
then decrement Bean_wht by one
else decrement Bean_blk by one
# if bean1 is black, put bean2 back in the urn. If bean2 is black, put bean1 back.
If (bean1 = bean2)
then increment Bean_blk by one
If we still have more than one bean left, go pick another pair of beans ->>
if (bean1=black)
then increment Bean_wht by one
else increment Bean_blk by one
If we still have more than one bean left, go pick another pair of beans ->>

# In short, if bean1 and bean2 are both the same color, add a black bean to the urn.
# If we have one bean left, stop picking beans and report the color of the last bean.
if (URN=1)
then if (Bean_wht)
print “the last bean is white”
else print “the last bean is black”
Okay, let me take a few moments to plug this in (or something like it) and see what I get. The metaphor (or paradigm) I’m using is “There is NO urn”. I just count beans. Yes, I’m literally a bean-counter. Anyway, this is what I’ve got:

```#!/bin/bash

# Beans.sh - a script to simulate the Grecian Urn problem from A.K. Dewdney's 'The
# Tinkertoy Computer"

# An urn has 150 black beans and 75 white beans. You pick two beans at random and then

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

# Setup

export BEAN_BLK=150
export BEAN_WHT=75
URN=\$((BEAN_BLK+BEAN_WHT)) # Total number of beans in the URN

# Let's out-source our bean picking to its own chunk of code
# This is actually a bit subtle, as my initial assumption is
# that I'm equally likely to pick a black bean as a white bean
# But we know that's not true, don't we, boys and girls?

pick_bean ()
{
# First, check to see if we've run out of white or black beans
if [ \$BEAN_BLK -eq 0 ] # no black beans left
then
{
echo "white"
return
}
fi

if [ \$BEAN_WHT -eq 0 ] # no white beans left
then
{
echo "black"
return
}
fi

RANGE=`expr \$BEAN_BLK + \$BEAN_WHT`
number=\$RANDOM

let "number %= \$RANGE" # pick a number from 0 to the number of beans

if [ "\$number" -lt \$BEAN_WHT ]
then
{
echo "white"
}
else
{
echo "black"
}
fi

}

#Another function to tell me how many beans I have left.
beans_remaining ()
{
echo Black beans left: \$BEAN_BLK
echo White beans left: \$BEAN_WHT
}

# Setup our beans
BEAN1=
BEAN2=

while [ `expr \$BEAN_BLK + \$BEAN_WHT` -gt 1 ]
do
{
BEAN1=`pick_bean`
BEAN2=`pick_bean`

if [ "\$BEAN1" == white ]
then let "BEAN_WHT -= 1" # decrement white beans
else let "BEAN_BLK -= 1" # decrement black beans
fi

if [ "\$BEAN2" == white ]
then let "BEAN_WHT -= 1"
else let "BEAN_BLK -= 1"
fi

if [ "\$BEAN1" == "\$BEAN2" ]
then
{
let "BEAN_BLK += 1"
continue
}
fi

if [ "\$BEAN1" = black ]
then
{
let "BEAN_WHT += 1"
continue
}
fi

if [ "\$BEAN1" = white ]
then
{
let "BEAN_WHT += 1"
continue
}
fi

#URN=\$((BEAN_BLK+BEAN_WHT))

}
done # End of while loop

beans_remaining```

When I run it, here’s my output:

```isaac7:WeHateMath tsinclair\$ ./Beans.sh
Black beans left: 0
White beans left: 1
isaac7:WeHateMath tsinclair\$ ./Beans.sh
Black beans left: 0
White beans left: 1
isaac7:WeHateMath tsinclair\$ ./Beans.sh
Black beans left: 0
White beans left: 1
isaac7:WeHateMath tsinclair\$ ./Beans.sh
Black beans left: 0
White beans left: 1```

I ran it several times and it looks like the last bean left is in fact white, just as Dewdney claims. Of course, the plural of anecdote is NOT data. If I ran it an infinite number of times, would it always come out the same?

For part 2 of this post, I’d like to see if I can explain why this is and prove, if possible, that it will always work out with one white bean left. If any of you have an answer or even just speculation, feel free to post it in the comments. For you advanced types, can you tell me if it makes a difference starting with equal amounts of white and black beans?