One square per person

Question

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?

NOTES:

• 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.

Answer 1

Here is my counter-example to the case of $n=2$ and $k=3$. Provided of course that the squares need not be the same size. You will have to trust me that all shapes are squares. However, we can see that each square overlaps all 3 of the squares of the other color.

Answer 2

I found an upper bound for the axis-aligned version. It is based on the following claim:

Claim 2: a square A can intersect at most 4 interior-disjoint squares that are as large or larger that A.

• Proof: If A intersects B and B is as large or larger than A, then at least one corner of A is covered by B (See Claim 1 at the end of the question). Since A has 4 corners, there can be at most 4 such squares that are interior-disjoint.

Now we can give each person a square of his choice, using the following algorithm:

1. Find the smallest square out of the $nk$ available squares. If there are more than one - choose one arbitrarily.
2. Give the smallest square to its owner, send that owner home, and remove all squares of that owner.
3. Remove all squares that are intersected by the smallest square. By Claim 2, there are at most 4 such squares per person. Thus, each of the n-1 persons has at least k-4 squares. Return to step 1.

If $k = 4n-3$, then the algorithm will eventually terminate with 1 person and 1 square.

This is only half a solution. Can we do better than $4k-3$ in the axis-aligned version?

Answer 3

This answer: Square coloring proves that, in the axis-aligned version, with $n=2$ people, $k=3$ squares are enough. This is a tight bound.

This answer: https://cs.stackexchange.com/questions/12275/team-construction-in-tri-partite-graph proves that, with $n=3$ people, $k=15$ squares are always enough, but this is obviously not a tight bound (in a previous answer I showed that $k=9$ squares are enough in this case). It is possible that $k=8$ squares are also enough, but this depends on a solution of a SAT problem, and in any case, it is not provably tight.