Problem of the Month
Solution to Problem 5: February 2023
Definition 1: For integers and , we say that divides if there is an integer with the property that . In this case, we write .
The phrases " is a divisor
of " and " is a multiple of " both have the exact same meaning
as " divides ". Notice that, by this definition,
every integer is a divisor of ,
but the only divisor of is itself. We give a few facts that will
be used in this solution. Their proofs are not included.
Fact 1: If
and are positive integers such
that , then .
Fact 2: If ,
, and are integers such that and , then and .
Fact 3: If ,
, and are integers such that and , then .
Suppose is a splendid
sequence. By definition, this means and . Since the
integers in a splendid sequence must be positive, Fact 1 implies that
and , which implies . If is a prime number such that , then by Fact 3. However, no prime
number can divide both and because is splendid. Therefore, no prime
number divides . Similarly, no
prime number divides , and so
.
Therefore, the only splendid sequence of length is .
There are several "generic" sequences that one might find. The
simplest is probably the sequence . That is, the sequence
with for all is always a splendid sequence. This is
because no prime number divides ,
and divides every integer.
Another splendid sequence is . For each integer
in this sequence, other than the
’s on the end and , the integers next to it are and , so their sum is , which is a multiple of
. The integers next to are and , which have a sum of .
In the remaining parts of the solution as well as in the Appendix, we
will often denote a sequence by a bold letter. For example, we might
refer to the sequence by .
Assume that is a splendid
sequence. We will show that
is a splendid sequence when .
If some prime number divides
every integer in , then it
also divides every integer in . Since is a splendid sequence, there is
no such prime number, so no prime number divides all of the integers in
.
If , then and
. Since is a splendid sequence, . We also have that , so or by Fact 2. Since every integer
divides itself, . To
see that , we note
that because is splendid and because every integer divides
itself. By Fact 2, so . The integers through all have exactly the same neighbours
in as they do in , which is a splendid sequence, so
satisfies all other
divisibility conditions required for it to be a splendid sequence.
If , then is splendid by a similar argument
to the one in the previous paragraph.
If , then . When
and when , divides the sum of its neighbours
because it has the exact same neighbours as it did in . In , the neighbours of the integer
are and . Since is a splendid sequence, . We also have
that , and so by Fact 2,
which
means . By
similar reasoning, . The integer is equal to the sum of its neighbours
in by definition, so it also
divides the sum of its neighbours. Therefore, every integer in divides the sum of its neighbours.
We already argued that no prime number divides every integer in , so is a splendid sequence.
Suppose is a splendid sequence. If , then the solution to part (a)
implies that .
Suppose . By definition,
we have that and
that . By
Fact 3, . Since
, we can apply Fact 2 to
get that
which implies that .
Since is splendid, we
also have that . We have just shown that divides , so by Fact 3, . We also have
that , so Fact 2
implies or . Continuing in this way,
we can show that for
all with . By the condition that no
prime number can divide every integer in , we conclude that . Essentially the same argument
shows that .
Most of the work is to prove these two claims.
Claim 1: If is a splendid
sequence of length that
contains at least one integer that is greater than , then there is some with such that and
is a splendid sequence. That is, there is an integer in the sequence
that is equal to the sum of its neighbours, and if it is removed, the
remaining shorter sequence is a splendid sequence.
Claim 2: If is a splendid
sequence of length , then
for every .
Proof of Claim 1. To prove Claim 1, suppose is a
splendid sequence with at least one integer greater than and let be such that is the largest integer in the
sequence, choosing the rightmost occurrence if there is a "tie". More
precisely, is the largest integer
with the property that
for all .
By part (d), , and
since there is at least one integer in that is greater than , neither nor can be the largest integer in , which means . The choice of ensures that and . If , then since is the largest integer in the
sequence, this would imply that
is not the rightmost occurrence of the largest integer in the
sequence. Therefore, we actually have that .
The inequalities and
imply that and since is
splendid, . As well, all integers in a splendid sequence
are positive, which means that is a positive multiple of
that is less than . The only such multiple is itself, and so .
We have shown that one of the integers in is equal to the sum of its
neighbours. To finish proving the claim, we need to show that is a splendid
sequence. In , only and have different neighbours than
they did in , so the
divisibility conditions we need to verify are that and
We know that and we have just
shown that .
Substituting, we get that . By Fact 2,
or . A
nearly identical argument shows that . Therefore,
satisfies the divisibility
conditions.
If a prime number divides
every integer in , then and , so by Fact 2 since . This would mean
divides every integer in , which is not the case since is splendid. ◻
We will now prove Claim 2 by mathematical induction. The essence of
the proof is that, by Claim 1, the largest integer in a splendid
sequence must be the sum of two integers in a shorter splendid sequence.
Therefore, the maximum size of an integer in a splendid sequence of
length is at most twice the
maximum size of an integer in a splendid sequence of length . This means that there is always a
fixed upper bound on the size of integers in a splendid sequence of a
fixed length.
Proof of Claim 2. To get an idea of how the induction will
work, we first prove this for ,
, and . For , we showed in the solution to part
(a) that the only splendid sequence of length is . The largest element in this
sequence is , so the claim
holds for .
Now suppose is a
splendid sequence of length . If
, then every integer
in the sequence is less than . Otherwise, since by part (d), Claim 1 implies
that is the
largest integer in the sequence, so all integers in the sequence are at
most .
Continuing to , suppose is a splendid sequence.
Again, if the sequence consists entirely of ’s, then for all . Otherwise, either is a splendid sequence of
length and , or is a splendid sequence of
length and . Either way, three of the
four integers are in a splendid sequence of length , and the fourth is the sum of two
integers in a splendid sequence of length . We just showed that an integer in a
splendid sequence of length is at
most , so an integer in a
splendid sequence of length is at
most .
Therefore, no integer in the sequence can exceed .
Now for the inductive step. Suppose, for some , that every integer in every
splendid sequence of length is at
most . This is our
inductive hypothesis. Consider a splendid sequence of length
. If for all , then for all . Otherwise, Claim 1 implies that there
is some so that and is a splendid sequence of length . By the inductive hypothesis, this
means each of , , , , , , , , and is at most , and since , each of these
integers is at most .
For , we have and since and , we conclude that
as well. We have shown
that every integer in a splendid sequence of length is at most . This completes the induction
and the proof. ◻
By Claim 2, every integer in a splendid sequence of length is at most . There are only finitely many
sequences of length consisting of
positive integers less than or equal to , regardless of whether they are
splendid. Therefore, for fixed ,
there are only finitely many splendid sequences of length .
The proof of part (f) will use some language about sets.
Specifically, we will use the language of injective, surjective, and
bijective functions. If you have seen this before, you should be ready
to read the solution to part (f). Otherwise, we recommend reading
Appendix 1 first.
As pointed out in the hint, the number of splendid sequences of
length is equal to the st Catalan
number. The th Catalan number is equal to , so the
number of splendid sequences of length is . The
sequence of Catalan numbers shows up in many contexts. A useful example
for this solution is given in Definition 2.
Definition 2: For each positive integer , we call a sequence of positive integers
a tame sequence if
and for every
integer with . In other words, and every other integer in the
sequence is at most more than the
previous integer.
The name tame sequence was made up for the purpose of this
solution, but it is known that the number of tame sequences of length
is equal to the th Catalan number. There are
proofs of this in various places in the literature. For completeness, we
have included a proof in Appendix 2. It is stated as Claim 5.
Let denote the set of tame
sequences of length and denote the set of splendid sequences
of length . We will show, for
, that there is a bijection
with domain and codomain
. By the discussion in
Appendix 1, this will show that the number of splendid sequences of
length is the st Catalan number.
Recall from part (c) that if is a splendid
sequence of length , then
is a splendid sequence of length .
From this point on, it will be notationally useful to prepend a zero
at the beginning of splendid sequences. For example, the sequence will now be the unique splendid
sequence of length . The sequence
is a splendid
sequence of length . This means
that a splendid sequence of length now has integers, the first of which is . For instance, , , , , , and is how we would index the sequence
going forward. Notice
that the observation from part (c) mentioned above also works if we
insert the sum between the first and second integers, and . You should convince yourself of this
before moving on.
For each , we define a
function, , with domain and codomain . The way works is to use a tame sequence as a
list of instructions to build a splendid sequence. Consider a tame
sequence of length . Starting with , the unique splendid sequence of
length , we read from left to right and each
integer in the tame sequence tells us where to insert a sum to get a
longer splendid sequence. Specifically, in the th step, the integer tells us that we should insert a sum
between and to get a longer splendid
sequence.
For example, suppose and the
tame sequence is . Start with , which has and . The first integer in is , so in the first step we insert the sum
between and . This means we go from to . To start the second
step, we reindex to , , and . The next integer in is , so we insert the sum between and to get . The next integer
in is , so we insert the sum between the third
and fourth integers in the current splendid sequence to get . Continuing, we
get ,
followed by , and
finally .
Thus, .
By part (c), if is a tame
sequence of length , then is a splendid sequence of
length . Also note that at the
start of the th step,
the splendid sequence has
integers in it. Because of the way tame sequences are defined, the th integer in a tame sequence
is at most , so at each step, the
splendid sequence is always long enough for the instruction to makes
sense.
For each , we will show
that the function is a
bijection. The proof will be by induction, but we first need a
definition and then a useful fact.
Definition 3: For a splendid sequence of length
(remember that ), we say that is a peak if .
By Claim 1 (see the solution to part (e)), every splendid sequence
with an integer greater than has
at least one peak. Moreover, if that peak is "removed", the resulting
shorter sequence is splendid. As well, with our new notation, if there
is no integer greater than , then
the sequence is of the form and the first
(leftmost) is its only peak. If
it is removed, the resulting shorter sequence is also splendid. Indeed,
the reason for introducing the at
the beginning was to avoid having to treat the sequence of all ’s separately in this part of the
argument.
Now for the useful fact:
Claim 3: Suppose is a splendid sequence of length
and that is a
tame sequence of length such
that . If we let
, then is the leftmost peak of .
A proof of Claim 3 is given at the end. We will now prove by
induction that is a bijection
for all .
It was observed in part (a) that the only splendid sequence of length
is . As well, the only tame
sequence of length is . It is easily checked that
. The sets and each have only one element. There is
only one function between two sets with one element, and it is always a
bijection (convincing yourself of this is a good exercise in
understanding definitions). Therefore, is a bijection.
For the inductive hypothesis, we assume for some that is a bijection.
We will show that is a
bijection, which means we need to show that it is injective and
surjective. To show that it is surjective, we assume that is in and let be its leftmost peak. By Claim 1 from
the solution to part (e), the sequence is in
. Since is a bijection by the inductive
hypothesis, it is surjective, so there is some tame sequence in with . For convenience,
let .
Recall that the leftmost peak of is . Note that since can never be a peak. Therefore,
and so .
Suppose is the leftmost peak
of . If , then is a peak of because has the same neighbours in and when . However, was chosen to be the leftmost peak of
, so we cannot have . This means , but by Claim 3, , so we get . Combining with , we have that , which means
the sequence is a tame sequence. We will call this
tame sequence .
To recap, the tame sequence is obtained by appending to , the splendid sequence is obtained by inserting the sum
between the st and
th integer in , and . It follows that . We have found
such that . Since was an arbitrary element of , this concludes the proof that
is surjective.
We will now show that is
injective. To do this, we suppose and are in with . We
will show that .
Let be
such that .
Suppose is the leftmost peak of
. By Claim 3, both and . This shows that . As well, if we set and and
, then
. By
the inductive hypothesis, is
bijective, and hence, it is injective, so . This shows that and have the same first integers, and since as well, we have that , which concludes the proof
that is injective.
We have now shown that
is bijective, which proves that and have the same number of elements when
. Therefore, the number of
splendid sequences of length is
as
claimed earlier.
Proof of Claim 3. The proof is by induction on . It was noted earlier that the only
tame sequence of length is
(), the only splendid sequence of
length is (, , ), and that . The leftmost peak of
is and . This shows that Claim 3 is true
when .
For the inductive hypothesis, we suppose, for some , that if is a
splendid sequence of length and
is a
tame sequence of length such
that , then the
leftmost peak of the is
where .
Suppose is a splendid sequence of
length and that is a tame
sequence of length with . Because of how
is applied, is a peak of . As well, is a splendid
sequence of length such that
where . For
convenience, set and . Suppose the leftmost peak of
is for some . For now, assume . It is not difficult to show
that it is impossible for a splendid sequence to have two consecutive
peaks. This means we must have since must be at
least two less than . If this
happens, is also a peak of
because has exactly the same neighbours
in and . By the inductive hypothesis,
is the leftmost peak of
, so and we get . Since is a tame sequence, or . This implies that so , which is impossible.
Therefore, we cannot have ,
which means is indeed the
leftmost peak of . This
completes the induction and the proof. ◻
Appendix 1
Suppose and are finite sets, where by "set" we mean
an unordered collection of objects. Suppose there is a "rule" that, for
every element in the set ,
produces an element in the set .
For instance, if the sets were and (both sets of three ordered pairs), the "rule"
might be "square the second entry, then reverse the order". With this
rule, becomes , becomes , and becomes , so every element of is transformed into an element of . Such a rule is called a function. The
set is called its "domain" and
is called its "codomain". If the
function is named , we would use
to denote the function applied
to an element in the domain. You
have probably seen functions before where the domain and codomain are
all or part of the set of real numbers, but the notion of a function
applies in a much broader context. Below are three important properties
that functions may (or may not) have.
Injectivity: A function with domain and codomain is called injective if for
every two elements of the domain, and , if , then . In other words, a
function is injective if its application to two different elements of
the domain always gives two different results. Note that when trying to
prove that a function is injective, we typically assume that and deduce that . You might want to think about
this logic.
Surjectivity: A function with domain and codomain is called surjective if for
every there exists an so that . In other words, a function is
surjective if every element of the codomain is the result of applying
to some element in the domain.
[We might also say that the range equals the codomain to
describe surjectivity.]
Bijectivity: A function is with domain and codomain is called bijective or is
a bijection if it is both injective and surjective.
There is a lot to be said about injective, surjective, and bijective
functions, but for us, the useful observation will be that if and are finite sets and there is a
bijective function with domain
and codomain , then and have the same number of elements.
Indeed, if has elements and has elements, then being injective implies
that and being surjective
implies that . Thus, being
bijective implies that , so .
Observe that the example given at the beginning of this appendix is
neither injective nor surjective, so it is not bijective. However, and do have the same number of elements. It
is important to keep in mind that we are only claiming that if there is
a bijection from to , then they have the same number of
elements. There are six bijective functions from to , the example we gave just happens to
not be one of them.
Appendix 2
We will now show that the number of tame sequences of length is equal to the th Catalan number, . The proof
relies on the material from Appendix 1. As well, the results here are
well known and proofs of them can be found in the literature.
Definition 4: For each positive integer , a sequence of integers is called a jagged
sequence of length if properties
and hold:
. Exactly of the integers are equal to and exactly of the integers are equal to .
. For each integer with , the sum of the first integers in the sequence is
non-negative.
Claim 4: There are jagged
sequences of length .
Proof of Claim 4. Fix a positive integer . Let be the set of sequences of integers that satisfy and fail . Also, let be the set of sequences of integers, of which equal and of which equal . We will show that and have the same number of elements.
Suppose is in . Since fails , there must be some with and the property that the sum of the first entries is negative. Let be the smallest such position in the
sequence. If , then . This means of the integers in the list are equal to , and of them are equal to . Therefore, the sequence has integers equal to and integers equal to , which means it is in .
If , then , , and so on up to , but . Since but , we must
have that is negative, but
, so . As well, each of the are integers, so the two sums above
are integers, which means and (there is
no other way to add to a non
negative integer and get a negative integer). The fact that implies that
exactly half of the integers in the list are equal to , and so the number of ’s in is one more than the
number of ’s. Since the number of
’s and ’s is equal in , this means the number of ’s in is one more than
the number of ’s. All of this
implies that
has two more ’s than ’s. Two numbers that differ by and have a sum of must be and , so the sequence above is in .
The above work defines a function, that we will call , with domain and codomain . Specifically, if in and the smallest integer such that , .
That is, is the sequence
obtained by negating every integer from to the end of the sequence. We
will show that is a
bijection.
To see that is injective,
suppose and are in with . We suppose that
is the smallest such that and is the smallest such that . We might as well
assume that . Our assumption
says that the sequences
and
are equal. Since , this
means when and when . Observe that ,
and since
by assumption, we get that . This means as well and so . Since when and , we have that for all . In other words, , so is injective.
Now suppose is a sequence is in . Because , exactly of the integers in are equal to and of them are equal to . Consider the list of sums The first "sum", , is either or . The final sum is . As we move from one sum
to the next in the list above, we add for some , which means the sums either increase
or decrease by as we move down
the list. Therefore, there is at least one sum that equals (it could be the first). Suppose is the smallest such that . Then the
sequence is in and . To see that , we have that and , ad so it must
be that .
Therefore, .
This means has the same
number of ’s and ’s, which means there are of each. As well, the sequence fails
because the first integers have a negative sum. This
shows that , and that
is essentially by
the definition of .
Therefore, is surjective, which
completes the proof that it is a bijection.
The number of sequences in is
. This is because
we can choose where to put the ’s
in ways, and then
there is no choice of where to place the ’s. By what we have shown, we now know
that there are
sequences in as well.
We can now compute the number of jagged sequences. The number of
sequences of integers that
satisfy is by reasoning similar to
that in the previous paragraph. To get the number of jagged sequences of
length , we need to subtract from
the number of
sequences that satisfy but fail
, which is exactly the number of
sequences in . Therefore, the
number of jagged sequences is
◻
Claim 5: The number of tame sequences of length
is .
Proof of Claim 5. We will find a bijection from the set of
jagged sequences of length to
the number of tame sequences of length .
Suppose is jagged and that are the
indices where the ’s
occur. That is, and all
other integers in are equal
to . We will now define a
sequence so that is the sum of the integers in from up to and including the th integer equal to . In symbols, .
Of the first integers in
, exactly of them are equal to and the other of them are equal to . Therefore, their sum (which is by definition), is . Thus, for a jagged
sequence , we define to be the sequence where .
We will show that is a
bijection, but we first need to confirm that is always tame, which means we
need to show that , for all , and that for all . We know that by , so this means and . Suppose . In , there are only ’s up to and including , which means that among the first
integers in , there are at least as many ’s as ’s. This means the sum of the first
integers cannot be positive.
Therefore, we must have that , and since both are integers,
, which rearranges to
, which gives . To see that , note that , so . Then and so or . This completes the
proof that is tame.
To see that is injective,
notice that can be
rearranged to get . In
other words, if ,
then is uniquely determined
from . This means that from
, the positions of the ’s in are uniquely determined, so the
entirety of is uniquely
determined by . This means
there is only one with the
property that , so
is injective.
To see that is surjective,
suppose
is a tame sequence. For each from
through , define , then define so that
if for some , and otherwise.
That follows by
rearranging to get . However, to conclude that
is surjective, we need to verify
that is indeed a jagged
sequence.
By one of the conditions of tameness, , so so we have that . Using the assumption that
which can be
rearranged to , we
get that which means and it follows that
. Finally, since
is positive, . We have shown that
. This
shows that all of the are
distinct, so satisfies .
Rearranging , we get
, and by the reasoning
from earlier, this means the sum of the first integers in (always ending with the th ) is equal to , which is positive because is tame. Now consider the sum
for some an
arbitrary with . If for some , then the sum is positive by the
reasoning just given. Otherwise, there is some for which . Since every
integer in strictly between
and equals by construction, we must have that
because the
latter is obtained from the former by adding some (possibly zero) ’s. We know that and that
is positive, so this means .
We have shown that
satisfies as well, so is a jagged sequence with . Therefore, is surjective, which completes the
proof that it is bijective. Therefore, the number of tame sequences of
length is . ◻