3
$\begingroup$

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).
$\endgroup$
2
  • 1
    $\begingroup$ If the points are in convex position, say on a circle, you can select an arbitrary subset to be the intersection with a convex set, including $\max(2n,|S_2|)$ elements of $S_2$. If $C$ is restricted to be an axis-parallel rectangle or square, the question is more interesting. $\endgroup$ Jan 16, 2016 at 22:15
  • $\begingroup$ @DouglasZare You are right. I edited the question accordingly. $\endgroup$ Jan 17, 2016 at 7:57

1 Answer 1

3
$\begingroup$

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}$.

$\endgroup$
2
  • $\begingroup$ By "there are at most $cn^4$ possible axis-parallel rectangles containing exactly $2n$ of them" you mean "there are at most $cn^4$ different subsets of $2n$ points that are defined by containment in an axis-parallel rectangle"? (since there are infinitely many different rectangles). $\endgroup$ Jan 17, 2016 at 10:54
  • $\begingroup$ Yes. I've edited to try and clarify. $\endgroup$ Jan 17, 2016 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.