Construction

In one sentence

The answer to many problems is a “thing”: an example, a function, a figure. Construction means building it. The most common pattern is a max/min problem:

upper bound prove \leq M + construction build an example = M ⟹ maximum = M

With only the bound, the answer might be smaller; with only the example, the answer might be larger. Another kind of construction is “recognizing” an expression: if it looks like a discriminant, build a quadratic function; if it looks like the law of cosines, build a triangle.

Predict first

At most how many numbers can be chosen from $1, 2, \dots, 20$ so that none of them is a multiple of another?

numbers

Choose an answer first; then you can see the result.

Example: at most how many numbers from {1, …, 2n}, none dividing another (n = 10)?

Step 1 / 5

Pick a few at random
Greedily picking from small to large is a bad idea: once $2$ is chosen, $4, 6, 8, \dots$ are all ruled out. The detector marks every pair where one divides the other.

$2 ∣ 6$
Build drawers: the upper bound
At most one per drawer
Construction: take the larger half
Conclusion

Stop 1 · Constructing a function (Vol. 2)

$(\sum a_{i} b_{i})^{2} \leq \sum a_{i}^{2} \sum b_{i}^{2}$ has the shape “ $B^{2} \leq A C$ ”, like a discriminant. So build a quadratic function whose discriminant it is.

One problem, several solutions

Prove the Cauchy inequality $(a_{1} b_{1} + \dots + a_{n} b_{n})^{2} \leq (a_{1}^{2} + \dots + a_{n}^{2}) (b_{1}^{2} + \dots + b_{n}^{2})$ .

Construct a quadratic function

Assume $\sum a_{i}^{2} > 0$ (otherwise it is obvious). Let $f (t) = \sum (a_{i} t - b_{i})^{2} = (\sum a_{i}^{2}) t^{2} - 2 (\sum a_{i} b_{i}) t + \sum b_{i}^{2}$ . Then $f (t) \geq 0$ for every real $t$ and the parabola opens upward, so the discriminant satisfies $Δ = 4 (\sum a_{i} b_{i})^{2} - 4 \sum a_{i}^{2} \sum b_{i}^{2} \leq 0$ . Equality holds if and only if some $t$ gives $a_{i} t = b_{i}$ for all $i$ .

CostYou first have to “see” the discriminant; after that, two lines.

Lagrange's identity

$\sum a_{i}^{2} \sum b_{i}^{2} - (\sum a_{i} b_{i})^{2} = \sum_{i < j} (a_{i} b_{j} - a_{j} b_{i})^{2} \geq 0$ .

CostJust expand to check, but you have to remember the identity.

Stop 2 · Constructing a figure (Vol. 3)

$a^{2} + b^{2} - ab$ is exactly what the law of cosines looks like with an angle of $6 0^{\circ}$ : $a^{2} + b^{2} - 2 ab cos 6 0^{\circ}$ .

Example: a, b, c > 0. Prove that √(a² − ab + b²) + √(b² − bc + c²) ≥ √(a² + ac + c²)

Step 1 / 4

Recognize the law of cosines
$a^{2} - ab + b^{2} = a^{2} + b^{2} - 2 ab cos 6 0^{\circ}$ ; $a^{2} + a c + c^{2} = a^{2} + c^{2} - 2 a c cos 12 0^{\circ}$ .

$6 0^{\circ}, 6 0^{\circ}, 12 0^{\circ}$
Draw the figure
Read off three sides
The triangle inequality

Stop 3 · Existence in sequences (Vol. 5)

“Are there arbitrarily long runs of consecutive composite numbers?” Yes, and you can write them down.

Example: for every positive integer k there are k consecutive composite numbers

Step 1 / 3

Give every term a divisor
We want the $j$ -th number to be divisible by $j + 1$ : start from a number divisible by all of $2, 3, \dots, k + 1$ .

$(k + 1)!$
Write them down
A construction need not be the smallest

Stop 4 · Partitions of a set (Vol. 1)

The same pattern with a different condition: the chosen numbers must be pairwise not coprime. The drawers become pairs of neighbors ${2 k - 1, 2 k}$ (consecutive integers are coprime).

Choose as many numbers from

1

16

as you can so that no two are coprime. First switch on “Group into drawers”, then build your example.

Upper bound: the $n$ drawers ${1, 2}, {3, 4}, \dots, {2 n - 1, 2 n}$ each allow at most one choice, so at most $n$ numbers. Construction: all the even numbers $2, 4, \dots, 2 n$ , any two of which share the factor $2$ . The maximum is $n$ .

Practice

Exercise 1Basic

At most how many numbers can be chosen from $1, 2, \dots, 30$ so that none of them divides another?

Exercise 2Basic

At most how many numbers can be chosen from $1, 2, \dots, 50$ so that no two of them are coprime?

Exercise 3Advanced

Five consecutive positive integers are all composite. What is the smallest possible value of the smallest one?

Exercise 4Challenge

Real numbers $a, b, c$ satisfy $a + 2 b + 3 c = 14$ . Find the minimum of $a^{2} + b^{2} + c^{2}$ .

In one sentence

Example: at most how many numbers from {1, …, 2n}, none dividing another (n = 10)?

Stop 1 · Constructing a function (Vol. 2)

Construct a quadratic function

Lagrange's identity

Stop 2 · Constructing a figure (Vol. 3)

Example: a, b, c > 0. Prove that √(a² − ab + b²) + √(b² − bc + c²) ≥ √(a² + ac + c²)

Stop 3 · Existence in sequences (Vol. 5)

Example: for every positive integer k there are k consecutive composite numbers

Stop 4 · Partitions of a set (Vol. 1)

Practice

Mistake Museum · Exhibits from this stop

A constructed example that was never checked

The factorial construction is off by one

Stops on this line