Maximize sum with no two consecutive variables Random variables $x_1,x_2,\dots,x_{100}$ are drawn independently from the uniform distribution over $(0,1)$. After knowing the values, we are allowed to choose a subset of them as long as no two consecutive variables are chosen. We want to maximize the sum of the chosen variables. In expectation, how high can we make it?
One way to choose is to ignore the values and always choose $x_1,x_3,x_5,\dots,x_{99}$. Since each variable has an expectation of $1/2$, this gives an expected sum of $50$. But it should be possible to do better if we consider the realized values.
 A: Well, the answer
$$
\Bbb{E}[\max(x_1+x_3+\ldots x_99, x_2+x_4+\ldots x_{100})]
$$
is not the correct answer for the expectation value, it is a bit low.
To see this, consider the case of only $4$ uniform randoms instead of $100$.
Here, the expectation in the proposed answer is 
$ \Bbb{E}[
\max(x_1+x_3, x_2+x_4)]
$
and you can work out in your head that this is $\frac{37}{30}$.  The actual expectation is 
$ \Bbb{E}[
\max(x_1+x_3, x_2+x_4, x_1+x_4)] = \frac{27}{20}
$
It is even possible, for higher values of $2N$, that the maximal sum uses fewer than $N$ of the variates!
The exact calculation for $N=100$ is intractable and not the most interesting aspect of the question.  The real question is:
Show that the expectation of the maximal no-contiguous-pair-containing sum among $2N$ uniform variates on $(0,1)$ is of the form
$$M(2N) = N + \frac{\sqrt{N}}{12\pi} + \Theta\left( N^s \right)
$$
with some $s < \frac12$, and as a bit toughr a problem, find $s$.
Note that the first two  terms of that expansion give (unless I have made a mistake) the first tow terms of the asymptotic form that the proposed answer would have implied).     
