# Translative Packing of Unit Squares into Squares

Authors: Janusz Januszewski
Journal: International Journal of Mathematics and Mathematical Sciences
 (2012)

---

## Abstract

Every collection ofn (arbitrary-oriented) unit squares admits a translative packing into any square of side length 2.5·n.


---

## Body

## 1. Introduction

Leti be a positive integer, let 0≤αi<π/2, and let a rectangular coordinate system in the plane be given. One of the coordinate system's axes is called x-axis. Denote by S(αi) a square in the plane with sides of unit length and with the angle between the x-axis and a side of S(αi) equal to αi. Furthermore, by I(s) denote a square with side length s and with sides parallel to the coordinate axes.We say that a collection ofn unit squares S(α1),…,S(αn) admits a packing into a set C if there are rigid motions σ1,…,σn such that the squares σiS(αi) are subsets of C and that they have mutually disjoint interiors. A packing is translative if only translations are allowed as the rigid motions.For example, two unit squares can be packed intoI(2), but they cannot be packed into I(2-ϵ) for any ϵ>0. Three and four unit squares can be packed into I(2) as well (see Figure 1(a)). Obviously, two, three, or four squares S(0) can be translatively packed into I(2). If either α1≠0 or α2≠0, then two squares S(α1) and S(α2) cannot be translatively packed into I(2). The reason is that for every α≠0, the interior of any square S(α) translatively packed into I(2) covers the center of I(2) (see Figure 1(b)).(a)
(b)The problem of packing of unit squares into squares (with possibility of rigid motions) is a well-known problem (e.g., see [1–3]). The best packings are known for several values of n. Furthermore, for many values of n, there are good packings that seem to be optimal.In this paper, we propose the problem of translative packing of squares. Denote bysn the smallest number s such that any collection of n unit squares S(α1),…,S(αn) admits a translative packing into I(s). The problem is to find sn for n=1,2,3,…. Obviously, sn>n. By [4, Theorem 7], we deduce that limn→∞sn/n=1. We show that
(1.1)sn≤2.5⋅n.


## 2. Packing into Squares

