Construction

I recently conduction a session for the Singapore International Mathematical Olympiad team, on the technique of Construction. Here is the set of notes.

Main Problem: Finding configurations which fulfill certain conditions.

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?

Different approaches

1) 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.

Problem 1: How many subsets of $\{1, 2, 3, \ldots, n\}$ are there? How many subsets of $\{1, 2, 3, \ldots, n\}$ are there, so that no 2 elements are consecutive?

2) 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.

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

Question: Does Forward Induction / Backward Induction work for these problems?
In the first problem, both methods work equally. In fact, in school, most people learn it in the Backward way: "How many ways are there of arranging 5 students?" "There are 5 choices for the first, then 4 choices, then 3, 2, 1."
In the second problem, because the mapping goes from $F_n$ to both $F_{n-1}$ and $F_{n-2}$, backward induction is a slightly more natural way of thinking about it.

3) 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.

Problem 3: Consider a $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.

4) 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.

Problem 4: (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.

This problem illuminates how to use this approach. The solution is posted in the comments below.

Problems

Please refrain from discussing 1, 2 and 7 as I intend to share them as problems shortly. The rest are fair game.

1) 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? Enter your answer here..
2) A lucky chain is a sequence of consecutive integers, whose digit sums are never a multiple of 11. What is the longest possible length of a lucky chain? Enter your answer here..
3) 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?
4) For which integers $n\geq 3$, does there exists $n$ points in a plane, not all collinear, such that the pairwise distance between any two points is an integer?
5) 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 $\lceil \frac{N}{2} \rceil$.
6) 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.
7) 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 cube.
8) Determine the largest positive integer $N$, such that given any $N-$gon (not necessarily convex), there exists a line (infinitely extended in both directions) that contains exactly 1 edge of the $N-$gon.

Image credit: Wikipedia