CONSTRUCTION PROBLEMS
VIPUL NAIK
Abstract.
In this article, I describe the general problem of constructing conﬁgurations subject tocertain conditions, and the use of techniques like “greedy algorithms” to construct such conﬁgurations
1.
The pivotal role of construction problems
1.1.
Construction, existence and enumeration.
The general situation of combinatorics could besummarized as follows: We are given a general kind of conﬁguration and we are asked to determinewhether there are any conﬁgurations of that general kind that satisfy certain particular constraints. Wecould have:(1) The
construction
problem which asks for an algorithm or method to construct a conﬁgurationsatisfying the constraints(2) The
existence
problem which simply asks for an answer to whether a conﬁguration exists(3) The
enumeration
problem which asks for the total number of conﬁgurationsSkill at solving the construction problem helps both with the existence problem and the enumerationproblem, as follows:
ã
If we are able to actually construct
a
conﬁguration, we can in particular prove that it exists.
ã
If we are able to devise an algorithm that constructs
all
conﬁgurations, and we can measure thenumber of times that algorithm outputs a conﬁguration, then we have counted the number of conﬁgurations.Thus, construction problems in combinatorics, apart from being important in their own right, alsohelp with existential and enumeration problems.2.
Construction by induction
2.1.
Construction by induction: the idea.
Let
C
n
be the set of
all
conﬁgurations of “size”
n
. Then,construction by induction uses a listing of the elements of
C
n
−
1
to obtain a listing of the elements of
C
n
.There are two possibilities for this. One is that we
ﬁrst
pick a conﬁguration of “size”
n
−
1 (that is,an element of
C
n
−
1
) and then make some further choices and decisions to obtain a conﬁguration of size
n
(that is, an element of
C
n
). Note that since we could make these choices in multiple ways, we mayhave more than one conﬁguration of size
n
corresponding to the conﬁguration of size
n
−
1.The other approach is to start oﬀ with a (as yet unspeciﬁed) conﬁguration of size
n
, make some choicesand decisions and then reach the situation where we have to choose a conﬁguration of size
n
−
1.Let’s look at each of these methods.2.2.
Topdown construction.
In a
topdown
construction, we start with trying to construct the conﬁguration of size
n
, make a few choices, and then reach down to the situation where we have to select aconﬁguration of size
n
−
1.Let’s take the example where the “conﬁguration” of “size”
n
is an arbitrary permutation of the set
{
1
,
2
,...,n
}
. In this context,
C
n
is the set of all permutations on
n
letters, while
C
n
−
1
is the set of allpermutations on
n
−
1 letters.A permutation here is described by a “word” with the ﬁrst letter being where 1 goes, the second letterbeing where 2 goes, and so on. Thus, the elements of
C
n
are words of length
n
(with all letters distinctand drawn from 1 to
n
) while the elements of
C
n
−
1
are words of length
n
−
1 (with all letters distinctand drawn from 1 to
n
−
1).Then, in order to describe a particular conﬁguration of size
n
, we start out by specifying the ﬁrstletter (that is, the image of 1 under the permutation). There are
n
choices for this. Once we have made
c
Vipul Naik, B.Sc. (Hons) Math and C.S., Chennai Mathematical Institute.
1
this choice, we can strip oﬀ the ﬁrst letter and get a word of length
n
−
1 with distinct letters drawnfrom 1 to
n
, except the ﬁrst letter.The number of ways of choosing such words equals the numbers of ways of choosing words of length
n
−
1 with letters drawn from 1 to
n
−
1 (by simply relabelling). This corresponds to the cardinality of
C
n
−
1
, and we get:

C
n

