Moving sofa problem

Last updated
Unsolved problem in mathematics:
What is the largest area of a shape that can be maneuvered through a unit-width L-shaped corridor?

In mathematics, the moving sofa problem or sofa problem is a two-dimensional idealization of real-life furniture-moving problems and asks for the rigid two-dimensional shape of the largest area that can be maneuvered through an L-shaped planar region with legs of unit width. [1] The area thus obtained is referred to as the sofa constant. The exact value of the sofa constant is an open problem. The leading solution, by Joseph L. Gerver, has a value of approximately 2.2195. In November 2024, Jineon Baek posted an arXiv preprint claiming that Gerver's value is optimal, which if true, would solve the moving sofa problem. [2]

Contents

History

The first formal publication was by the Austrian-Canadian mathematician Leo Moser in 1966, [3] although there had been many informal mentions before that date. [1]

Bounds

Work has been done to prove that the sofa constant (A) cannot be below or above specific values (lower bounds and upper bounds).

Lower

The Hammersley sofa has area 2.2074 but is not the largest solution Hammersley sofa animated.gif
The Hammersley sofa has area 2.2074 but is not the largest solution
Gerver's sofa of area 2.2195 with 18 curve sections Gerver.svg
Gerver's sofa of area 2.2195 with 18 curve sections
A telephone handset, a closer match than a sofa to Gerver's shape Telefono automatico a batteria centrale (BCA) - Museo scienza tecnologia Milano D0955 10.jpg
A telephone handset, a closer match than a sofa to Gerver's shape

A lower bound on the sofa constant can be proven by finding a specific shape of a high area and a path for moving it through the corner. is an obvious lower bound. This comes from a sofa that is a half-disk of unit radius, which can slide up one passage into the corner, rotate within the corner around the center of the disk, and then slide out the other passage.

In 1968, John Hammersley stated a lower bound of . [4] This can be achieved using a shape resembling an old-fashioned telephone handset, consisting of two quarter-disks of radius 1 on either side of a 1 by rectangle from which a half-disk of radius has been removed. [5] [6]

In 1992, Joseph L. Gerver of Rutgers University described a sofa with 18 curve sections, each taking a smooth analytic form. This further increased the lower bound for the sofa constant to approximately 2.2195 (sequence A128463 in the OEIS ). [7] [8]

Upper

Hammersley stated an upper bound on the sofa constant of at most . [4] [1] [9] Yoav Kallus and Dan Romik published a new upper bound in 2018, capping the sofa constant at . Their approach involves rotating the corridor (rather than the sofa) through a finite sequence of distinct angles (rather than continuously) and using a computer search to find translations for each rotated copy so that the intersection of all of the copies has a connected component with as large an area as possible. As they show, this provides a valid upper bound for the optimal sofa, which can be made more accurate using more rotation angles. Five carefully chosen rotation angles lead to the stated upper bound. [10]

Ambidextrous sofa

Romik's ambidextrous sofa Romik.svg
Romik's ambidextrous sofa

A variant of the sofa problem asks the shape of the largest area that can go around both left and right 90-degree corners in a corridor of unit width (where the left and right corners are spaced sufficiently far apart that one is fully negotiated before the other is encountered). A lower bound of area approximately 1.64495521 has been described by Dan Romik. 18-curve sections also describe his sofa. [11] [12]

See also

Related Research Articles

<span class="mw-page-title-main">Circumference</span> Perimeter of a circle or ellipse

In geometry, the circumference is the perimeter of a circle or ellipse. The circumference is the arc length of the circle, as if it were opened up and straightened out to a line segment. More generally, the perimeter is the curve length around any closed figure. Circumference may also refer to the circle itself, that is, the locus corresponding to the edge of a disk. The circumference of a sphere is the circumference, or length, of any one of its great circles.

<span class="mw-page-title-main">Squaring the circle</span> Problem of constructing equal-area shapes

Squaring the circle is a problem in geometry first proposed in Greek mathematics. It is the challenge of constructing a square with the area of a given circle by using only a finite number of steps with a compass and straightedge. The difficulty of the problem raised the question of whether specified axioms of Euclidean geometry concerning the existence of lines and circles implied the existence of such a square.

In number theory, Skewes's number is any of several large numbers used by the South African mathematician Stanley Skewes as upper bounds for the smallest natural number for which

<span class="mw-page-title-main">Sphere packing</span> Geometrical structure

