What was the closed form expression for the number of rabbits?
The number of rabbits at the (i+1)'th step is equal to the number of rabbits at the i'th step minus that one rabbit which is /maybe/ being eaten. And the "maybe" I think can be quantified as the probability the Troll has to find a rabbit at the i'th step. So:
R_(i+1) = R_i -1 * P(Troll finds a rabbit)
And now we have to calculate the probability of the event "Troll finds a rabbit" (i'll call it event A). There are 2 cases: * the Troll falls into a black hole (btw, i'm gonna assume the blackholes teleport to any cell with uniform probability); * the Troll does not fall into a black hole;
I'm going to call these two events B and not(B).
So:
P(A) = P(A given B) + P(A given not(B))
Well, P(A given B) is the probability that Troll is being teleported to a cell with a rabbit in it, that is number of rabbits over number of cells: R_i / (nm)
P(A given not(B)) is the probability that Troll will step on a rabbit in a nearby cell which is: rabbits' density over 8: R_i / (8nm)
So:
R_(i+1) = R_i - ( R_i/nm + R_i/8nm ) = R_i * ( 1 - 9/8nm ) = ... iterating ... = R_0 * ( 1 - 9/8nm )^i
R_0 being the initial number of rabbits. I'm not sure all this is correct, but that formula confirms the following intuitions: * The number of rabbits is monotonically decreasing at every step; * The bigger the grid, the slower the decrease.
edit: The closed formula would be:
int numOfRabbits(int numOfSteps) {
if (numOfSteps == 0) return R_0;
else return R_0 * (1 - 9/8nm)^(numOfSteps-1);
}