Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can you arrange a finite number of green and red squares on the plane, sides parallel to the axes, such that:

  • Every red square intersects $M$ green squares and no red square;
  • Every green square intersects $M$ red squares and no other green square?

For $M=2$, this is easy:

enter image description here

For $M=3$, this is more difficult, and was solved recently by dtldarek:

enter image description here

For $M=5$, this is impossible, because the smallest square necessarily intersects at most 4 squares of the other color.

So, the only remaining case is $M=4$: Is this possible?

share|cite|improve this question
maybe it can only be done on an infinite plane just quares of the same s1ze and each overlapping its diagonal neightbours, would this solution count? – Willemien Jan 21 '14 at 12:48
@Willemien ‎The number of squares of each color should be finite. – Erel Segal-Halevi Jan 21 '14 at 13:03
What happened to multiple colors? – dtldarek Jan 21 '14 at 16:05
@dtldarek you are right, there is no direct reduction from the multiple-color case (where each square is required cut $M$ squares of a single other color) to the two-color case. But apparently Barry Cipra's answer is adaptable to the multiple-color case. What do you think? – Erel Segal-Halevi Jan 21 '14 at 16:44
@ErelSegalHalevi It is not, the smaller square might have the all the corners covered by (possibly larger) squares of other color. I've also tried to create infinite sequences of similar kind, but with multiple colors you can go close to the edge, and it is still possible to "come back" to center (all the time using "covered" squares). On the other hand, the feeling that it is impossible for values of 4 and higher is even stronger. – dtldarek Jan 21 '14 at 17:15
up vote 3 down vote accepted

It can't be done for $M=4$, for much the same reason as for $M=5$. When two squares intersect, they do so either by each clipping a corner of the other, or by one of them taking a bite from a side of the other. But the latter case requires the biter to be smaller than the bitee, and this leaves only two corners of the smaller (say Green) square available for clipping, hence requires a yet smaller (now Red) square to take a bite from one of its sides, ad infinitum. Hence all the intersections must occur at the corners of the squares. But in any finite arrangement, there'll be squares at the outskirts whose outer corners aren't clipped.

(Side note: In any finite collection of closed sets, there is some minimum distance between non-overlapping pairs. This gives room for the sets to be independently expanded by epsilonish amounts, so that each has a different size while preserving all pairs that do and do not intersect.)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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