Assume $ n\ge7$ and there exist $ n$ boxes $ B_1,\ldots,B_n$ such that $ B_i$ and $ B_j$ intersect if and only if $ i\not\equiv j\pm1\pmod{n}$. $ B_1$ and $ B_2$ does not intersect, but both intersect $ B_{n-3}$ and $ B_{n-2}$. So $ B_{n-2}$ and $ B_{n-3}$ are bridges which connect $ B_1$ and $ B_2$. But $ B_n$ intersects $ B_{n-2}$, $ B_{n-3}$ and $ B_2$. Therefore the three borders of $ B_n$ must coincide with sides of $ B_2$, $ B_{n-3}$ and $ B_{n-2}$. This makes an empty space bordered by $ B_1,B_{n-3},B_{n-2},B_n$ (see attachment C1a.gif). Note that $ B_3$ intersects $ B_1,B_{n-3},B_{n-2},B_n$. Therefore the space is exactly $ B_3$. But now $ B_3$ cannot intersect any other boxes, which is impossible since $ B_3$ is supposed to intersect $ n-2\ge5$ boxes. We get a contradiction. Therefore $ n\le6$. The following figure (C1b.gif) shows that the answer is indeed 6.

I have just realized a mistake in the above reasoning. The empty space is not exactly $ B_3$, but only a part of it. But this hole can be fixed easily. Consider $ B_{n-1}$. It must intersect $ B_1,B_2,B_3,B_{n-3}$ but not $ B_{n-2},B_n$. Clearly, we cannot put $ B_{n-1}$ anywhere. Please tell me if there are still some mistakes.

Johan Gunardi wrote: I have just realized a mistake in the above reasoning. I think you just fixed the mistake nicely, and I think your solution is now right. However, I think that your reasoning may be simplified and made more clear if you just transform it

I don't understand one thing in daniel's solution. Why can we have at most three empty intersections on each axis?

Ivob wrote: I don't understand one thing in daniel's solution. Why can we have at most three empty intersections on each axis? Here goes the complete proof of this result: Let $ [a_1,b_1], [a_2,b_2],\dots,[a_n,b_n]$ be a set of at least $ 4$ intervals (the problem is trivial for $ n\leq3$) in the real axis, such that $ [a_i,b_i]\cap[a_j,b_j]\neq\emptyset$ if $ |i - j|\neq1$ (assume cyclic notation, or modulo $ n$ notation, such that $ i = n + i$). Now, call $ A = \max\{a_i\}$, and $ B = \min\{b_i\}$, such that wlog $ a_2 = A$ (otherwise we rotate the coefficients cyclically). Then,...

Daniel's solution was very nice, and I suppose even my silly solution has its merits. Straightforward (my) approach: As above, we provide the example for $ n = 6$ and claim that $ n\ge 7$ does not work. Note that if we prove that it's impossible to arrange $ n\ge 7$ boxes so each borders exactly $ n - 3$ of the others, we are done; so suppose on the contrary that this is possible. Every box borders exactly a fixed number greater than four others; implying that if we consider a given box, for each box bordering it, there must exist another box bordering it which does not border the first - this is easy to show through contradiction. But this holds for any box, so consider one pair of the boxes which do not border each other, $ A$ and $ B$. $ A$ must also border at least three other boxes, so consider the boxes which $ A$ does not border which border these; $ C$, $ D$, and $ E$. Likewise, $ B$ must also border at least three other boxes, so consider the boxes which $ B$ does not border which border these; $ F$, $ G$, and $ H$. But there must only be two distinct boxes among $ B,C,D,E$ and similarly for $ A,F,G,H$. This now degenerates into some unfortunate casework on which of these are the same, all of which lead to a contradiction - i.e. if they're both two and two then let $ B = C,D = E,A = F,G = H$; then $ B,A$ don't border, $ D,G$, don't border. But then eachof the extremities - $ D$, $ G$ - would have to be not bordering at least three of the boxes or they would be on both sides of $ A,B$ respectively at the same time, so we have a contradiction. We can argue similarly for the other cases. Hopefully there's a slick way to bypass this which I can't find. EDIT: Actually I think the extremities argument works for all cases except when $ B=C=D=E$ or $ A=F=G=H$ (WLOG the first), in which case we can argue using the four boxes which border both $ B$ ($ =C=D=E$) and $ A$ and note that they must all border, because the ones not between any other ones would be not bordering more than two boxes otherwise. Yet this only accounts for six boxes, and any additional boxes would not border at least one of the edge ones, so we have a contradiction there too.