In geometry, a sphere packing is an arrangement of non-overlapping spheres within a containing space. The spheres considered are usually all of identical size, and the space is usually three-dimensional Euclidean space. However, sphere packing problems can be generalised to consider unequal spheres, spaces of other dimensions or to non-Euclidean spaces such as hyperbolic space.

<span class="mw-page-title-main">Heilbronn triangle problem</span> On point sets with no small-area triangles

In discrete geometry and discrepancy theory, the Heilbronn triangle problem is a problem of placing points in the plane, avoiding triangles of small area. It is named after Hans Heilbronn, who conjectured that, no matter how points are placed in a given area, the smallest triangle area will be at most inversely proportional to the square of the number of points. His conjecture was proven false, but the asymptotic growth rate of the minimum triangle area remains unknown.

<span class="mw-page-title-main">Reuleaux tetrahedron</span> Shape formed by intersecting four balls

The Reuleaux tetrahedron is the intersection of four balls of radius s centered at the vertices of a regular tetrahedron with side length s. The spherical surface of the ball centered on each vertex passes through the other three vertices, which also form vertices of the Reuleaux tetrahedron. Thus the center of each ball is on the surfaces of the other three balls. The Reuleaux tetrahedron has the same face structure as a regular tetrahedron, but with curved faces: four vertices, and four curved faces, connected by six circular-arc edges.

In mathematics, a Ramanujan prime is a prime number that satisfies a result proven by Srinivasa Ramanujan relating to the prime-counting function.

In complex analysis, a branch of mathematics, Bloch's theorem describes the behaviour of holomorphic functions defined on the unit disk. It gives a lower bound on the size of a disk in which an inverse to a holomorphic function exists. It is named after André Bloch.

<span class="mw-page-title-main">Q-function</span> Statistics function

In statistics, the Q-function is the tail distribution function of the standard normal distribution. In other words, is the probability that a normal (Gaussian) random variable will obtain a value larger than standard deviations. Equivalently, is the probability that a standard normal random variable takes a value larger than .

<span class="mw-page-title-main">Circle packing</span> Field of geometry closely arranging circles on a plane

In geometry, circle packing is the study of the arrangement of circles on a given surface such that no overlapping occurs and so that no circle can be enlarged without creating an overlap. The associated packing density, η, of an arrangement is the proportion of the surface covered by the circles. Generalisations can be made to higher dimensions – this is called sphere packing, which usually deals only with identical spheres.

<span class="mw-page-title-main">Introduction to systolic geometry</span> Non-technical introduction to systolic geometry

Systolic geometry is a branch of differential geometry, a field within mathematics, studying problems such as the relationship between the area inside a closed curve C, and the length or perimeter of C. Since the area A may be small while the length l is large, when C looks elongated, the relationship can only take the form of an inequality. What is more, such an inequality would be an upper bound for A: there is no interesting lower bound just in terms of the length.

In mathematics, systolic inequalities for curves on surfaces were first studied by Charles Loewner in 1949. Given a closed surface, its systole, denoted sys, is defined to be the least length of a loop that cannot be contracted to a point on the surface. The systolic area of a metric is defined to be the ratio area/sys2. The systolic ratio SR is the reciprocal quantity sys2/area. See also Introduction to systolic geometry.

<span class="mw-page-title-main">Gauss circle problem</span> How many integer lattice points there are in a circle

In mathematics, the Gauss circle problem is the problem of determining how many integer lattice points there are in a circle centered at the origin and with radius . This number is approximated by the area of the circle, so the real problem is to accurately bound the error term describing how the number of points differs from the area. The first progress on a solution was made by Carl Friedrich Gauss, hence its name.

<span class="mw-page-title-main">Hadwiger conjecture (combinatorial geometry)</span>

In combinatorial geometry, the Hadwiger conjecture states that any convex body in n-dimensional Euclidean space can be covered by 2n or fewer smaller bodies homothetic with the original body, and that furthermore, the upper bound of 2n is necessary if and only if the body is a parallelepiped. There also exists an equivalent formulation in terms of the number of floodlights needed to illuminate the body.

In convex geometry, the Mahler volume of a centrally symmetric convex body is a dimensionless quantity that is associated with the body and is invariant under linear transformations. It is named after German-English mathematician Kurt Mahler. It is known that the shapes with the largest possible Mahler volume are the balls and solid ellipsoids; this is now known as the Blaschke–Santaló inequality. The still-unsolved Mahler conjecture states that the minimum possible Mahler volume is attained by a hypercube.

