There are n persons.
Each person draws k interior-disjoint squares.
I want to give each person a single square out of his chosen k, so that the n squares I give are interior-disjoint.
What is the minimum k (as a function of n) for which I can do this?
- For n=1, obviously k=1.
- For n=2, obviously k must be more than 2, since with 2 squares per person, it is easy to think of situations where both squares of person 1 intersect both squares or person 2. It seems that k=3 is enough, but I couldn't prove this formally.
- If we don't limit ourselves to squares, but allow general rectangles, then even for n=2, no k will be large enough, as it is possible that every rectangle of player 1 intersects every other rectangle of player 2. So, the sqauare limitation is important.
EDIT: The problem has two versions: in one version, the squares are all axis-aligned. In the second version, the squares may be rotated. Solutions to any of these versions are welcome.
EDIT: Here is a possibly useful claim, relevant for the axis-aligned version:
Claim 1: If two axis-aligned squares, A and B, intersect, then one of the following 3 options hold:
- At least 2 corners of A are covered by B, and B is as large or larger than A;
- One corner of A is covered by B, and one corner of B is covered by A,
- At least 2 corners of B are covered by A, and A is as large or larger than B.
Thus, if A intersects B, then, out of the 8 corners of A and B, at most 6 corners remain uncovered.