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?

There are two states: pick new number or not. In replacement there are four
choices and without replacement there are three:$(0, 0), (0, 1), (1, 0)$.
The probability of the last two is $\frac{1\cdot(n-1)}{n(n-1)}$ and the
expected value is $n\frac{n-1+1}{2}$. Multiplying and simplifying gives $n/2$.
Let $e_n$ be the replacement expectation and $r_n$ the expectation without replacement:
$$
r_n = \frac{(n-1)(n-2)}{n(n-1)} r_{n-1} + 2\frac{n}{2} = (1 - \frac{2}{n}) r_{n-1} + n
$$
so $r_n = \frac{1}{12} (n + 1)  (3n + 2)$. Since $e_n = \frac{(n+1)^2}{4}$,
$$    e_n - r_n = \frac{n^2 + 2n + 1}{4} - \frac{n^2}{4} -\frac{5n}{12} - \frac{1}{6} = \frac{n+1}{12}>0.
$$
