Waste less time on Facebook — follow Brilliant.
×

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

Note by Calvin Lin
3 years, 5 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Feeling a little bit dizzy after reading all of this.....information overload... :D Prasun Biswas · 3 years, 5 months ago

Log in to reply

@Prasun Biswas Indeed. I should have broken it up into smaller pieces. Will remember to do so next time and spread it out across different notes.

Can't really be helped that I had to describe numerous different approaches, and spreading it out will not make sense. I tried to introduce them in a short manner.

If you have any suggestions, let me know! Calvin Lin Staff · 3 years, 5 months ago

Log in to reply

Problem 5:

Consider the subset \(S\) of \(\{1, 2, \cdots , n\} \) which contains all the odd numbers. Note that this subset has \(\left \lceil \dfrac{n}{2} \right \rceil \) elements. For all \(x, y \in S\), \(2|x+y\), so \(S\) is sum-free (since all elements in \(S\) are odd). \(\blacksquare\) Sreejato Bhattacharya · 3 years, 5 months ago

Log in to reply

@Sreejato Bhattacharya Good job Sreejato. That's exactly what I did. This problem was very trivial and the solution can be seen immediately after some inspection of the parity of x,y,z. Muhammad Shariq · 3 years, 4 months ago

Log in to reply

@Sreejato Bhattacharya then how is \(x=y\) applicable here? \(x=1. y+1 , z=2\) ? Sagnik Saha · 3 years, 4 months ago

Log in to reply

@Sagnik Saha You didn't get my point. First, \(S\) consists entirely of odd elements, so \(2 \not \in S\). For all \(x, y \in S\) (not necessarily distinct), \(x+y\) is even, and hence not included in \(S\). I never mentioned \(x \neq y\). Sreejato Bhattacharya · 3 years, 4 months ago

Log in to reply

Solution to Problem 4, India TST.

Proof: The structure 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:

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, 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, c+ 1 - k \) are both in \(c\). We may then continue removing \(k\) from both of these elements, which results in a contradiction. Thus \(C\) doesn't contain consecutive elements.

But since \(B\) and \(C\) don't contain consecutive elements either, this tells us that if \( c \in C \), then \( c - 1 \in A \). Hence, we have 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 \). Calvin Lin Staff · 3 years, 5 months ago

Log in to reply

Woah. That's intensely awesome. :D Finn Hulse · 3 years, 5 months ago

Log in to reply

A solution to problem 5: Clearly the set \({1,2,3,....,n}\) has \(\lceil \frac{n}{2} \rceil\) odd numbers.

The sum of any two of these odd numbers is even(This holds true even if \(x = y\)).Hence \(x+y = even\) and \(z = odd\).So the equaltity \(x+y = z\) can never holds true.Hence we have a sum free set!! Eddie The Head · 3 years, 4 months ago

Log in to reply

For 3), when u say "contains", do u mean the lattice point is inside the circle, i.e. it lies inside the circle but not on the circumference or does "contains" allows the lattice point to lie on the circumference. If "contains" only refers to the inside, then the problem is trivial. Muhammad Shariq · 3 years, 4 months ago

Log in to reply

SUPERB....READING WILL PRACTICE IT NOW ON.... Karttikeya Mangalam · 3 years, 4 months ago

Log in to reply

helpless :( Taimoor Afzal · 3 years, 4 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...