fwolth wrote: Daniel's solution was very nice, and I suppose even my silly solution has its merits. The solution is not silly, and unless I am mistaken it has the merit of being right! Good job fwolth!

Johan Gunardi wrote: I have just realized a mistake in the above reasoning. The empty space is not exactly $ B_3$, but only a part of it. But this hole can be fixed easily. Consider $ B_{n - 1}$. It must intersect $ B_1,B_2,B_3,B_{n - 3}$ but not $ B_{n - 2},B_n$. Clearly, we cannot put $ B_{n - 1}$ anywhere. Please tell me if there are still some mistakes. Hi, in your original post, you wrote that B3 must intersect $ B_1, B_{n-3}, B_{n-2}, B_n$. For n=7, $ B_{n-3}=B_4$ which B3 should not intersect? Am I misunderstanding something?

it was a typo, and i think it is not important because i have revised my solution.

Assume $n\ge 7$ Consider the projections of $B_{1},B_{2},...,B_{n}$ on the $x,y$ axis. Call those segments $X_{1},X_{2},...X_{n}$ $Y_{1},Y_{2},...,Y_{n}$ respectively. Now let 2 of those segments make a good pair if they are disjoint. Now since $B_{i}$ and $B_{i+1}$ are disjoint for each $i(mod n)$ we have that for each $i$ one of the pairs $(X_{i},X_{i+1}),(Y_{i},Y_{i+1})$ are good. Now WLOG we assume that there is more or the same good pairs in $X_{1},X_{2},...,X_{n}$ than there is in $Y_{1},Y_{2},...,Y_{n}$. This gives us at least $n/2$ good pairs in $X_{1},....,X_{n}$. Now choose some good pair $X_{i},X_{i+1}$(since all $X_{i},X_{k}$ where $k-i\not = 1 (mod n)$ are not good pairs) and let WLOG $X_{i}$ be left of $X_{i+1}$. Than all points which are not $X_{i-1},X_{i},X_{i+1},X_{i+2}$ contain the right end of $X_{i}$ and left end of $X_{i+1}$ so they are all connected to each other and don't form any good pairs. The only possible good pairs are from points $X_{i-2},X_{i-1},...,X_{i+3}$(Rename those to segments $a,b,c,d,e,f$ in that order. If $b,c$ and $d,e$ are connected that are atmost $3$ good pairs. If $b,c$ and $d,e$ are not connected then $b$ containt left end of $d$ (and so is connected to $a$) and $e$ contains the right end of $c$(and so is connected to $f$) which gives again at most $3$ good pairs. Now WLOG $b,c$ are connected and $d,e$ are not then $b$ contains the left end of $d$ and so is connected to $a$ giving at most $3$ good pairs. We have now proved that there are at most $3$ good pairs so $n/2\le 3$ or $n\le 6$ giving a contradiction. It is not hard to find examples for $n=1,2,3,4,5,6$

Hello everyone. I've attached an image for n=7. I'm pretty sure there's something wrong with this construction but I can't pinpoint exactly where. Perhaps someone can help me spot it. Thanks! leader wrote: Assume $n\ge 7$ Consider the projections of $B_{1},B_{2},...,B_{n}$ on the $x,y$ axis. Call those segments $X_{1},X_{2},...X_{n}$ $Y_{1},Y_{2},...,Y_{n}$ respectively. Now let 2 of those segments make a good pair if they are disjoint. Now since $B_{i}$ and $B_{i+1}$ are disjoint for each $i(mod n)$ we have that for each $i$ one of the pairs $(X_{i},X_{i+1}),(Y_{i},Y_{i+1})$ are good. Now WLOG we assume that there is more or the same good pairs in $X_{1},X_{2},...,X_{n}$ than there is in $Y_{1},Y_{2},...,Y_{n}$. This gives us at least $n/2$ good pairs in $X_{1},....,X_{n}$. Now choose some good pair $X_{i},X_{i+1}$(since all $X_{i},X_{k}$ where $k-i\not = 1 (mod n)$ are not good pairs) and let WLOG $X_{i}$ be left of $X_{i+1}$. Than all points which are not $X_{i-1},X_{i},X_{i+1},X_{i+2}$ contain the right end of $X_{i}$ and left end of $X_{i+1}$ so they are all connected to each other and don't form any good pairs. The only possible good pairs are from points $X_{i-2},X_{i-1},...,X_{i+3}$(Rename those to segments $a,b,c,d,e,f$ in that order. If $b,c$ and $d,e$ are connected that are atmost $3$ good pairs. If $b,c$ and $d,e$ are not connected then $b$ containt left end of $d$ (and so is connected to $a$) and $e$ contains the right end of $c$(and so is connected to $f$) which gives again at most $3$ good pairs. Now WLOG $b,c$ are connected and $d,e$ are not then $b$ contains the left end of $d$ and so is connected to $a$ giving at most $3$ good pairs. We have now proved that there are at most $3$ good pairs so $n/2\le 3$ or $n\le 6$ giving a contradiction. It is not hard to find examples for $n=1,2,3,4,5,6$

