Imagine a cube-shaped piece of Swiss cheese. We model the cheese through a 20x20x20 grid. For simplicity, we assume that each grid cube consists entirely of cheese or entirely of air. On the upper side of our cube of Swiss cheese we then pour water, which penetrates the cheese only through the air holes in the cube. The water may flow through a continuous channel from the top to the bottom, but it may only flow from one air cube to the next, if the two cubes are connected through a face (not just an edge or a corner). The water can also flow on detours such as in a sink drain trap, but it may not flow out on the side walls of the cheese cube.
Now let us programmaticaly implement that model of the Swiss cheese with a random distribution of air and cheese cubes as described above, with the probability of cheese p and the probability of air 1 - p and simulate water flowing through the cheese in order to find out, whether the water flows through to the bottom of the Swiss cheese cube.
By repeatedly simulating water flowing throught the Swiss cheese cube with different probabilities of cheese and air we can ascertain a relationship between p and the probability of water flowing through to the bottom of the Swiss cheese cube, let's name it q. The result looks like this:
q
1 ************************
0.8 *
0.6 *
0.4 *
0.2 *
0 ***********
0 0.2 0.4 0.6 0.8 1 p
My qustion: Why such a strange curve?
This question is taken from the 23rd federal competition of informatics in Germany (2004/2005). An answer to "why such a strange curve" has not been provided on the web (solutions provided).
I hope I'm at the right place with this sort of question.
Maybe you'll find the following explanation intuitive:
In your case, 20*20*20 cells, unless you have at least 20 holes, the probability of water flow is exactly 0. If you have 20 holes, the water can flow if you order them in a column, but the probability that such an order appears randomly is very low, 20*20/Comb(20^3, 20) ~= 1e-57. As you increase the number of holes, appearance of contiguous paths becomes more and more probable.
When all your cells except 20*20 of them are holes, the only way to block the flow is to order all cheese cells into a single "blocking" layer, e.g. a horizontal 20*20 layer. (There are also other possible configurations, but none too probable. You need exactly one cheese block for every (x, y) coordinate and every cheese block must be in touch with all its (x, y)-neighbors. But they may be spread along the z-axis).
Once you have less than 20*20 cheese blocks, you cannot form a full layer and the flow probability becomes exactly 1.