0

Original problem statement:

Melon-boy lives in a flat world, where there is an infinite two-dimensional grid, where each gridsquare is either occupied by a melon (50% chance) or a pumpkin (50% chance). Melon-boy is born on top of a random melon. Melon-boy is also extremely allergic to pumpkins, and will only stay on the little island of melons that he was born on (i.e. he will never cross a pumpkin). Melon-boy can only travel up, down, left and right (i.e. no diagonal crossings). Find the average size of the melon-island (where the size is the total number of melons that melon-boy can reach) upon which melon-boy is born upon.

For example, this is picture represents a melon-island of size 13, where the dark grey gridsquares represent melons that are a part of the island, the light grey gridsquares represent melons that are not part of the island, and the white squares represent pumpkins.

enter image description here

I had no idea how to solve this problem, so first I solved the one-dimensional case of the problem , which turned out to be the following:

$$A = 2(\sum_{n=1}^\infty \dfrac{n}{2^n}) - 1 = 3$$

and which I confirmed through computation. I computed the value for the average island-size for the two-dimensional case, which turned out to be roughly 60, but I still have no idea how to solve it.

Community
  • 1
QCD_IS_GOOD
  • 2,318
  • 1
  • 16
  • 35

1 Answers1

1

This is known as site percolation on the square lattice. There is a critical probability $p_c$ for sites to be occupied by melons above which an infinite cluster appears and the expected cluster size diverges. No closed form is known for this probability; it is approximately given by $p_c\approx0.5927460507921$ (see Wikipedia and MathWorld).

The fact that the critical probability is not known exactly indicates that no closed form is known for the expected cluster size, since one could then find the critical probability by finding where the expected cluster size diverges.

Your result of roughly $60$ fits well with the fact that your probability $0.5$ is quite near to the critical probability.

joriki
  • 238,052