=
nC
n
−
1
Topdown approaches are typically more
local
in nature since the initial local choices have to be made
before
ﬁxing the conﬁguration of size
n
−
1. In other words, when following a topdown approach, wecannot
a priori
know the global impact.In the case of permutations that is not a problem, because whatever choice we make for the ﬁrst letter,the behaviour for the remaining
n
−
1 letters is qualitatively similar.2.3.
Bottomup construction.
In
bottomup
construction, we start by constructing the conﬁgurationof size
n
−
1, and then from that we proceed to construct the conﬁguration of size
n
.That is, for very element
c
∈
C
n
−
1
we try various ways of augmebnting
c
to obtain an element of
C
n
.Bottomup approaches are typically more
global
in nature since here the local choices have to be made
after
ﬁxing the conﬁguration (hence we can make them more intelligently).3.
A bottomup problem: convolutions
3.1.
Problem statement.
Here’s a (rather hard) problem which is best solved bottomup:
Problem 1
(Romanian TST 2002)
.
Consider words of length
n
in four letters:
a
,
b
,
c
and
d
. Deﬁnea convolution in a word as a contiguous repetition of the same block, for instance
aa
is a convolution andso is
abab
. Call a word
convolutionfree
if it does not contain any convolutions. Prove that the numberof convolutionfree words of length
n
is at least 2
n
.3.2.
Exploration of this problem.
We ﬁrst set this problem within the framework of “conﬁgurations”and “constraints”:
ã
The
conﬁgurations
here are the strings of length
n
with letters drawn from
a
,
b
,
c
and
d
ã
The
constraint
is that of being convolutionfree, viz there is no convolution
anywhere
in the word.We want to show that there are lots of conﬁgurations (namely at least 2
n
) of length
n
.In order to use induction, let’s ﬁrst try to understand how convolutionfree words of length
n
arerelated to convolutionfree words of smaller length. :
ã
Let
w
be a string of length
n
and
v
be a contiguous substring of
w
. Then any convolution in
v
gives a convolution in
w
.
ã
Hence, if
w
is convolutionfree, so is every contiguous substring of
w
.
ã
In particular, if
w
is convolutionfree, then the substring obtained by stripping oﬀ the last letterof
w
, is also convolutionfree.This means that to construct all the convolutionfree words of length
n
, it suﬃces to ﬁrst constructall convolutionfree words of length
n
−
1, and then try each of the four possibilities for the last letter.3.3.
Some notation.
For our convenience, we’ll let
C
n
denote the set of all convolutionfree wordsof length
n
, and
D
n
denote the set of all words of length
n
whose initial segment of length
n
−
1 isconvolutionfree.To be able to manipulate strings (words) eﬀectively, we’ll deﬁne the following notation for substrings.Whenever
n
≥
m
+
k
−
1, deﬁne
i
m,k
as the map that takes a string of length
n
and outputs the contiguoussubstring of length
k
starting at the
m
th
place. Then, the fact that every contiguous substring of aconvolutionfree word is convolutionfree, can be expressed via the fact that
i
m,k
maps
C
n
to inside
C
k
.3.4.
How many will work?
Here’s the question: given a convolutionfree word of length
n
−
1, howmany possibilities are there for the last letter so that the new word is again convolutionfree?Answer: It could be as large as 3 and as low as 0.For instance, if the word so far is
abc
, then any of the letters
a
,
b
, or
d
can be added.On the other hand, if the word so far is
babcbabdbabcbab
then
none
of the letters works.
2
3.5.
What’s the algorithm?
Let’s look again at the procedure for obtaining convolutionfree words of length
n
.
ã
First, list all the elements of
C
n
−
1
, viz all the convolutionfree words of length
n
−
1.
ã
Using this, list all the elements of
D
n
. Recall that
D
n
is the set of words of length
n
whose initialsegment of length
n
−
1 is convolutionfree.

D
n

= 4

C
n
−
1

because all we do is try appendingeach of the four letters to each element of
C
n
−
1
.
ã
Try every word that arises by attaching a letter at the end to a convolutionfree word of length
n
−
1. For this word, check that it is convolutionfree.If the initial segment of
n
−
1 letters is convolutionfree, then any convolution in the new word musthave been
introduced
by the last letter – hence one of the blocks must contain the last letter. This forcesthe following picture:The last
k
letters are a repeat of the
k
letters just before them (here
k
≤
n/
2).Put in symbols, this is the same as:
∀
w
∈
D
n
\
C
n
,
∃
k
≤
n/
2 such that
i
m
−
2
k
+1
,k
(
w
) =
i
m
−
k
+1
,k
(
w
)Let’s think of it as a ﬁlter. We send to this ﬁlter an element in
D
n
. The ﬁlter checks, for each
k
, if thelast
k
letters are a repeat of the
k
letters that come before them. If this happens, the word is “ﬁlteredout” by the ﬁlter.Thus, to ﬁnd out how many candidates get ﬁltered in, we can calculate how many candidates getﬁltered out.Let
F
n
denote the set of candidates that are ﬁltered out by this process. In other words,
F
n
=
D
n
\
C
n
.Then, we have:
F
n
=
1
≤
k
≤
n/
2
F
n,k
where
F
n,k
is the set of those candidates that are rejected because the last
k
letters are a repeat of the
k
letters before them.In symbols:
F
n,k
=
{
w
∈
D
n

i
m
−
2
k
+1
,k
(
w
) =
i
m
−
k
+1
,k
(
w
)
}
3.6.
Cardinality bounding.
To get a bound on the size of
F
n
, it suﬃces to get a bound on the size of
F
n,k
for each
k
. Let’s look closely at a word
w
∈
F
n,k
.By assumption, the initial segment of
w
of length
n
−
1 is convolutionfree, hence, since
k
≥
1, theinitial segment of
w
of length
n
−
k
is convolutionfree. Further, once we ﬁx the ﬁrst
n
−
k
letters, thelast
k
are anyway ﬁxed (since they are a repeat of earlier letters). Hence, we have an injective map:
i
1
,n
−
k
:
F
n,k
→
C
n
−
k
which just strips the last
k
coordinates.In particular:

F
n,k
 ≤ 
C
n
−
k

Thus:

F
n
 ≤
k

F
n,k

=
⇒ 
F
n
 ≤
k

C
n
−
k

=
⇒ 
C
n
 ≥ 
D
n
−
k

C
n
−
k

=
⇒
t
n
≥
4
t
n
−
1
−
k
t
n
−
k
3
3.7.
The ﬁnal step.Claim.
For any
n
≥
2,
t
n
≥
2
t
n
−
1
Proof.
Let us assume that the result holds inductively. Then we have:
t
n
−
1
≥
2
t
n
−
2
≥
2
2
t
n
−
3
...
Thus in general:
t
n
−
k
≤
t
n
−
1
2
n
−
1
−
k
Plugging this in the inequality for
t
n
, we get:
t
n
≥
4
t
n
−
1
−
t
n
−
1
(1 + 12 + 12
2
...
)=
⇒
t
n
≥
4
t
n
−
1
−
2
t
n
−
1
=
⇒
t
n
≥
2
t
n
−
1
We are using lots of loose inequalities here (for instance, the actual summation is only a ﬁnite one butwe are extending it to an inﬁnite summation so that we can apply the formula for summing a geometricprogression).
3.8.
Learning and value from this proof.
This proof brings out many ideas:(1) The nature of the constraints and dependencies encourages a bottomup construction: In theproblem of ﬁnding convolutionfree words, a topdown approach is less natural, because there arelots of dependencies (in fact, there are dependencies all over the place). Hence, it is hard to makeone’s
initial
choices wisely without knowing how the rest of the word looks like. A bottomupapproach, where one starts oﬀ with a convolutionfree word of length
n
−
1 and
then
tries to plugin the last letter, thus takes the dependencies into account more eﬀectively.(2) For any
speciﬁc
conﬁguration of size
n
−
1, we cannot predict how many conﬁgurations of size
n
we can construct from it. However, we can count (or at least bound) the
total
number of conﬁgurations that get rejected.(3) When trying to prove a lower bound on a combinatorial quantity, it is sometimes more helpfulto inductively prove a lower bound on the growth rate. For instance, in this problem, we startedoﬀ with trying to prove
t
n
>
2
n
, but found it easier to prove that
t
n
≥
2
t
n
−
1
.4.
Greedy algorithms for existential problems
4.1.
The core idea.
Suppose we have a notion of conﬁgurations for every size
n
, and we are asked todetermine whether there exists a conﬁguration of that size
n
. Then, the topdown approach will say:make some initial choices, and then come down to the problem of constructing a conﬁguration of size
n
−
1.Suppose now that there
does
exist a conﬁguration of size
n
. Then there are two possibilities:
ã
Our initial choices are wise and they help us hit a conﬁguration
ã
Our initial choices are unwise and they do not help us hit a conﬁgurationOn the other hand, suppose there does not exist a conﬁguration of size
n
. Then there is only onepossibility: our initial choices do not help us hit a conﬁguration.Thus, if our initial choices lead to a correct conﬁguration, we have solved the existence problempositively. However, if our initial choices do
not
yield a correct conﬁguration, we cannot be sure whetheror not there exists a correct conﬁguration. The problem is that our initial choices
may have been bad
.This leads us to the question: Can we use some local heuristic to ensure that our initial choicesare always the
best
, that is, that if there is a correct conﬁguration, then there will also be a correctconﬁguration yielded by our initial choices?
4