Example 2.1.
We haves1=2. Each unit square can be translatively packed into I(2), but it is impossible to translatively pack S(π/4) into I(2-ϵ) for any ϵ>0.Example 2.2.
We haves2=5 (see [5]). Here, we only recall that two squares: S(arctan1/2) and S(arctan2) cannot be translatively packed into I(5-ϵ) for any ϵ>0 (see Figure 2(a)).(a)
(b)Example 2.3.
We haves4=22. Four squares S(π/4) admit a translative packing into I(22) (see Figure 3, where 2/2≤λ≤32/2). In Figure 3(b) and Figure 4(a), we illustrate the cases when λ=2 and λ=2/2, respectively. By these three pictures, we conclude that four squares S(π/4) cannot be translatively packed into I(22-ϵ), for any ϵ>0. Consequently,  s4≥22. On the other hand, four circles of radius 2/2 can be packed into I(22) (see Figure 4(b)). Since any square S(αi) can be translatively packed into a circle of radius 2/2, it follows that s4≤22.(a)
(b)(a)
(b)Lemma 2.4 (see [5]).
Every unit square can be translatively packed into any isosceles right triangle with legs of length5.Theorem 2.5.
Ifn≥3, then sn≤((10+5)/23)·n.Proof.
LetS(α1),S(α2),andS(α3) be unit squares and put
(2.1)λ1=12(10+5).
Three congruent quadrangles Q1,Q2,andQ3, presented in Figure 2(b), of side lengths λ1,5,2.5, and  λ2=λ1-5, are contained in I(λ1). Since the length of the diagonal of S(αi) is smaller than 2.5, by Lemma 2.4 we deduce that S(αi) can be translatively packed into Qi for i=1,2,3. Consequently, the squares S(α1),S(α2),andS(α3) can be translatively packed into I(s) and
(2.2)s3≤λ1=10+523⋅3.
Now assume that4≤n≤16.
Denote bymn the smallest number s such that n circles of unit radius can be packed into I(s). The problem of minimizing the side of a square into which n congruent circles can be packed is a well-known question. The values of  mn are known, among others, for n≤16 (see Table 2.2.1 in [6] or [7]). We know that
(2.3)m4=4,m5<4.83,m6<5.33,m7<5.74,m8<m9=6,m10<6.75,m11<7.03,m12<m13<7.47,m14<m15<m16=8.
Since each unit square is contained in a circle of radius2/2, it follows that  n unit squares can be translatively packed into I(2mn/2). It is easy to verify that
(2.4)sn≤22mn<10+523⋅n,
for n=4,5,…,16.
Finally, assume thatn>16. We use two lattice arrangements of circles.
There exists an integerm≥4 such that either
(2.5)m2<n≤m2+morm2+m<n≤(m+1)2.
Obviously,m2 circles of radius 2/2 can be packed into I(2m) (see Figure 5(a)). Moreover, m2+m circles of radius 2/2 can be packed into I(2m+2/2) (see Figure 5(b)); it is easy to check that
(2.6)(3m+2)⋅22<2m+22,
provided m≥4.
Ifm2+1≤n≤m2+m, then
(2.7)sn≤2m+22≤2⋅n-1+22<10+523⋅n.
Ifm2+m+1≤n≤(m+1)2, then sn≤2(m+1). Since m2+m+1≤n, it follows that m≤(1/2)4n-3-1/2. Thus,
(2.8)sn≤2(124n-3+12)<10+523⋅n.(a)
(b)By Theorem2.5, Examples 2.1  and 2.2, we conclude the following result.Corollary 2.6.
Every collection ofn unit squares admits a translative packing into any square of area 2.5n, that is, sn≤2.5·n. Furthermore, s2=5.Forn≥1980, the following upper bound is better than the bound presented in Theorem 2.5.Lemma 2.7.
Letn be a positive integer, and let k be the greatest integer not over n4. Then
(2.9)sn≤(1+π2k)[2(1+k)+n+2k2-4k+2].Proof.
Assume thatS(α1),…,S(αn) is a collection of n unit squares. Let k be the greatest integer not over n4, let η=π/2k, and put
(2.10)ζ=(1+η)[2(1+k)+n+2k2-4k+2].
For eachi∈{1,…,n}, there exists j∈{1,2,…,k} such that
(2.11)(j-1)η≤αi<jη.
Putφ=αi-(j-1)η. We have 0≤φ<η. Moreover, let λ3 and λ4 denote the lengths of the segments presented in Figure 6(a). Since
(2.12)λ3+λ4=cos⁡φ+sin⁡φ≤1+φ<1+η,
it follows that S(αi) is contained in a square Pi with side length 1+η and with the angle between the x-axis and a side of Pi equal to (j-1)η. We say that Pi is a j-square.
To prove Lemma2.7, it suffices to show that P1,…,Pn can be translatively packed into I(ζ). Denote by Aj the total area of the j-squares, for j=1,…,k. Obviously,
(2.13)∑j=1k‍Aj=n(1+η)2.
Put(2.14)hj=Ajζ-22(1+η)+22(1+η),
for j=1,…,k. Observe that
(2.15)∑j=1k‍hj=A1+⋯+Akζ-22(1+η)+2k2(1+η).
Thus,(2.16)∑j=1k‍hj=n(1+η)2ζ-22(1+η)+2k2(1+η).
The equation(2.17)n(1+η)2x-22(1+η)+2k2(1+η)=x
is equivalent to
(2.18)x2-x⋅22(1+η)(k+1)+(8k-n)(1+η)2=0.
It is easy to verify thatx=ζ is a solution of this equation. Consequently,
(2.19)∑j=1k‍hj=n(1+η)2ζ-22(1+η)+2k2(1+η)=ζ.
We divideI(ζ) into k rectangles R1,…,Rk, where Rj is a rectangle of side lengths ζ and hj. Since the diagonal of each Pi equals 2(1+η) and
(2.20)Aj=[ζ-22(1+η)][hj-22(1+η)],
it follows that all j-squares admit a translative packing into Rj for j=1,…,k (see Figure 6(b)). Hence, P1,…,Pn, and consequently S(α1),…,S(αn) can be translatively packed into I(ζ). This implies that sn≤ζ.(a)
(b)Theorem 2.8.
Letn be a positive integer. Then
(2.21)sn≤n+(2+π2)n4+O(1),
as n→∞.Proof.
Letk be the greatest integer not over n4. Since
(2.22)n+2k2-4k+2<n+2k2≤n+2n<n+1,
by Lemma 2.7, it follows that, for n>1,
(2.23)sn<(1+π2n4-2)[2(1+n4)+n+1]=n+(2+π2)n4+(2+1)(π2+1)+π+π2n4-1.



---

*Source: 613201-2012-06-27.xml*