Rectangles 4 and 5 touch each other. However, just move the right side of rectangle 4 a bit to the left so it lies in rectangle 7 but not 5, and you have a valid solution for $n=7$.

Not quite. 7 also intersects 1, and that's not so easy to fix. There is no construction for $n = 7$.

Oh, I just read modulo $n$; I only thought $i \neq j \pm 1$.

Can someone please check this? My solution appears to be solid enough, but I believe that it may have a hole or two somewhere... edit: this is almost certainly wrong rip

The largest possible $n$ is $6$. Construction is shown below. Consider the two rectangles $B_2$, $B_{n}$. If they are both entirely on one side of $B_1$, then we see that it would be impossible to put rectangles $B_3$ and $B_{n-1}$ such that both of them intersect $1$ and one of $B_2$ or $B_n$. Then for $B_2$ there exists a side of $B_1$ for which $B_2$ is on the opposite side of that side from $B_1$, and similarly another corresponding side of $B_1$ for $B_n$. Then consider the corner formed by these two sides. If there exists two rectangles $B_i$ and $B_{i+1}$ where $4 \le i \le n-3$, then they must intersect $B_1$, $B_2$,$B_n$ which means that they must intersect at that corner of $B_1$. But this is impossible since $B_i$ doesn't intersect $B_{i+1}$. We see that such two rectangles exist if $n \ge 7$.

We claim that the largest such $n$ is $6$. The construction for $n = 6$ is easy enough, so I'll omit it. Call two non-intersect rectangles RLE to each other if one lies completely to the right of the other, and TDE to each other if one lies completely above the other. For convenience, we'll omit 'to each other' from now on. Note than any two non-intersecting cannot be both not RLE and not TDE. Note that if $A, B$ are RLE, and $C, D$ intersect both $A, B$, and if $C, D$ are non-intersecting, then $C, D$ have to be $TDE$, and cannot be $RLE$. Analogous result holds for $A, B$ that are TDE. Let $n \ge 7$. WLOG let rectangles $1, 2$ be TDE. Then as $4, 5, 6$ intersect both $1, 2$, the pairs $4, 5$ and $5, 6$ are RLE. As $1, n$ intersect both $4, 5$, the rectangles $1, n$ cannot be RLE. As $2, 3$ intersect both $5, 6$, the rectangles $2, 3$ are TDE. Then as $6, 7$ intersect both $2, 3$, the rectangles $6, 7$ have to be RLE. Case : $3, 4$ are RLE - As $6, 7$ intersect both $3, 4$, the rectangles $6, 7$ cannot be $RLE$. Contradiction. Case : $3, 4$ are TDE - As $1, n$ intersect both $3, 4$, the rectangles $1, n$ have to be $RLE$. Contradiction.

