Auto-Nim

We can set up a recurrence relation to solve the problem.

It is clear that $E(1)=1$ .

If there are $m$ coins, a robot can take any number of coins from $1$ to $m$ , all with a probability of $\frac{1}{m}$ . Therefore, the probability that there are $n$ remaining coins, where $n\in\mathbb{Z},0≤n≤m-1$ , is $\frac{1}{m}$ .

We can deduce that $E(m)=1+\frac{1}{m}\sum_{i=0}^{m-1} E(i)$ . Note that $1$ is added because the action of a robot taking any number of coins between $1$ and $m$ counts as one turn. Since $E(0)=0$ , we can write the above expression as $E(m)=1+\frac{1}{m}\sum_{i=1}^{m-1} E(i)$ , or $E(m)=1+\frac{1}{m}E(m-1)+\frac{1}{m}\sum_{i=0}^{m-2} E(i)$ .

Notice that $E(m-1)-1=\frac{1}{m-1}\sum_{i=0}^{m-2} E(i)$ . We can use this to simplify the above expression as $E(m)=1+\frac{1}{m}E(m-1)+\frac{m-1}{m}(E(m-1)-1)$ .

Therefore, $E(m)=1+\frac{1}{m}E(m-1)+\frac{m-1}{m}(E(m-1)-1)=1+\frac{1}{m}E(m-1)+\frac{m-1}{m}E(m-1)-\frac{m-1}{m}=E(m-1)+\frac{1}{m}$ .

Because $E(1)=1$ , we can deduce that $E(m)=\sum_{i=1}^{m}\frac{1}{i}$ . Then a simple computer program can show that minimum value of $x$ such that $E(x)>10$ is $\boxed{12367}$ .

Please post your solution to the bonus problem if you figured it out!

Conditional expectation theory tells us that $E(x) \; = \; 1 + \frac{1}{x}\sum_{j=1}^x E(x-j) \hspace{1cm} x \ge 1$ where we are defining $E(0)=0$ . Let us consider the generating function of these coefficients $\mathcal{E}(t) \; =\; \sum_{x=1}^\infty E(x)t^x$ Then $\begin{aligned} t\mathcal{E}'(t) & = \; \sum_{x=1}^\infty xE(x)t^x \; = \; \sum_{x=1}^\infty\left(x + \sum_{j=1}^x E(x-j)\right)t^x \; = \; \sum_{x=1}^\infty\left(x - E(x) + \sum_{j=0}^x E(x-j)\right)t^x \\ & = \; \sum_{x=1}^\infty xt^x - \mathcal{E}(t) + \frac{1}{1-t}\mathcal{E}(t) \; = \; \frac{t}{(1-t)^2} + \frac{t}{1-t}\mathcal{E}(t) \\ \frac{d}{dt}\Big((1-t)\mathcal{E}(t)\Big) & = \; (1-t)\mathcal{E}'(t) - \mathcal{E}(t) \; = \; \frac{1}{1-t} \\ (1-t)\mathcal{E}(t) & = \; -\ln(1-t) \\ \mathcal{E}(t) & = \; -\frac{\ln(1-t)}{1-t} \end{aligned}$ so we end up with the Harmonic numbers $E(x) \; = \; H_x \hspace{2cm} x \ge 0$ Since $H_x \sim \ln x + \gamma$ as $x \to \infty$ we deduce that $H_x \approx 10$ when $x \approx e^{10 - \gamma} = 12366.96811$ , which gives us a good point to start calculating. Since $H_{12367} = 10.000043$ and $H_{12366} = 9.999162$ , we obtain the answer $\boxed{12367}$

---

As for the bonus question, let $a_x$ be the probability that the first robot A wins, given that it is robot A's turn and there are $x$ coins in the pile, and let $b_x$ be the probability that the first robot A wins, given that it is the second robot B's turn and there are $x$ coins in the pile. Then it is easy to see that we have the recurrence relations $\begin{aligned} a_x & = \; \frac{1}{x}\sum_{j=1}^{x-1}b_{x-j} + \frac{1}{x} \\ b_x & = \; \frac{1}{x}\sum_{j=1}^{x-1}a_{x-j} \end{aligned}$ together with $a_1=1$ and $b_0=0$ . It is easy to check that these recurrence relations (plus initial conditions) define all the probabilities $a_x,b_x$ , and that they are satisfied by $a_x \; = \; \left\{ \begin{array}{lll} 1 & \hspace{1cm} & x = 1 \\ \tfrac12 & & x \ge 2 \end{array}\right. \hspace{2cm} b_x \; = \; \left\{ \begin{array}{lll} 0 & \hspace{1cm} & x = 1 \\ \tfrac12 & & x \ge 2 \end{array}\right.$ which gives us the required result.