# Least greedy square

There are $n$ squares of $m$ different colors. Squares of the same color are interior disjoint, but squares of different colors may intersect.

For every square, define its “greed” as the maximum number of squares of a single color that it intersects. For example, in the figure below, the top-left red square has a greed of 1 because it intersects 1 green square; the bottom-right red square has a greed of 4 becaues it intersects 4 green squres (in addition to 1 blue square); the other two red squares have a greed of 2.

MY QUESTION IS: What is the minimum greed that a single square can have, in the worst case?

4 is an upper bound, because the smallest of all squares has a greed of at most 4. This is because, when a square intersects a larger square, at least one corner of the smaller square must be covered. Since a square has 4 corners, it can intersect at most 4 larger squares that are disjoint, i.e., at most 4 squares per color.

2 is a lower bound, as shown by the construction below, where all squares have a greed of 2:

So, the question is whether there is always a square with a greed of at most 2? Or at most 3?

#### Solutions Collecting From Web of "Least greedy square"

Partial solution: Here is an example for lowerbound of $\mathbf{3}$:

and my hypothesis is that this is it (assuming finite number of squares and colors).

I hope this helps $\ddot\smile$