Five Geometry Problems That Look Simple but Remain Unsolved
Square Packing
A unit square is a square with a side length of one unit. Suppose you have a collection of some number of unit squares, which we’ll call n. You want to pack all these squares into a large square enclosure with no overlap. For a given number of unit squares n, what is the smallest enclosure you can make? We express the size of the enclosure using its side length, a. This is known as the square packing problem.
The most trivial case is when n is a perfect square (1, 4, 9, etc.). Then you can simply arrange all of your unit squares into a grid pattern with a square border, and this border is the enclosure, having side length √n. Many other values of n yield simple solutions as well, where the squares are similarly aligned to the grid, like with 2 or 3 squares.
5 squares is an interesting case. One square is placed at a 45° angle from the grid and the other four are placed around it, resulting in an enclosure side length of a = 2 + 1/√2, about 2.707. The solution for 10 squares is simply an extension of the solution for 5 squares.
Despite the square packing problem’s apparent simplicity, much about it is still unknown. It remains unsolved for some rather small values of n, the smallest two being n = 11 and n = 17. Approximations have been obtained in these cases, those being a ≈ 3.88 and a ≈ 4.68 respectively, and giving some bizarre-looking packings.
Bellman’s Lost in a Forest Problem
Imagine being lost in a forest. You don’t know where you are or what direction you’re facing, but you do know the exact shape and size of the forest. What is the best path to take to ensure the lowest escape time in the worst-case scenario?
This problem was first posed by American mathematician Richard E. Bellman. It was originally about unbounded regions like an infinite strip between two parallel lines or a half-plane (the region of a plane on one side of a line). However, mathematicians later investigated bounded regions as well.
There is no known general solution to this problem. Such a solution would be some kind of algorithm where you plug in the forest’s shape and size and it gives you back the best path of escape. However, some specific cases have been proven. One possibility is that a forest is “fat,” meaning that the best escape route is a linear path: just walk in a straight line. For instance, every regular polygon with at least four sides is fat. If you let the number of sides of a regular polygon approach infinity, the sequence of shapes approaches a circle, so a circle is also fat.
The only regular polygon with no known solution is the equilateral triangle.
The lost-in-a-forest problem is part of a group of optimization problems in geometry that have practical uses when it comes to search strategies. However, there do not seem to be any real-world applications of this specific problem to actually being lost in a forest. If that happens, you should usually stay put and wait for searchers.
Ulam’s Packing Conjecture
Ulam’s packing conjecture is another packing problem, though this one is in three dimensions instead of two. It concerns the packing of identical solids in a three-dimensional space.
To begin, we must define convex solids. A convex solid is a solid figure where any pair of points in the solid is connected by a line segment that is also completely contained in the solid. For instance, a ball is a convex solid because if you choose any two points inside the ball and draw the line segment between them, the line segment will also be entirely inside the ball. On the other hand, a solid torus (a doughnut shape) is not convex, because for example the line segment between two opposite points of the solid torus will pass through empty space.
Now imagine taking a bunch of identical convex solids and using them to fill a space, packing them as tightly as possible with no overlap. The packing density is the proportion of the space that is occupied by the solids. If the solids are packed as tightly as they can be, their density is called the optimal packing density. Of course, we can’t take the volume of infinitely many solids and divide it by the volume of the infinite space they occupy. Instead, we consider the proportion of occupied volume in a very large space, then take the limit as the volume of this space approaches infinity.
Ulam’s packing conjecture, named for Polish mathematician Stanisław Ulam (where “conjecture” is math-speak for an educated guess), states that the ball has the smallest optimal packing density of any convex solid. In other words, if you want to fill up a space with a bunch of identical solids, then balls are the least efficient way to do it.
A related result called the Kepler conjecture says that the optimal packing density for balls is π/(3√2), or equivalently τ/(6√2), approximately 74%. As for Ulam’s packing conjecture, experimenting with many different convex solids has given confidence that the conjecture is true, but no proof has been devised.
Lebesgue’s Universal Covering Problem
You may already know what the diameter of a circle is: it’s the largest possible distance from one point on the circle to another. Similarly, the diameter of any shape can be defined as the largest possible distance from one point on that shape to another. For instance, the diameter of a unit square is √2, since that’s the distance between opposite vertices of the unit square, and those are the points that are farthest apart.
Let’s say we’re in 2D and we have some kind of convex shape that can contain any shape with a diameter of 1. Let’s call the first shape the “cover,” since it can be used to cover up any of the diameter-1 shapes. The diameter-1 shapes can be translated, rotated, and reflected (slid, spun around, and flipped, respectively) to fit in the cover. Lebesgue’s universal covering problem asks: what is the smallest area that this cover can have?
The problem is named after French mathematician Henri Lebesgue, who first posed it in 1914 in a letter to Hungarian-Danish mathematician Gyula Pál. Pál analyzed the problem in a 1920 paper, and his analysis involved curves of constant width. A curve of constant width is a shape with the same width in all directions. The most well-known example is the circle, but there are infinitely many more, such as the Reuleaux triangle. The paper showed that if you simply find a cover for all curves of constant width with a diameter of 1, then it will also cover every possible shape of diameter 1.
Pál also showed his best solution for such a cover: a hexagon with two corners snipped off. Its area is 2 − 2/√3, about 0.8454. This upper bound was improved to about 0.8441 in 1936, then to about 0.8441 in 2018. The best known lower bound is about 0.832, meaning no cover could ever have an area less than this.
Moser’s Worm Problem
Imagine a curve in the plane with a length of 1. You could think of it as a worm or a piece of string. Similar to Lebesgue’s universal covering problem, Moser’s worm problem asks for the smallest area of a region that can contain every such curve. Once again, translations, rotations, and reflections are allowed.
For this problem, it is relatively easy to find some simple covers. One example is a disc of radius 1/2, where any curve of length 1 can be covered by placing its midpoint at the disc’s center. This disc has an area of π/4, about 0.785. An even smaller cover is a rhombus with angle measures of 60° and 120° and a long diagonal that’s 1 unit long, with an area of 1/√3, about 0.577. (And no, this is not the Euler-Mascheroni constant.)
When approaching this problem, one possibility to consider is that a solution doesn’t even exist. For instance, what if we found out that a cover can be constructed with a given area if and only if that area is greater than some number, say 0.5? In that case, our cover’s area could be 0.51 or 0.501 and so on, but never exactly 0.5. Since you could just keep getting closer and closer to 0.5, approaching it without reaching it, there would be no smallest area.
However, if we only consider convex covers, then the Blaschke selection theorem tells us that a smallest convex cover must exist. Though the solution to this problem is unknown, some bounds have been obtained both in the general case and the convex case. The general case has an upper bound of about 0.26, while the convex case has a lower bound of about 0.23 and an upper bound of about 0.27.
A 30° unit-radius circular sector with an area of π/12 (about 0.2618) was conjectured to be a convex cover by John Wetzel in the 1970s. Proofs were independently claimed in 2017 and 2021. If these are confirmed, this will be a new upper bound for the area of a convex cover.
Kobon’s Triangle Problem
If you draw 3 lines (infinite lines, not line segments) in a plane, you can make them form a triangle. If you draw 4 lines in a plane, you can make them form a maximum of 2 triangles. For 5 lines, the maximum jumps up to 5 triangles.
So in general, for k lines, what is the largest possible number of non-overlapping triangles formed, N(k)? This problem is called Kobon’s triangle problem, named after Kobon Fujimura.
A known upper bound for N(k) exists: ⌊k(k − 2)/3⌋, found by Saburo Tamura. Here the floor function takes in a number and returns the greatest integer less than or equal to that number (basically, it rounds down). For instance, if k = 4, this expression gives ⌊4 × 2/3⌋ = ⌊8/3⌋ = ⌊2.667⌋ = 2.
Exact solutions are known for numbers of lines from 3 to 9, as well as 13, 15, and 17. In the case of the first unsolved number of lines, k = 10, the upper bound is 26 triangles, whereas the best solution obtained so far is 25.
Further Reading
- Square Packing in a Square on Wikipedia
- Lebesgue’s Universal Covering Problem on MathWorld
- Moser’s Worm Problem on MathWorld
- Curves of Constant Width on MathWorld
- Kepler Conjecture on MathWorld
Leave a Reply