Consider a graph where the nodes are boxes, and an edge joins any two boxes that intersect. Note that if this graph is not planar, then it is clearly impossible to draw boxes in the plane with the desired property. For $n \ge 8$, it is trivial to find a $K_{3, 3}$ graph within the graph, so therefore it is not possible for $n \ge 8$ (because $K_{3, 3}$ isn't planar). For $n = 7$, if you combine $B_2$ with $B_6$ and combine $B_4$ with $B_7$, then the graph becomes $K_5$. Hence this graph is not planar, so it is also not possible for $n = 7$. For $n = 6$ see someone else's construction.

Why does planar -> not possible to draw the bloxes We now prove that $n\ge 7$ is not possible. Project each box $B_i$ to segments $X_i,Y_i$ on the $x$ and $y$ axes respectively. Note that $B_i,B_j$ intersect if and only if $X_i,X_j$ and $Y_i,Y_j$ both intersect. First, we claim that for each $i$ taken mod $n$ either $X_i,X_{i+1}$ intersect or $Y_i,Y_{i+1}$ does. Assume otherwise, then $X_{i+3},X_{i+4}$ intersects both $X_{i}$ and $X_{i+1}$ so $X_{i+3}$ and $X_{i+4}$ must both cover the space between $X_{i},X_{i+1}.$ As a result, $X_{i+3},X_{i+4}$ intersect and similarly so do $Y_{i+3},Y_{i+4}$, a contradiction. Suppose WLOG $Y_1$ and $Y_2$ intersect. Then, $X_4,X_5,X_6$ both cover the gap between $X_1$ and $X_2$ and so $Y_4,Y_5$ and $Y_5,Y_6$ are disjoint while $Y_4,Y_6$ intersect. $Y_3$ intersects $Y_1$, $Y_5$, $Y_6.$ Suppose WLOG that $Y_5$ is below $Y_4$ and $Y_6$. If $Y_6$ has a part that lies below $Y_4$ then take $B_7$ which must intersect $B_2,B_3,B_4,B_5$ but be disjoint from $B_6.$ Obviously then $B_7$ cannot intersect $B_1$ and there would be no place to put $B_3.$ Induce a similar argument for the other case, and we're done.

For $n=6$ see constructions already listed. For $n\ge 7$ note that $B_1$ and $B_3$ intersect. Consider the intersection $R$ of $B_1$ and $B_3$. Clearly there exists a side of $R$ which is intersected by both $B_5$ and $B_6$, as otherwise, there would be no place to put $B_2$. Suppose that $B_3$ intersects $B_6$ at a point farther from the corner of $B_6$ contained in $R$ compared to where $B_1$ intersects $B_6$ (here, we take the intersection which lies on the side perpendicular to the side which both $B_5$ and $B_6$ intersect $R$ at). Then note that $B_4$ is blocked from $B_1$ by $B_3$ (otherwise, it wouldn't intersect $B_7$), so we are done by symmetry. $\blacksquare$

I don't find this solution here, please see if it is wrong or not.Denote the boxes by their numbers Say $n \geq 7$.Now consider $n-2,2$ clearly they intersect each other now $n$ intersects both so should be on the same side.Now $n-3$ intersect $n,2$ so $n-3$ should be on the opposite side of $2$ w.r.t $n-2$.Now $n-1$ intersects $2,n-3$ but not $n$ and $1$ intersects $n-2,n-3,n-1$.So $1$ and $n-1$ should be on the opposite side of $2,n-2,n-3$ w.r.t $n$.Now $3$ intersects $n-2,n-1,1,n$.Now $3$ must be on the opposite side of $n-2$ w.r.t $2$.Now $n-1$ if intersects $3$ the $n-2$ height must be in a lesser extend than a lower most portion of $n-1$.Which means height of $n-2$ is less than $2$ ,but that is not possible since height of $n-2,n-3$ need to be more than $2$ so that $1$ could intersect both of them without intersecting $2$ and thus we have a contradiction. I will try to attach some documents to make this feasible to understand.

I claim the answer is $n = 6$. Construction: (see linked image) Bound: We begin with a useful lemma. First, note that all rectangles can be parameterized as two ranges, one representing the $x$ coordinates and one representing the $y$ coordinates. We say a set of rectangles "shares" an $x$ coordinate if all of their $x$ ranges contain a number, and likewise for $y$. Note that two rectangles intersect if and only if they share an $x$ coordinate and a $y$ coordinate. Lemma: If each pair of three rectangles intersect, they all intersect in one spot. Proof: We independently prove this for each coordinate. If the the second and third rectangles share an $x$ coordinate outside of the $x$ range of the first rectangle, WLOG let it be to the right. Then since both rectangles intersect the first rectangle, both of them must contain something at least as far left as the rightmost $x$ coordinate in the range of the first rectangle, and since both of them contain something to the right of the rightmost $x$ coordinate, both of them most contain the rightmost $x$ coordinate, thus all $3$ $x$ ranges meet. Repeating this for the $y$ coordinate, we see that we can find a point that is in all three rectangles, so we are done. Lemma: If each pair of $n$ rectangles intersect, they all intersect in one spot. Proof: We do this for each coordinate again, we can effectively repeat the same argument, assume inductively $n - 1$ of the $x$ ranges concur outside (WLOG the right) of the other $x$ range, then all of them contain something on the right of the rightmost part of the last $x$ range, and all of them contain something on the left of the rightmost part of the last $x$ range, so all of them contain the rightmost coordinate of the last $x$ range. Now repeat this for $y$, and make the same argument that we have a point that is in all the rectangles. Assume we have a working solution with $n \ge 7$. Take $B_1 \cdots B_7$. Note that no two boxes with adjacent indices are intersecting, and all others are, with the exception of $1,7$. In the case that $n = 7$ forces that $B_1, B_7$ are not intersecting, and $n > 7$ forces that they are. Our argument will account for both. Now rectangles $4,5$ don't intersect. However, rectangles $1,2,7$ all intersect rectangles $4,5$. If rectangles $4,5$ do not share an $x$ or a $y$ coordinate, then all three rectangles $1,2,7$ must contain every $x$ and every $y$ coordinate between rectangles $4,5$, so all three rectangles intersect, impossible. Thus rectangles $4,5$ share some coordinate, wlog let it be the $y$ coordinate. Using the lemma above on $y$ coordinates in specific, we then see that rectangles $1,3,6,4,5$ contain a common $y$ coordinate. Now WLOG assume rectangle $4$ is to the left of rectangle $5$. Now we claim that at least one of rectangles $3,6$ shares a $y$ coordinate with both rectangles $2,7$. WLOG we can assume rectangle $1$ is beneath rectangle $2$. If rectangle $7$ has any $y$ coordinate between the bounds of rectangles $1,2$, we can conclude that rectangle $6$ shares a $y$ coordinate with rectangle $7$ since it shares $y$ coordinates with both rectangles $1,2$ and thus everything in between. Otherwise, rectangle $7$ must have its lowest $y$ coordinate above the lowest $y$ coordinate of rectangle $2$. In this case, take rectangle $3$, since it contains every $y$ coordinate between rectangles $1,7$, so it must share a $y$ coordinate with rectangle $2$. Denote the rectangle from this claim as rectangle $A$. Since we established that rectangles $3,4$ share a common $y$ coordinate, they cannot share a common $x$ coordinate, likewise $5,6$ cannot share a common $x$ coordinate. Now we claim that both rectangles $3,6$ occupy some $x$ coordinate between rectangles $4,5$. Since they intersect, it suffices to do casework on the location of the intersection. Clearly it cannot be inside one of the $x$ coordinates of rectangles $4,5$ since that would result in one of $3,6$ sharing an $x$ coordinate with one of $4,5$ respectively. It cannot be to the left of rectangle $4$ because that would force rectangle $3$ to contain $x$ coordinates from rectangle $5$ (to the right of rectangle $4$) and to the left of rectangle $4$, so it would result in rectangles $3,4$ sharing an $x$ coordinate. Likewise for the intersection being to the right of rectangle $5$, we would have rectangles $5,6$ sharing an $x$ coordinate. Thus the intersection must be between rectangles $4,5$. Now take rectangle $A$, this rectangle shares a $y$ coordinate with both rectangles $2,7$ and contains at least $x$ coordinate between rectangles $4,5$. Since rectangles $2,7$ both occupy every $x$ coordinate between rectangles $4,5$, this implies rectangle $A$ intersects both rectangles $2,7$, but this should be impossible regardless of the identity of $A$, since if it were $3$ it should not have intersected $2$ and if it were $6$ it should not have intersected $7$, hence contradiction.

We show that for $n \geq 7$ this is impossible. FTSOC assume otherwise. Consider boxes $B_1, B_{n-1}.$ They intersect in a particular region. Then, consider boxes $B_3, B_4, \cdots, B_{n-3}.$ There are at least $2$ of them. Now, note that these boxes cannot be fully contained in any of $B_1, B_{n-1}$ as otherwise there is no way to place $B_n$ without it intersecting $B_1$ or $B_{n-1}.$ Therefore, there are two possible regions for where to place the blocks, as indicated in the diagram. WLOG place $B_3$ as shown in the diagram. Then $B_4$ must be placed in the other region, $B_5$ in the same region as $B_4,$ etc. Eventually we will reach $B_{n-3}.$ Now, both of our regions will have at least $1$ box (as there are at least $2$ boxes among $B_3, B_4, \cdots, B_{n-3}$), and thus it is impossible to place box $B_n$ as it must intersect both regions, and thus no matter what it will intersect both $B_1, B_{n-1}.$ Hence $n \leq 6.$ We show that this is attainable with a construction (I give credit to my friend for this:)