You play the following game.

1. You get $4n$ gold coins and have to arrange them in the unit square in general position (no two coins have the same x or the same y coordinate). Call this set of coins $S_1$.
2. There is a lottery in which each coin in $S_1$ is selected with probability 1/2, independently of the others. Call the set of selected coins $S_2$ (it is a subset of $S_1$).
3. You select an axis-parallel rectangle $C$, with the constraint that it must contain exactly $2n$ original coins ($|C\cap S_1| = 2n$).
4. Your prize is the coins in $C\cap S_2$.

What is the largest number of coins that you can guarantee to yourself in probability at least $1-1/n$, by a sophisticated arrangement of the coins and selection of $C$?

NOTES:

• A. If you have to select $C$ before the lottery (steps 2 and 3 are swapped), then your prize is a binomial variable distributed like $Binom[2n,1/2]$. Its expected value is $n$, and by known tail-bounds, with probability at least $1-1/n$ the prize is at least $n-O(\sqrt{n\log n})$. Here you can select $C$ after seeing the lottery outcomes, so you can potentially do better.
• B. In contrast, if $C$ does not have to be convex, then of course you can just select a set which contains $2n$ coins of $S_2$ and your prize is $\min(|S_2|,2n)$. So the answer should be between $n-O(\sqrt{n\log n})$ and $2n$.
• C. I do not know the answer even in the simpler case in which $C$ must be a square or a 1-dimensional interval (about the latter case I asked in Math.Se).