Take the 2-minute tour ×
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.

There are 3 red axis-aligned interior-disjoint squares.

There are 3 blue axis-aligned interior-disjoint squares.

Is it always possible to find a pair of 1 red square and 1 blue square, such that they are interior-disjoint?

I tried many combinations, and it seems that it's always possible, but unfortunately, I couldn't prove this...

(BTW, what is the name of the subfield of geometry that deals with such questions?)

share|improve this question
1  
diagram, please? –  user31280 Jun 6 '13 at 9:38

1 Answer 1

up vote 2 down vote accepted

I will prove your proposition by a reductio ad absurdum. It turned out to be a rather lengthy argument, mainly due to problems of language and notation, but here it goes:

Let your red squares be given by $$R^i = \left[R_l^i,R_r^i\right]\times \left[R_u^i,R_d^i\right]\subseteq\mathbb{R}^2$$ and your blue squares by $$B^i=\left[B_l^i,B_r^i\right]\times \left[B_u^i,B_d^i\right]\subseteq\mathbb{R}^2$$ and assume that the red squares as well as the blue squares are pairwise interior disjoint. Also assume that no blue square is interior disjoint with any red square.

If $R^1$ and $R^2$ are to be interior disjoint then at least one of the following must be true:

  • $R_r^1 \leq R_l^2$
  • $R_l^1 \geq R_r^2$
  • $R_u^1 \leq R_d^2$
  • $R_d^1 \geq R_u^2$

By rotating our plane if needed we may assume without loss of generality that $R_r^1 \leq R_l^2$.

In order for $B^i$ not to be interior disjoint with $R^1$, we now have $B_l^i\leq R^1_r$. In order for $B^i$ not to be interior disjoint with $R^2$ we have $B_r^i\geq R^2_l$. Thus $[R^1_r,R^2_l]\subseteq [B^i_l,B^i_r]$ for $i=1,2,3$. This means that the blue squares must lie above each other (i.e. $B^1_u\leq B^2_d$, $B^2_u \leq B^3_d$ for the appropriate numbering).

The same argument now shows that the red squares must all lie beside each other (i.e. $R^1_r\leq R^2_l$, $R^2_r \leq R^3_l$ for the appropriate numbering).

Now the distance between the left-most and the right-most red squares is at least the side-length of the middle red square. Hence the side-length of any blue square must exceed the side-length of this particular red square if it is to overlap with the outermost red squares. By the same argument, the side-length of any red square must exceed the side-length of the middle blue square. Thus by transitivity, the side-length of the middle blue square must exceed itself, which is an absurdity.

Hence we conclude that our assumption, that no blue square is interior disjoint from any red square, must be impossible.

share|improve this answer
    
Thank you very much! I will try to summarize: A. The red squares are interior-disjoint. Thus, without loss of generality, we can assume that Red1 is entirely to the left of Red2 (otherwise, rotate the plane). B. If all blue squares intersect both Red1 and Red2, then the horizontal projection of all blue squares must contain the interval between Red1.right to Red2.left. C. The blue squares are interior disjoint. Thus, because of B, they must lie above of each other. –  Erel Segal Halevi Jun 7 '13 at 13:51
    
D. If all red squares intersect each of the blue square, then the vertical projection of all red squares must properly contain the vertical projection of the middle blue square. E. The red squares are interior disjoint. Thus, because of D, they must lie besides each other. F. If all blue squares intersect all red squares, then the horizontal projection of all blue squares must properly contain the horizontal projection of the middle red square. G. From D, the middle red square must be larger than the middle blue square. From F, it is the opposite. Contradiction. –  Erel Segal Halevi Jun 7 '13 at 13:56
    
@Erel That's exactly right. –  Abel Jun 7 '13 at 18:58

Your Answer

 
discard

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.