# Opening Doors Puzzle

You are in a corridor which has N doors all of the doors are opened. Every time someone passes through the corridor, he closes randomly with equal probability a certain number of doors between 1 and the number of remaining opened doors. What is the expected number of people that need to pass before all the doors are closed? What about when they instead close 0 to N doors each time rather than 1 to N?

So currently I have:

Let $P_N$ = number of people needed to close N doors.

$$E(P_N) = 1 + \frac{1}{N}(\sum\limits_{i=1}^N E(P_{N-i}))$$

Since you add 1 for the one guy coming through, and then since each amount of doors happens of equal probability its just that summation term times the probability of each event happening (which is $1/N$).

I'm not quite sure how to continue to simplify this though...

Thanks for any help.

-
Have you tried working out the cases with 1, 2, 3 doors? – Mark Bennet Jun 30 '12 at 19:38
This question looks related (although in a loose way): math.stackexchange.com/questions/164384/… – D. Thomine Jun 30 '12 at 20:01
You already did most of the work. Write down $E[P_{N-1}]$ and try to use both equations to cancel out the summation. – madprob Jun 30 '12 at 20:02

$$E_N = 1 + \frac{1}{N}\sum\limits_{i=0}^{N-1} E_i$$ starting at $E_0=0$. This is the same as
$$N E_N = N + \sum\limits_{i=0}^{N-1} E_i.$$ But you also have
$$(N-1) E_{N-1} = N-1 + \sum\limits_{i=0}^{N-2} E_i$$ and taking the difference and tidying up gives a simple expression for $E_N - E_{N-1}$ and thus a known sequence for $E_N$.
For your alternative question you instead start with $$A_N = 1 + \frac{1}{N+1}\sum\limits_{i=0}^{N} A_i$$ and proceed in a similar way to get a similar but slightly different result. It is worth working $A_1$ out explicitly as you cannot calculate $\frac00$.