Many famous problems in mathematics are phrased as a search for a specific construction that fulfills certain criteria. This often requires some creativity and understanding of the theory behind the problem.
Some well-known construction problems are:
- Fermat's Last Theorem: Does there exist non-trivial solutions to for ?
- Borsuk's conjecture: Can every bounded subset of the space be partitioned into sets, each of which has a smaller diameter than ?
- Geometric problem of antiquity: Can we trisect any angle using a compass and straightedge only?
In a construction problem, we seek an explicit characterization or identification, which allows us to verify that the statement is true or false.
There are 3 aspects to this:
- Construction - Is there an algorithm or method which allows us to construct a configuration which satisfies the constraints?
- Existence - Is there a configuration which satisfies the conditions? Can we prove that no configuration exists?
- Enumeration - How many configurations satisfies the conditions?
We introduce the following approaches as a way to help think about construction problems.
We start off by picking a configuration for , and make further choices to obtain a configuration for . This mapping could be one-to-many, and need not be surjective or `injective'. Double counting could be an issue.
How many subsets of are there?
Let there be the number of subsets of .
We will prove by forward induction that .
Base case: We know that , which is the empty set .
Given a subset of , how can we create a subset of ? There are 2 possibilities:
1. We can add the element to it.
2. We can do nothing to it.
Thus, each subset of corresponds to 2 subsets of . Conversely, we can find these 2 subsets of that correspond to a subset of . This sets up the "bijection," which shows us that .
We start off with a configuration for , and make further choices to obtain a configuration for . This mapping could be one-to-many, and need not be surjective or injective. Double counting could be an issue. It is comparatively harder to implement.
How many subsets of are there, so that no 2 elements are consecutive?
Given such a subset, let's consider if it contains the element .
- If it contains the element , then it cannot contain the element . There are no further restrictions and we thus get a subset of that satisfies the conditions and we union it with .
- If it does not contain the element , then we clearly have a subset of that satisfies the conditions.
Let denote the number of subsets that satisfy this condition. Then, the above argument shows us that . We can calculate the initial values of (the empty set) and (the empty set and ). Along with the recurrence relation and these starting values, we conclude that we will get the Fibonacci numbers.
What is the difference between these 2 methods of induction? While these are similar, the forward/backward aspect is the way we think about an approach these problems. Often, both of these approaches could be used, with a slightly different solution.
In the first problem, both methods work equally. The backward induction approach would be to start with such a subset, and then consider if it contains the element .
In the second problem, because the mapping goes from to both and , backward induction is more natural way of thinking about it.
Greedy Algorithm - Covering Everything
Uses a local heuristic to ensure that our choices are good, but still simple enough. Ideally, "there exists a configuration if and only if there exists a configuration using a local heuristic," but this isn't always true.
Consider an board. Can a knight tour the entire board by visiting each square exactly once?
I do not know the complete solution to this problem. You can fill in the details.
The underlying principle is known as Warnsdorff's rule: Go to the neighbor which has the least number of neighbors.
Why does this work (or at least, why is this likely to work)?
- It gives priority to squares that are most likely to be cut off.
- Especially for squares which only have 2 free neighbors left, when you land on one of the neighbors, you have to move to the square, and then exit through the other neighbor.
- However, it doesn't guarantee that you will explore the entire board. You might be stick in a local position. This is the drawback of the greedy algorithm.
Structure avoider and finder
If the aim of the problem is to construct a configuration which avoids a certain kind of structure (e.g. existence of monochromatic triangle, elements such that ), it can be helpful to consider these 2 players:
- Structure-avoider: Goal is to construct a configuration that avoids the structure.
- Structure-finder: Goal is to find the structure (if it exists) in the configuration.
(India TST) Consider any partition of the numbers into three sets each of size . Prove that there exists , and such that one of them is the sum of the other two.
The structures we want to avoid are things of the form . What are our main obstacles? presents a huge problem, but that is easily controlled. also presents a problem, but that is harder to control. Hence we work with .
WLOG, . What is the next problem? Clearly it is . Do we know where it goes? Not really, it could go into any set, in particular . If it goes into , then we can continue asking about . Hence, the proper formulation of is as follows:
Let and .
What do we think is likely the issue? The condition of equal size has not been used, and so in order for it to come into play, we must believe that one of the sets will be large. We don't have any information as yet, but my bet will be on being large.
Now, the structure-finder tells us that no pair of elements in and can differ by . The structure-avoider tells us that no pair of consecutive (or within ) elements can be in and . Hence, if has 2 consecutive elements and , then is not in or , so it is in . Also, is not in or in , so it is in . Thus, and are both in . We may then repeatedly remove from both of these elements till one of these elements is , which results in a contradiction. So, if , then .
Furthermore, since , if , then .
From the previous 2 statements, we can conclude that if , then . This gives us an injective map from to . It is not surjective because , and thus , which contradicts the assumption of equal size. .
The idea here is to prove that a statement is not true, by constructing a specific counterexample.
The typical examples are the three geometric problems of antiquity: squaring of the circle, doubling of the cube, and trisection of angles through a compass and straightedge only. To solve these problems, we develop the concept of a constructible number in the complex plane. A complex number is constructible if its corresponding point in the Euclidean plane is constructible by using a unruled straightedge, compass and line segment of unit length. Using the language of field theory, it turns out that the constructible numbers are the "quadratic closure of the rational numbers." While this complete characterization is somewhat beyond us for now, we can show that a constructible number must be an algebraic number (which means that it is the root of a polynomial with integer coefficients). This follows by considering what the various compass and straightedge constructions actually allow. As such, since is transcendental, it shows that we are unable to square the circle.
Euler's conjecture (stated in 1769) states that
If there are non-zero integers such that with and , then .
This seems to generalize Fermat's last theorem, which is the case that for . This conjecture is easily shown to be true for , by showing that there are no non-trivial solutions to , i.e. a specific case of Fermat's last theorem.
Finally in 1966, through a direct computer search, a counterexample for was found:
And in 1986, Noam Elkies found a family of solutions for :
where . Because this is an elliptic curve with a rational point at , there are infinitely many other rational points. We can then substitute this into the above equation and clear denominators.
In 1999 and 2000, cases respectively were disproved with specific examples.
To date, it is not known if or is false. Care to give it a try?
The Borsuk conjecture asks
Can every bounded subset of the space be partitioned into sets, each of which has a smaller diameter than ?
This is a famous problem, in which it is true for (proved in 1932) and (proved in 1947, 1955). It was believed to be true for larger , but no further results were available, until Jeff Kahn and Gil Kalai showed by constructing a certain set of points that it was not true for . Andrij Bondarenko has shown that the conjecture is false for all . Currently, it is unknown if is a true statement.
A longevity chain is a sequence of consecutive integers, whose digit sums are never a multiple of 9. What is the longest possible length of a longevity chain?
We know that any number which is a multiple of 9, has a digit sum which is a multiple of 9. Hence, the longevity chain can have at most 8 elements.
As an explicit example, the sequence is a sequence of 8 consecutive integers, whose digit sums are never a multiple of 9.
Hence, the answer is 8.
In the above problem, the understanding that we needed was how digit sums relate to multiples of 9. With that understanding, the construction of the solution is straightforward.
Does there exist a family of concentric circles such that each circle contains exactly 1 lattice point, and each lattice point is on a circle?
Consider the center of these concentric circles. Since each lattice point is on a unique concentric circle, this means that the distance of each lattice point to the center must be distinct.
Claim: The point works as the center of the concentric circles.
Suppose not, then we must have 2 lattice points whose distances are the same. This implies that
Expanding the terms, we get that
If , then the LHS is rational while the RHS is irrational, which is a contradiction. Thus . Hence, , which implies that , or that . Since the second term is never 0 (because are integers), we must have This contradicts the assumption that the points are distinct.
In the above problem, we played around with the conditions and rephrased it into a number-theoretic statement, which made it easier to approach.
Note: There is an existence solution which works by showing that the plane cannot be covered by countably many lines.
Is it possible to find 7 points in the plane such that out of every subset of 3 points, there are 2 points that are a unit distance apart?
Let be 4 points such that . Let's rotate this slightly about , to get such that .
Claim: This set of 7 points satisfy the conditions.
Proof: If the 3 points lie in or , then we are done. Otherwise, we must have 2 points that are in each of these sets. If these points are not or , then they will be a unit distance apart. Hence, the 3 points must thus be , but this gives us , so we are done.
1) A subset is sum-free if there are no solutions to for . (Note: We allow for .)
Prove that for any , there is a sum-free subset of of size .
2) A lattice square is a square in the plane, whose 4 vertices are lattice points. Describe the set of possible side lengths of a lattice square.
3) For which integers , does there exist points in a plane, not all collinear, such that the pairwise distance between any two points is an integer?
A lattice hypercube is a cube in 4-dimensional space, whose vertices are lattice points. Describe the set of possible side lengths of a lattice hypercube.
Note: A lattice point is a point whose coordinates are all integers. is a lattice point, but is not a lattice point.
If you are interested in Lattice cubes, try the 3-D version.
For similar problems, you can read my note on Construction.
-gon, we say that a line is loyal if it intersects the perimeter of the -gon along the entire length of exactly one edge. Determine the largest integer such that every non-degenerate -gon has a loyal line.Given an
Details and assumptions
- An -gon is non-degenerate if no three consecutive vertices are collinear, or equivalently, that no two consecutive edges are on the same line.
- The above image is an example of a 20-gon that doesn't satisfy the conditions of the problem. The 10 dotted lines are all the lines that contain at least one edge of the 20-gon, however, because all of these lines contain 2 edges, none of them are loyal lines. This shows that the answer is not 20.