I'll give it a try...

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);

}

I've made a good living as a programmer for a decade now, and I'm not afraid to say I don't even understand the question.

It's a silly question unless it's for a quantitative role.

Edit: Redacted: left for consistency. Had him confused there.

A closed form expression is basically just a mathematical function used to model a potentially infinite series.

Take a look here: http://en.wikipedia.org/wiki/Closed-form_expression

Look at the first and second examples.

You'll see the big summation sign (for loop: i to infinite) and then an explicit function.

If you want to think, what the heck is this math crap used for: think about a more basic everyday concept like recursion. How do you know it will terminate?

I don't think he is talking about the closed form expression (at least I know what a closed-form is and still couldn't understand the question).

There was no information whatsoever about what changes on each iteration... if nothing changes then the answer would be a constant of whatever rabbits were at the beginning... and that doesn't sound about right :/

Bah got ya.

Thank god I am not alone...

Good to hear. I'm working as a Jr. Software Engineer now, and I don't consider mathematics one of my strong points. Do many positions actually expect people to know these kinds of questions? I'd crash and burn here.

My guess is that you'd model the troll as a 2D simple symmetric random walk with the rabbits and black holes stationary and distributed randomly with some densities R and B.

As a first go I'd assume that the topology was that of a torus, so as to not deal with the boundary. Now, as the exact definition of a "round" wasn't specified, I'll just assume the troll can walk forever.

Now, it's been proven that a simple symmetric random walk on a 2D lattice has probability 1 of reaching any given point as the number of steps goes to infinity. So, ignoring the teleporting, the closed form answer for the number of rabbits eaten is mnR.

With teleporting, I'd guess the Markov chain would mix better. So, the closed form answer would again be mnR.

It's underspecified anyway -- we need to know about the motion of rabbits, the troll, the density of black holes, etc.

probaby not right...

E(number_of_rabbits) = rabbits_in_last_turn - prob(land on rabbit) - sum_i_to_infinity(prob(land_on_blackhole)^i*prob(land on rabbit))

This is not a closed form thought... (although it sounds about right)

I don't think the question is complete... otherwise I probably just give: x => Num of Rabbits, y => Num Holes x,y,x+y=[0,m*n-1]

In that context I'd be really tempted to ask why they needed a closed form expression for the number of rabbits...

Yes

But my bet would be zero, if the troll has infinite time

Am also curious.