A game of plates and olives

The answer to Question 1 is that yes, the belief is justified. By Stirling's approximation, $(2n+1)!!=n^n(2/e)^{n(1+o(1))}$ or $\log (2n+1)!! = n \log n +n(2/e)(1+o(1))$, so for an affirmative answer to Question 1 it is enough to get an upper bound on $G_n$ of the form $G_n \leq n^nC^n$ for some constant $C$.

Here's a sketch of such an upper bound. A game of length $2n$ involves $n$ "$+$'' moves (either $P_+$ or $O_+$) and $n$ "$-$'' moves, so the profile of a game, at the high level of where $+$ moves and $-$ moves are made, can be specified at a cost of $\binom{2n}{n}$ (but a bound of $4^n$ is fine here, too).

Now consider a game in which there are exactly $t$ $O_+$ moves. There are at most $\binom{n}{t}$ options for the location of these moves, and at most $\binom{n}{t}$ options for the location of the corresponding $O_-$ moves.

We now have to consider how many options there are at each $P_+$, $P_-$, $O_+$ and $O_-$ move. That's easy for the $P_+$ moves --- these involve no choice.

For the other moves: given a configuration ${\mathcal C}$ of plates and olives, let $o({\mathcal C})$ be the total number of olives, and let $p({\mathcal C})$ be the size of $\{k:\mbox{in ${\mathcal C}$ there is a plate with $k$ olives}\}$. Then we have (basically) $p({\mathcal C}) \leq \sqrt{2o({\mathcal C})}$, because to have $p({\mathcal C})$ any larger we would need more than $0+1+\cdots + \sqrt{2o({\mathcal C})} \approx o({\mathcal C})$ olives.

We can now bound the number of options at $P_-$ moves by $(\sqrt{2t})^2$ (we have to choose a plate to remove, cost at most $\sqrt{2t}$, the largest possible value of $o({\mathcal C})$ when there are $t$ $O_+$ moves, and then choose a plate on which to deposit the olives from the removed plate, again cost at most $\sqrt{2t}$). So the maximum contribution from $P_-$ moves is $(2t)^{n-t}$. Here and in the next paragraph we are crucially using that all plates with the same numbers of olives on them are indistinguishable.

At the $\ell$th $O_+$ move, there are at most $\sqrt{2\ell}$ options (because there are at most $\ell$ olives on the table at that time), and at the $(t-\ell)$th $O_-$ move there are again at most $\sqrt{2\ell}$ options (with only $\ell$ $O_-$ moves remaining, there are again at most $\ell$ olives on the table at that time). The maximum contribution from $O_+$ and $O_-$ moves is then at most $$ \left(\prod_{\ell \leq t} \sqrt{2\ell}\right)^2 \approx 2^t t! \approx 2^t\left(\frac{t}{e}\right)^t. $$

Putting it all together we get an upper bound on $G_n$ of the form $$ \sum_{t \leq n} 4^n\binom{n}{t}^2 2^t \left(\frac{t}{e}\right)^t (2t)^{n-t} = 8^n\sum_{t \leq n} \binom{n}{t}^2 \frac{t^n}{e^t}. $$

Parameterizing $t=\alpha n$ the summand above is (basically) $$ n^n \exp_2\left\{n(2H(\alpha) +\log_2 \alpha -\alpha\log_2 e)\right\} $$ where $H(x)$ is the binary entropy function. So we have an upper bound of $$ G_n \leq n^n C^n $$ where $$ C=8 \times \exp_2\left\{\max_{\alpha \in (0,1)} (2H(\alpha) +\log_2 \alpha -\alpha\log_2 e)\right\}. $$

With Teena Carroll at Emory & Henry we have been working to optimize this argument (there's lots of room for improvement), and we can currently get $C$ down to about 1.87, off by a multiplicative factor of about 2.5 from the $(2/e)$ appearing in the lower bound.

As to the expected duration, if you look at the total number of plates plus olives there are a+1 moves which increase it and ${ a \choose 2 } + b$ which decrease it, therefore it increases with probability at least $\frac {a + 1} {{a \choose 2 } + b + a + 1}$. As long as a + b is at least 5 this number is always small, much less than .5 (full disclosure: haven't proven that, just plotted a few cases). This guarantees that you will return to N < 5 at least like a random walk with negative drift, which occurs in finite expected time.It is standard to show that since you have a positive probability of ending within 5 steps from there you will soon do it, also within finite expected time.