Sample two numbers from 1 to 10; maximize the expected product Assume you sample two numbers, randomly drawn from 1 to 10; you could choose two strategies: 1) pick with replacement and 2) pick without replacement. Which strategy would you prefer to maximize the expected product?
I encountered this problem while preparing for an interview. My intuition is picking with replacement would be better. However, I found it too complex to use the brute-force method to prove it. Could anyone suggest a better approach?

Don't know if this counts as simpler than doing direct computation (you have to know Gauss's formula for the sum of the first $n$ numbers), but you can prove your guess by induction on the number of randomly drawn numbers $n$ (and then, your case follows from the special case $n=10$).
So, we have to prove that for each $n \in \mathbb{N}$ with $n \ge 2$ it holds that
$$\frac{1}{n(n-1)}\sum_{\substack{i,j=1 \\ i\neq j}}^n i j < \frac{1}{n^2}\sum_{i,j=1}^n  ij\;,$$
and since, by straightforward computations, we have that
$$ \frac{1}{n^2}\sum_{i,j=1}^n  ij = \frac{(n+1)^2}{4} \;, $$
everything boils down to proving that
$$\frac{1}{n(n-1)}\sum_{\substack{i,j=1 \\ i\neq j}}^n i j < \frac{(n+1)^2}{4}\;.$$
The base case $n=2$ is clear. Assuming we have proven the claim for $n \in \mathbb{N}$ with $n \ge2$, we can prove that the claim is true also for $n+1$ in the following way:
\begin{align*}
   \frac{1}{(n+1)n}\sum_{\substack{i,j=1 \\ i\neq j}}^{n+1} i j
&=
   \frac{1}{(n+1)n}\sum_{\substack{i,j=1 \\ i\neq j}}^n ij + \frac{2}{n} \sum_{k=1}^n k
=
   \frac{1}{(n+1)n}\sum_{\substack{i,j=1 \\ i\neq j}}^n ij + (n+1)
\\
&=
   \frac{n-1}{n+1} \frac{1}{n(n-1)}\sum_{\substack{i,j=1 \\ i\neq j}}^n ij + (n+1)
\\
&<
   \frac{n-1}{n+1} \frac{(n+1)^2}{4} + (n+1) = \frac{(n+1)(n+3)}{4} < \frac{(n+2)^2}{4} \;,
\end{align*}
where the first inequality follows by the induction hypothesis and the second one by the fact that the square is among the rectangles of a given perimeter the one that has the largest area.
As a side effect, note that as a corollary of previous result, we can recycle the previous proof to prove the stronger claim that, for each $n \in \mathbb{N}$ such that $n \ge 2$, we have
$$ \frac{1}{n(n-1)}\sum_{\substack{i,j=1 \\ i\neq j}}^n i j \le \frac{n(n+2)}{4} \;,$$
with strict inequality as long as $n \ge 3$ (base case $n =2$ by direct computation, and then the same proof as before ending just before the last inequality).
