Construction

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 $x^n + y^n = z ^n$ for $n \geq 2$?
• Borsuk's conjecture: Can every bounded subset $S$ of the space $\mathbb{R}^ n$ be partitioned into $n+1$ sets, each of which has a smaller diameter than $S$?
• 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.

Forward Induction

We start off by picking a configuration for $n-1$, and make further choices to obtain a configuration for $n$. This mapping could be one-to-many, and need not be surjective or `injective'. Double counting could be an issue.

How many subsets of $\{1, 2, 3, \ldots, n\}$ are there?

---

Let there be $S_n$ the number of subsets of $\{ 1, 2, 3, \ldots , n \}$.

We will prove by forward induction that $S_n = 2 ^ n$.

Base case: We know that $S_0 = 1$, which is the empty set $\emptyset$.

Induction step:
Given a subset of $\{ 1, 2, 3, \ldots, k \}$, how can we create a subset of $\{ 1, 2, 3, \ldots, k+1 \}$? There are 2 possibilities:
$\quad$1. We can add the element $\{ k+1\}$ to it.
$\quad$2. We can do nothing to it.
Thus, each subset of $\{ 1, 2, 3, \ldots, k \}$ corresponds to 2 subsets of $\{ 1, 2, 3, \ldots, k+1 \}$. Conversely, we can find these 2 subsets of $\{ 1, 2, 3, \ldots, k+1 \}$ that correspond to a subset of $\{ 1, 2, 3, \ldots, k \}$. This sets up the "bijection," which shows us that $S_{k+1} = 2 \times S_{k} = 2 \times 2^k = 2 ^{k+1}$. $_ \square$

Backward Induction

We start off with a configuration for $n$, and make further choices to obtain a configuration for $n-1$. 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 $\{1, 2, 3, \ldots, n\}$ are there, so that no 2 elements are consecutive?

---

Given such a subset, let's consider if it contains the element $n$.

• If it contains the element $n$, then it cannot contain the element $n - 1$. There are no further restrictions and we thus get a subset of $\{1, 2, 3 \ldots , n - 2 \}$ that satisfies the conditions and we union it with $\{ n \}$.
• If it does not contain the element $n$, then we clearly have a subset of $\{ 1, 2, 3, \ldots , n-1 \}$ that satisfies the conditions.

Let $F_n$ denote the number of subsets that satisfy this condition. Then, the above argument shows us that $F_n = F_{n-1} + F_{n-2}$. We can calculate the initial values of $F_0 = 1$ (the empty set) and $F_1 = 2$ (the empty set and $\{ 1 \}$). Along with the recurrence relation $F_n = F_{n-1} + F_{n-2}$ and these starting values, we conclude that we will get the Fibonacci numbers. $_\square$

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 $n$.
In the second problem, because the mapping goes from $F_n$ to both $F_{n-1}$ and $F_{n-2}$, 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 $n\times n$ 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 $a+b = c$), 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 $\{1, 2, 3, \ldots, 3n \}$ into three sets $A, B, C$ each of size $n$. Prove that there exists $x \in A$, $y \in B$ and $z \in C$ such that one of them is the sum of the other two.

---

The structures we want to avoid are things of the form $x + y = z$. What are our main obstacles? $x=1$ presents a huge problem, but that is easily controlled. $z = 3n$ also presents a problem, but that is harder to control. Hence we work with $x=1$.

WLOG, $1 \in A$. What is the next problem? Clearly it is $x = 2$. Do we know where it goes? Not really, it could go into any set, in particular $A$. If it goes into $A$, then we can continue asking about $x=3$. Hence, the proper formulation of $A$ is as follows:

Let $\{1, 2, \ldots , k-1 \} \subset A$ and $k \in B$.
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 $A$ being large.

Now, the structure-finder tells us that no pair of elements in $A$ and $C$ can differ by $k$. The structure-avoider tells us that no pair of consecutive (or within $k-1$) elements can be in $B$ and $C$. Hence, if $C$ has 2 consecutive elements $c$ and $c+1$, then $c+1-k$ is not in $A$ or $B$, so it is in $C$. Also, $c- k$ is not in $A$ or in $B$, so it is in $C$. Thus, $c-k$ and $c+ 1 - k$ are both in $C$. We may then repeatedly remove $k$ from both of these elements till one of these elements is $\leq k+1$, which results in a contradiction. So, if $c+1 \in C$, then $c \not \in C$.

Furthermore, since $1 \in A$, if $c+1 \in C$, then $c \not \in B$.

From the previous 2 statements, we can conclude that if $c + 1 \in C$, then $c \in A$. This gives us an injective map from $C$ to $A$. It is not surjective because $k \not \in C$, and thus $|C| < |A|$, which contradicts the assumption of equal size. $_ \square$.

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 $\pi$ 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 $$\sum_{i = 1 } ^ n a_i ^k = b^k$$ with $n> 1$ and $k > 1$, then $n \geq k$.

This seems to generalize Fermat's last theorem, which is the case that for $k > 2, n \neq 2$. This conjecture is easily shown to be true for $k = 3$, by showing that there are no non-trivial solutions to $a^3 + b^3 = c ^3$, i.e. a specific case of Fermat's last theorem.

Finally in 1966, through a direct computer search, a counterexample for $k = 5$ was found:

$$27^5 + 84^5 + 100 ^ 5 + 133 ^5 = 144 ^5.$$

And in 1986, Noam Elkies found a family of solutions for $k = 4$:

$$( 85v^2 + 484 v - 313)^4 + ( 68v^2 - 586v + 10)^4 + (2u)^4 = ( 357 v^2 - 204v + 363)^4,$$

where $u^2 = 22030 + 28849 v - 56158v^2 + 36941v^3 - 31790 v^4$. Because this is an elliptic curve with a rational point at $v = - \frac{31}{467}$, there are infinitely many other rational points. We can then substitute this into the above equation and clear denominators.

In 1999 and 2000, cases $k = 7, 8$ respectively were disproved with specific examples.

To date, it is not known if $k = 6$ or $k \geq 9$ is false. Care to give it a try?

The Borsuk conjecture asks

Can every bounded subset $S$ of the space $\mathbb{R}^ n$ be partitioned into $n+1$ sets, each of which has a smaller diameter than $S$?

This is a famous problem, in which it is true for $n = 2$ (proved in 1932) and $n = 3$ (proved in 1947, 1955). It was believed to be true for larger $n$, 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 $n = 1325$. Andrij Bondarenko has shown that the conjecture is false for all $n \geq 65$. Currently, it is unknown if $n = 4$ 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 $1, 2, 3, 4, 5, 6, 7, 8$ is a sequence of 8 consecutive integers, whose digit sums are never a multiple of 9.
Hence, the answer is 8. $_\square$

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 $\left( \frac {1}{3}, \sqrt{2} \right)$ works as the center of the concentric circles.

Suppose not, then we must have 2 lattice points $(x_1, y_1), (x_2, y_2)$ whose distances are the same. This implies that

$$\left( x_1 - \frac {1}{3} \right)^2 + \left( y_1 - \sqrt{2} \right) ^2 = \left( x_2 - \frac{1}{3} \right)^2 + \left(y_2 - \sqrt{2}\right) ^2 .$$

Expanding the terms, we get that

$$x_1^2 - \frac{2}{3} x_1 + y_1^2 - x_2 ^2 + \frac {2}{3} x_2 - y_2 ^2 = \sqrt{2} ( 2 y_2 - 2 y_1 ).$$

If $y_2 \neq y_1$, then the LHS is rational while the RHS is irrational, which is a contradiction. Thus $y_1 = y_2$. Hence, $LHS=RHS=0$, which implies that $x_1^2 - \frac {2}{3} x_1 - x_2^2 + \frac {2}{3} x_2 = 0$, or that $0 = (x_1 - x_2) \left( x_1 + x_2 - \frac {2}{3} \right)$. Since the second term is never 0 (because $x_1, x_2$ are integers), we must have $x_1 = x_2.$ This contradicts the assumption that the points are distinct. $_\square$

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 $ABCD$ be 4 points such that $\left\lvert\overline{AB}\right\rvert=\left\lvert\overline{BC}\right\rvert=\left\lvert\overline{CD}\right\rvert=\left\lvert\overline{DA}\right\rvert=\left\lvert\overline{BD}\right\rvert = 1$. Let's rotate this slightly about $A$, to get $AB^*C^*D^*$ such that $\left\lvert\overline{CC^*}\right\rvert\overline =1$.

image

Claim: This set of 7 points satisfy the conditions.

Proof: If the 3 points lie in $\{A, B, C, D \}$ or $\{ A, B^*, C^*, D^*\}$, then we are done. Otherwise, we must have 2 points that are in each of these sets. If these points are not $\{A, C\}$ or $\{A, C^*\}$, then they will be a unit distance apart. Hence, the 3 points must thus be $\{A, C, C^* \}$, but this gives us $CC^* = 1$, so we are done. $_\square$

1) A subset $A \subset \mathbb{N}$ is sum-free if there are no solutions to $x + y = z$ for $x, y, z \in A$. (Note: We allow for $x=y$.)
Prove that for any $n$, there is a sum-free subset of $\{1, 2, 3, \ldots, n \}$ of size $\left\lceil \frac{N}{2} \right\rceil$.

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 $n\geq 3$, does there exist $n$ points in a plane, not all collinear, such that the pairwise distance between any two points is an integer?

Greedy Algorithm