35
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 10
    $\begingroup$ 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. $\endgroup$
    – Henry Cohn
    Commented Dec 30, 2012 at 3:10
  • 1
    $\begingroup$ 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. $\endgroup$
    – Henry Cohn
    Commented Dec 30, 2012 at 3:14
  • $\begingroup$ 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. $\endgroup$
    – François Brunault
    Commented Dec 30, 2012 at 9:33
  • $\begingroup$ See here: math.stackexchange.com/q/1085687/29780 for a similar question: how many nonoverlapping unit squares can overlap one unit square? $\endgroup$
    – Erel Segal-Halevi
    Commented Aug 13, 2015 at 6:29
  • $\begingroup$ It seems that the answer is also 8, but the proof of @SergeiIvanov does not work because the middle square does not have to cross the twice-bigger square. $\endgroup$
    – Erel Segal-Halevi
    Commented Aug 13, 2015 at 6:34

3 Answers 3

Reset to default
33
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ That's beautiful! $\endgroup$
    – Henry Cohn
    Commented Dec 31, 2012 at 15:15
  • 6
    $\begingroup$ @Sergei: It is natural to wonder if this beautiful proof could extend to cubes in $\mathbb{R}^3$... $\endgroup$
    – Joseph O'Rourke
    Commented Dec 31, 2012 at 18:43
  • $\begingroup$ Very nice ... elegant! $\endgroup$
    – Kevin R. Vixie
    Commented Dec 31, 2012 at 18:54
  • $\begingroup$ Beautiful. And a big thank-you to Joseph for putting 7 figures into one and post it here! $\endgroup$
    – Yuichiro Fujiwara
    Commented Dec 31, 2012 at 19:04
  • 2
    $\begingroup$ 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! $\endgroup$
    – Kevin R. Vixie
    Commented Dec 31, 2012 at 19:07
8
$\begingroup$

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 (source)

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.)

Improve this answer
$\endgroup$
3
$\begingroup$

The problem for squares may have been settled first by J W T Youngs, A lemma on squares, American Math Monthly 46 (1939) 20-22. Youngs' proof can also be found in A M Gleason et al., The William Lowell Putnam Mathematical Competition – Problems and Solutions: 1938-1964, pp. 461-463, and in R Honsberger, Mathematical Morsels, pp. 82-89. A discussion of the history, and another proof, will be found in M S Klamkin et al., The kissing number of the square, Mathematics Magazine 68 (1995) 128-133.

Likuan Zhao, The kissing number of the regular polygon, Discrete Mathematics 188 (1998) 293-296, lets $P_n$ be a regular polygon with $n$ sides, and $k(n)$ its kissing number. After citing earlier results $k(3)=12$, $k(4)=8$, and $k(6)=6$, the paper establishes $k(n)=6$ for $n>6$. Zhao and Junqin Xu, The kissing number of the regular pentagon, Discrete Math 252 (2002) 293-298, finish it off by proving $k(5)=6$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .