Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

How many nonoverlapping unit squares can (nonoverlappingly) touch one unit square? By "nonoverlapping" I mean: not sharing an interior point. By "touch" I mean: sharing a boundary point.
           SquareKissing
It seems the answer for a square in $\mathbb{R}^2$ should be $8$, and for a cube in $\mathbb{R}^3$, $26$.

But a 1999 paper by Larman and Zong,

"On the Kissing Numbers of Some Special Convex Bodies." Discrete Comput Geom 21:233–242 (1999). (Springer link)

says

"In this note we determine the kissing numbers of octahedra, rhombic dodecahedra and elongated octahedra. In fact, besides balls and cylinders, they are the only convex bodies whose kissing numbers are exactly known."

In that paper, they were interested in the translative kissing number and the lattice kissing number, whereas I want to consider arbitrary orientations of each square/cube. Despite the quote above, it seems this should be known...?


Update (30Dec12) The following explains (I believe) the $0.82$ in Henry Cohn's comment, leading to his proof for $\le 9$ in $\mathbb{R}^2$:
           Henry Cohn Proof

share|improve this question
7  
For translative kissing numbers, it's easy: for squares, all the neighbors must be contained within the figure on the right above, and there are only eight units of area for them. I don't know how to prove the general case (or even whether it's known). For squares, it's not hard to prove an upper bound of 9. Specifically, you can look at how much of that figure is covered by each neighboring square. A short calculation shows that the worst case scenario is meeting at a 45 degree angle, covering area $0.82\dots$. Since $8/0.82 < 8/0.8 = 10$, at most nine squares can fit. –  Henry Cohn Dec 30 '12 at 3:10
    
I bet you could rule out nine squares by a more elaborate case analysis, but I haven't done it, and this approach doesn't seem likely to lead to a pleasant proof or a generalization to higher dimensions. –  Henry Cohn Dec 30 '12 at 3:14
    
Looking at Figure 1 for example, one could try to cut what is too far from the red square and paste it in the lost space. Whether this can be done in a natural way I don't know. –  François Brunault Dec 30 '12 at 9:33
add comment

2 Answers 2

up vote 17 down vote accepted

The square case was posed as a problem at Leningrad (now St. Petersburg) high school math olympiad in 1963. I wrote a solution of this problem for the volume "St. Petersburg mathematical olympiads 1961-1993", D.V.Fomin, K.P.Kokhas eds., Lan' Publ. 2007 (in Russian), it is Problem 63.31 in that book.

Here is the original very detailed draft of the solution from my archive (only a sketch made it into the final book). It is in Russian but the pictures and formulae might be enough to follow the proof. Up to elementary but cumbersome case chasing, the solution is the following.

Consider the boundary of the twice bigger square with the same center and parallel sides. It is a broken line of length 8. It turns out that each of the kissing squares takes away a piece of length at least 1 from this broken line. Hence there are at most 8 kissing squares (and furthermore one analyse the equality case).
           Figs from Russian description
           (Snapshots of the figures added by J.O'Rourke)

The proof of the fact that the length of the intersection is at least 1 is essentially an exhaustion of cases, each of which is trivial. It is helpful to observe that the length of the intersection is a piecewise linear function of the relative position of the squares (if the orientation is fixed), so one has to consider only "borderline" positions (i.e. those where one of the corners is on one of the lines). This leaves about 10 cases to consider.

share|improve this answer
    
That's beautiful! –  Henry Cohn Dec 31 '12 at 15:15
2  
@Sergei: It is natural to wonder if this beautiful proof could extend to cubes in $\mathbb{R}^3$... –  Joseph O'Rourke Dec 31 '12 at 18:43
    
Very nice ... elegant! –  Kevin R. Vixie Dec 31 '12 at 18:54
    
Beautiful. And a big thank-you to Joseph for putting 7 figures into one and post it here! –  Yuichiro Fujiwara Dec 31 '12 at 19:04
2  
I thought briefly about the bigger annulus and boundary coverage, but didn't play with that long enough to try the smaller annulus. Hardy would say I am like the bear in the zoo, not taking a good idea far enough. The story goes that he was upset with Polya, who had disappointed him by not carrying an idea far enough. He visited the zoo, observing the bear fiddling with the lock on the cage but giving up after a short while, upon which Hardy said "He is like Polya. He has excellent ideas, but he does not carry them out." Again, very nice solution Sergei! –  Kevin R. Vixie Dec 31 '12 at 19:07
add comment

Here is an answer for the square case: Following what Henry did, using matlab/octave calculations, one gets that 8 is the maximum.

Synopsis: you can lose a bit more than 11% of the area and still have an area that divides into 8 less than 9 times. Now note that we don't lose that much area from the intersection of the tipped square and the square annulus unless the tip of the square is between approx 17 and 73 degrees. We are also guaranteed to have at least one side of the tipped square at least .5 units from a corner of the central square. (see the figure below -- the angle bounds are approximate)

alt text

Now, a bit of thought and playing around will convince you that the area red rectangle is a lower bound on the inaccessible area to other squares in the annulus, thus that area can be added back to the lost area.

(I did the calculations twice, found a simple arithmetic error that did not effect conclusion -- I am pretty sure this is right.)

share|improve this answer
add comment

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.