<span class="mw-page-title-main">Smoothed octagon</span> Two-dimensional shape

The smoothed octagon is a region in the plane found by Karl Reinhardt in 1934 and conjectured by him to have the lowest maximum packing density of the plane of all centrally symmetric convex shapes. It was also independently discovered by Kurt Mahler in 1947. It is constructed by replacing the corners of a regular octagon with a section of a hyperbola that is tangent to the two sides adjacent to the corner and asymptotic to the sides adjacent to these.

<span class="mw-page-title-main">Moser's worm problem</span> Unsolved geometry problem about planar regions

Moser's worm problem is an unsolved problem in geometry formulated by the Austrian-Canadian mathematician Leo Moser in 1966. The problem asks for the region of smallest area that can accommodate every plane curve of length 1. Here "accommodate" means that the curve may be rotated and translated to fit inside the region. In some variations of the problem, the region is restricted to be convex.

<span class="mw-page-title-main">Opaque set</span> Shape that blocks all lines of sight

In discrete geometry, an opaque set is a system of curves or other set in the plane that blocks all lines of sight across a polygon, circle, or other shape. Opaque sets have also been called barriers, beam detectors, opaque covers, or opaque forests. Opaque sets were introduced by Stefan Mazurkiewicz in 1916, and the problem of minimizing their total length was posed by Frederick Bagemihl in 1959.

<span class="mw-page-title-main">Lebesgue's universal covering problem</span> Unsolved geometry problem

Lebesgue's universal covering problem is an unsolved problem in geometry that asks for the convex shape of smallest area that can cover every planar set of diameter one. The diameter of a set by definition is the least upper bound of the distances between all pairs of points in the set. A shape covers a set if it contains a congruent subset. In other words the set may be rotated, translated or reflected to fit inside the shape.

Dan Romik is a mathematician and a professor of mathematics at the University of California, Davis. He is known for contributions to probability theory and discrete mathematics.

References

  1. 1 2 3 Wagner, Neal R. (1976). "The Sofa Problem" (PDF). The American Mathematical Monthly. 83 (3): 188–189. doi:10.2307/2977022. JSTOR   2977022. Archived from the original (PDF) on 2015-04-20. Retrieved 2009-07-25.
  2. Baek, Jineon (2024-11-29). "Optimality of Gerver's Sofa". arXiv: 2411.19826 [math.MG].
  3. Moser, Leo (July 1966). "Problem 66-11, Moving furniture through a hallway". SIAM Review . 8 (3): 381. doi:10.1137/1008074. JSTOR   2028218.
  4. 1 2 J. M. Hammersley (1968). "On the enfeeblement of mathematical skills by 'Modern Mathematics' and by similar soft intellectual trash in schools and universities". Bulletin of the Institute of Mathematics and Its Applications. 4: 66–85. See Appendix IV, Problems, Problem 8, p. 84.
  5. Croft, Hallard T.; Falconer, Kenneth J.; Guy, Richard K. (1994). Halmos, Paul R. (ed.). Unsolved Problems in Geometry . Problem Books in Mathematics; Unsolved Problems in Intuitive Mathematics. Vol. II. Springer-Verlag. ISBN   978-0-387-97506-1 . Retrieved 24 April 2013.
  6. Finch, Steven, Moving Sofa Constant, Mathcad Library (includes a diagram of Gerver's sofa).
  7. Gerver, Joseph L. (1992). "On Moving a Sofa Around a Corner". Geometriae Dedicata . 42 (3): 267–283. doi:10.1007/BF02414066. ISSN   0046-5755. S2CID   119520847.
  8. Weisstein, Eric W. "Moving sofa problem". MathWorld .
  9. Stewart, Ian (January 2004). Another Fine Math You've Got Me Into... Mineola, N.Y.: Dover Publications. ISBN   0486431819 . Retrieved 24 April 2013.
  10. Kallus, Yoav; Romik, Dan (December 2018). "Improved upper bounds in the moving sofa problem". Advances in Mathematics . 340: 960–982. arXiv: 1706.06630 . doi:10.1016/j.aim.2018.10.022. ISSN   0001-8708. S2CID   5844665.
  11. Romik, Dan (2017). "Differential equations and exact solutions in the moving sofa problem". Experimental Mathematics. 26 (2): 316–330. arXiv: 1606.08111 . doi:10.1080/10586458.2016.1270858. S2CID   15169264.
  12. Romik, Dan. "The moving sofa problem - Dan Romik's home page". UCDavis. Retrieved 26 March 2017.