|
|
Columns Balls and Probability
Posted:
Jul 20, 2008 8:50 PM
|
|
I'm going out on a limb here, to see if anyone can help me or point me into the correct direction:
The problem is simple, but very hard to answer as we make some of the numbers bigger. Lets start of with a simple example:
In this problem, I have Columns, that are hollow, like pipes, and they have space in them for 2 balls. I can represent them with a 2 x 2 matrix when empty,
[ 0 , 0 ]
[ 0 , 0 ]
and full
[ 1 , 1 ]
[ 1 , 1 ]
The problem comes, is determining the probability of "filling" up a column or tube when a ball is placed randomly, The only information that we keep after each ball is placed in, is how many we have previously placed.
This 2 x 2 example is incredibly easy. Here it is as follows, Let f(N) = the probability that a ball will fill a column, where N is the number of balls previously in the array.
f(0) = 0%
[ 0 , 0 ]
[ 0 , 0 ] <= if a ball goes it, it cant fill up a column
f(1) = 50%
[ 0 , 0 ]
[ X , X ] <= the ball has a 50/50 chance of landing on another ball
f(2) = 100%
[ 0 , 0 ]
[ 1 , 1 ] <= no matter where the ball goes, it will always fill up a column
Lets expand this out, to a 2x3
[ 0 , 0 , 0 ]
[ 0 , 0 , 0 ]
This is straight forward as well.
f(0) = 0%
f(1) = ~33%
f(2) = ~67%
f(3) = 100%
Thus for a 2 deep column the equation looks something like this
f(N) = N/X
where X is the number of columns.
I get stuck, where the column dept increases beyond 2, to 3, or 4
Thus for a 3x4
[ 0 , 0 , 0 , 0 ]
[ 0 , 0 , 0 , 0 ]
[ 0 , 0 , 0 , 0 ]
I get lost here... Can anyone help me or point me in the right direction?
PS I did some calcs by hand, and for a 3x4 to get you started looks something like this <c = total possible combinations>
f(0) = 0% <1>
f(1) = 0% <4>
f(2) = 10% <10>
f(3) = 18.75% <16>
f(4) = ~31.5789474% <19>
f(5) = 43.75% <16>
f(6) = 60% <10>
f(7) = 75% <4>
f(8) = 100% <1>
This was just done with lots and lots of counting, and a little bit of deduction.
|
|
