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](https://en.wikipedia.org/wiki/Binomial_distribution#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](https://math.stackexchange.com/q/1612286/29780)).



A lottery on coins in a convex set
One quick upper bound for the axis-parallel rectangle case for large $n$: Fix an arbitrary arrangement of $4n$ points. Then there are at most $cn^4$ distinct subsets of $2n$ points that lie inside axis-parallel rectangles containing exactly $2n$ points (the points in a rectangle are determined by an uppermost, lowermost, leftmost, and rightmost point). 


For any fixed rectangle containing $2n$ points, the proportion of lotteries for which that rectangle beats $n+C\sqrt{n \log n}$ is $o(n^{-4})$ for sufficiently large $C$, by the same tail bounds you linked to. By the union bound, it follows that with probability approaching $1$ none of the axis-parallel rectangles beat $n+C \sqrt{n \log n}$. 


