# 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?

• Why could a large red square not intersect, say, 15 blue squares, all lined up along its right-hand edge, but not intersecting each other? Perhaps you need to be clearer for us on what the constraints on the squares might be. – John Hughes Jan 16 '14 at 20:43
• Or, what if all squares have distinct interiors? – Eddie E. Jan 16 '14 at 20:43
• @John If I understand the problem correctly, then the question is on $$\sup_{\text{instance }I}\quad\min_{\text{square } s \in I}\quad\mathrm{greed}(s).$$ – dtldarek Jan 16 '14 at 20:44
• @HagenvonEitzen yes. In other words: Is there an arrangement of squraes where each square intersects at least 3/4 squares of at least one other color? – Erel Segal-Halevi Jan 16 '14 at 20:59
• @Listing The question stipulates that they must be squares, i.e. side lengths are equal. – Eddie E. Jan 16 '14 at 22:10

Partial solution: Here is an example for lowerbound of $\mathbf{3}$: I hope this helps $\ddot\smile$