CEMC Banner

Problem of the Month
Solution to Problem 5: February 2023

Definition 1: For integers a and b, we say that a divides b if there is an integer c with the property that ac=b. In this case, we write ab.

The phrases "a is a divisor of b" and "b is a multiple of a" both have the exact same meaning as "a divides b". Notice that, by this definition, every integer is a divisor of 0, but the only divisor of 0 is 0 itself. We give a few facts that will be used in this solution. Their proofs are not included.

Fact 1: If a and b are positive integers such that ab, then ab.

Fact 2: If a, b, and c are integers such that ab and ac, then a(bc) and a(b+c).

Fact 3: If a, b, and c are integers such that ab and bc, then ac.

  1. Suppose (a,b) is a splendid sequence. By definition, this means ab and ba. Since the integers in a splendid sequence must be positive, Fact 1 implies that ab and ba, which implies a=b. If p is a prime number such that pa, then pb by Fact 3. However, no prime number can divide both a and b because (a,b) is splendid. Therefore, no prime number divides a. Similarly, no prime number divides b, and so a=b=1.

    Therefore, the only splendid sequence of length 2 is (1,1).

  2. There are several "generic" sequences that one might find. The simplest is probably the sequence (1,1,1,,1). That is, the sequence (a1,a2,a3,,an) with ai=1 for all i is always a splendid sequence. This is because no prime number divides 1, and 1 divides every integer. Another splendid sequence is (1,2,3,4,,n1,1). For each integer k in this sequence, other than the 1’s on the end and n1, the integers next to it are k1 and k+1, so their sum is (k1)+(k+1)=2k, which is a multiple of k. The integers next to n1 are n2 and 1, which have a sum of n1.

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 (a1,a2,,an) by x.

  1. Assume that x=(a1,a2,,an) is a splendid sequence. We will show that y=(a1,a2,,ai,c,ai+1,,an) is a splendid sequence when c=ai+ai+1.

    If some prime number p divides every integer in y, then it also divides every integer in x. Since x is a splendid sequence, there is no such prime number, so no prime number divides all of the integers in y.

    If i=1, then y=(a1,c,a2,a3,,an) and c=a1+a2. Since x is a splendid sequence, a1a2. We also have that a1a1, so a1(a1+a2) or a1c by Fact 2. Since every integer divides itself, c(a1+a2). To see that a2(c+a3), we note that a2(a1+a3) because x is splendid and a2a2 because every integer divides itself. By Fact 2, a2(a1+a2+a3) so a2(c+a3). The integers a3 through an all have exactly the same neighbours in y as they do in x, which is a splendid sequence, so y satisfies all other divisibility conditions required for it to be a splendid sequence.

    If i=n1, then y is splendid by a similar argument to the one in the previous paragraph.

    If 1<i<n1, then y=(a1,a2,,ai1,ai,c,ai+1,ai+2,,an). When k<i and when k>i+1, ak divides the sum of its neighbours because it has the exact same neighbours as it did in x. In y, the neighbours of the integer ai are ai1 and c. Since x is a splendid sequence, ai(ai1+ai+1). We also have that aiai, and so by Fact 2, ai(ai+ai1+ai+1) which means ai(ai1+c). By similar reasoning, ai+1(c+ai+2). The integer c is equal to the sum of its neighbours in y by definition, so it also divides the sum of its neighbours. Therefore, every integer in y divides the sum of its neighbours. We already argued that no prime number divides every integer in y, so y is a splendid sequence.

  2. Suppose x=(a1,a2,a3,,an) is a splendid sequence. If n=2, then the solution to part (a) implies that a1=an=1.

    Suppose n3. By definition, we have that anan1 and that an1(an2+an). By Fact 3, an(an2+an). Since anan, we can apply Fact 2 to get that an(an2+anan) which implies that anan2.

    Since x is splendid, we also have that an2(an3+an1). We have just shown that an divides an2, so by Fact 3, an(an3+an1). We also have that anan1, so Fact 2 implies an(an3+an1an1) or anan3. Continuing in this way, we can show that anai for all i with 1in. By the condition that no prime number can divide every integer in x, we conclude that an=1. Essentially the same argument shows that a1=1.

  3. Most of the work is to prove these two claims.

    Claim 1: If (a1,a2,,an) is a splendid sequence of length n3 that contains at least one integer that is greater than 1, then there is some i with 1<n such that ai=ai1+ai+1 and (a1,a2,,ai1,ai+1,ai+2,,an) 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 (a1,a2,,an) is a splendid sequence of length n2, then ai2n2 for every i.

    Proof of Claim 1. To prove Claim 1, suppose x=(a1,a2,,an) is a splendid sequence with at least one integer greater than 1 and let i be such that ai is the largest integer in the sequence, choosing the rightmost occurrence if there is a "tie". More precisely, i is the largest integer with the property that aiaj for all 1jn.

    By part (d), an=a1=1, and since there is at least one integer in x that is greater than 1, neither a1 nor an can be the largest integer in x, which means 1<i<n. The choice of i ensures that ai1ai and ai+1ai. If ai=ai+1, then since ai is the largest integer in the sequence, this would imply that ai is not the rightmost occurrence of the largest integer in the sequence. Therefore, we actually have that ai+1<ai.

    The inequalities ai1ai and ai+1<ai imply that ai1+ai+1<2ai and since x is splendid, ai(ai1+ai+1). As well, all integers in a splendid sequence are positive, which means that ai1+ai+1 is a positive multiple of ai that is less than 2ai. The only such multiple is ai itself, and so ai1+ai+1=ai.

    We have shown that one of the integers in x is equal to the sum of its neighbours. To finish proving the claim, we need to show that y=(a1,a2,,ai1,ai+1,ai+2,,an) is a splendid sequence. In y, only ai1 and ai+1 have different neighbours than they did in x, so the divisibility conditions we need to verify are that ai1(ai2+ai+1) and ai+1(ai1+ai+2)

    We know that ai1(ai2+ai) and we have just shown that ai=ai1+ai+1. Substituting, we get that ai1(ai2+ai1+ai+1). By Fact 2, ai1(ai2+ai1+ai+1ai1) or ai1(ai2+ai+1). A nearly identical argument shows that ai+1(ai1+ai+2). Therefore, y satisfies the divisibility conditions.

    If a prime number p divides every integer in y, then pai1 and pai+1, so pai by Fact 2 since ai=ai1+ai+1. This would mean p divides every integer in x, which is not the case since x 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 n+1 is at most twice the maximum size of an integer in a splendid sequence of length n. 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 n=2, n=3, and n=4. For n=2, we showed in the solution to part (a) that the only splendid sequence of length 2 is (1,1). The largest element in this sequence is 1=20=222=2n2, so the claim holds for n=2.

    Now suppose (a1,a2,a3) is a splendid sequence of length 3. If a1=a2=a3=1, then every integer in the sequence is less than 232=2. Otherwise, since a1=a3=1 by part (d), Claim 1 implies that a2=a1+a3=1+1=2 is the largest integer in the sequence, so all integers in the sequence are at most 2=232.

    Continuing to n=4, suppose (a1,a2,a3,a4) is a splendid sequence. Again, if the sequence consists entirely of 1’s, then ai242=4 for all i. Otherwise, either (a1,a3,a4) is a splendid sequence of length 3 and a2=a1+a3, or (a1,a2,a4) is a splendid sequence of length 3 and a3=a2+a4. Either way, three of the four integers are in a splendid sequence of length 3, and the fourth is the sum of two integers in a splendid sequence of length 3. We just showed that an integer in a splendid sequence of length 3 is at most 232, so an integer in a splendid sequence of length 4 is at most 232+232=2×232=242. Therefore, no integer in the sequence (a1,a2,a3,a4) can exceed 242.

    Now for the inductive step. Suppose, for some n2, that every integer in every splendid sequence of length n is at most 2n2. This is our inductive hypothesis. Consider a splendid sequence (a1,a2,,an,an+1) of length n+1. If ai=1 for all i, then ai2n2 for all i. Otherwise, Claim 1 implies that there is some i so that ai=ai1+ai+1 and (a1,a2,,ai1,ai+1,,an,an+1) is a splendid sequence of length n. By the inductive hypothesis, this means each of a1, a2, a3, , ai1, ai+1, , an, and an+1 is at most 2n2, and since 2n2<2(n+1)2, each of these integers is at most 2(n+1)2. For ai, we have ai=ai1+ai+1 and since ai12n2 and ai+12n2, we conclude that ai2n2+2n2=2(2n2)=2(n+1)2 as well. We have shown that every integer in a splendid sequence of length n+1 is at most 2(n+1)1. This completes the induction and the proof. ◻

    By Claim 2, every integer in a splendid sequence of length n is at most 2n2. There are only finitely many sequences of length n consisting of positive integers less than or equal to 2n2, regardless of whether they are splendid. Therefore, for fixed n, there are only finitely many splendid sequences of length n.

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.

  1. As pointed out in the hint, the number of splendid sequences of length n is equal to the (n1)st Catalan number. The nth Catalan number is equal to 1n+1(2nn), so the number of splendid sequences of length n is 1n(2n2n1). 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 n1, we call a sequence (b1,b2,,bn) of positive integers a tame sequence if b1=1 and bk+1bk+1 for every integer k with 1k<n. In other words, b1=1 and every other integer in the sequence is at most 1 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 n is equal to the nth 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 Tn denote the set of tame sequences of length n and Sn denote the set of splendid sequences of length n. We will show, for n2, that there is a bijection with domain Tn1 and codomain Sn. By the discussion in Appendix 1, this will show that the number of splendid sequences of length n is the (n1)st Catalan number.

    Recall from part (c) that if (a1,a2,,an) is a splendid sequence of length n, then (a1,a2,a3,,ai,ai+ai+1,ai+1,,an) is a splendid sequence of length n+1.

    From this point on, it will be notationally useful to prepend a zero at the beginning of splendid sequences. For example, the sequence (0,1) will now be the unique splendid sequence of length 1. The sequence (0,1,2,5,3,1) is a splendid sequence of length 5. This means that a splendid sequence of length n now has n+1 integers, the first of which is 0. For instance, a1=0, a2=1, a3=2, a4=5, a5=3, and a6=1 is how we would index the sequence (0,1,2,5,3,1) going forward. Notice that the observation from part (c) mentioned above also works if we insert the sum between the first and second integers, 0 and 1. You should convince yourself of this before moving on.

    For each n2, we define a function, fn, with domain Tn1 and codomain Sn. The way fn works is to use a tame sequence as a list of instructions to build a splendid sequence. Consider a tame sequence x=(b1,b2,,bn1) of length n1. Starting with (0,1), the unique splendid sequence of length 1, we read x 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 kth step, the integer bk tells us that we should insert a sum between abk and abk+1 to get a longer splendid sequence.

    For example, suppose n=6 and the tame sequence is x=(1,2,3,2,1,1). Start with (0,1), which has a1=0 and a1=1. The first integer in x is 1, so in the first step we insert the sum between a1 and a2. This means we go from (0,1) to (0,0+1,1)=(0,1,1). To start the second step, we reindex to a1=0, a2=1, and a3=1. The next integer in x is 2, so we insert the sum between a2 and a3 to get (0,1,1+1,1)=(0,1,2,1). The next integer in x is 3, so we insert the sum between the third and fourth integers in the current splendid sequence to get (0,1,2,2+1,1)=(0,1,2,3,1). Continuing, we get (0,1,1+2,2,3,1)=(0,1,3,2,3,1), followed by (0,0+1,1,3,2,3,1)=(0,1,1,3,2,3,1), and finally (0,0+1,1,1,3,2,3,1)=(0,1,1,1,3,2,3,1). Thus, f7(x)=(0,1,1,1,3,2,3,1).

    By part (c), if x is a tame sequence of length n1, then fn(x) is a splendid sequence of length n. Also note that at the start of the kth step, the splendid sequence has k+1 integers in it. Because of the way tame sequences are defined, the kth integer in a tame sequence is at most k, so at each step, the splendid sequence is always long enough for the instruction to makes sense.

    For each n2, we will show that the function fn 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 (a1,a2,a3,,an+1) of length n (remember that a1=0), we say that ai is a peak if ai=ai1+ai+1.

    By Claim 1 (see the solution to part (e)), every splendid sequence with an integer greater than 1 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 1, then the sequence is of the form (0,1,1,1,,1) and the first (leftmost) 1 is its only peak. If it is removed, the resulting shorter sequence is also splendid. Indeed, the reason for introducing the 0 at the beginning was to avoid having to treat the sequence of all 1’s separately in this part of the argument.

    Now for the useful fact:

    Claim 3: Suppose y=(a1,a2,,an+1) is a splendid sequence of length n and that x=(b1,b2,,bn1) is a tame sequence of length n1 such that fn(x)=y. If we let bn1=m, then am+1 is the leftmost peak of y.

    A proof of Claim 3 is given at the end. We will now prove by induction that fn is a bijection for all n2.

    It was observed in part (a) that the only splendid sequence of length 2 is y=(0,1,1). As well, the only tame sequence of length 21=1 is x=(1). It is easily checked that f2(x)=y. The sets T1 and S2 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, f2 is a bijection.

    For the inductive hypothesis, we assume for some n2 that fn is a bijection.

    We will show that fn+1 is a bijection, which means we need to show that it is injective and surjective. To show that it is surjective, we assume that y=(a1,a2,,an,an+1,an+2) is in Sn+1 and let ak be its leftmost peak. By Claim 1 from the solution to part (e), the sequence z=(a1,a2,,ak1,ak+1,,an,an+1,an+2) is in Sn. Since fn is a bijection by the inductive hypothesis, it is surjective, so there is some tame sequence w=(b1,b2,,bn1) in Tn1 with fn1(w)=z. For convenience, let m=bn1.

    Recall that the leftmost peak of x is ak. Note that k1 since a1=0 can never be a peak. Therefore, k2 and so k11.

    Suppose ar is the leftmost peak of z. If rk2, then ar is a peak of y because ar has the same neighbours in y and z when rk2. However, ak was chosen to be the leftmost peak of y, so we cannot have rk2. This means rk1, but by Claim 3, r=m+1, so we get k1m+1. Combining with 1k1, we have that 1k1m+1=bn1+1, which means the sequence (b1,b2,,bn1,k1) is a tame sequence. We will call this tame sequence x.

    To recap, the tame sequence x is obtained by appending k1 to w, the splendid sequence y is obtained by inserting the sum between the (k1)st and kth integer in z, and fn(w)=z. It follows that fn+1(x)=y. We have found xTn such that fn+1(x)=y. Since y was an arbitrary element of Sn+1, this concludes the proof that fn+1 is surjective.

    We will now show that fn+1 is injective. To do this, we suppose x=(b1,b2,,bn) and w=(c1,c2,,cn) are in Tn with fn+1(x)=fn+1(w). We will show that x=w.

    Let y=(a1,a2,,an+1,an+2) be such that y=fn+1(x)=fn+1(w). Suppose ak is the leftmost peak of y. By Claim 3, both cn=k1 and bn=k1. This shows that cn=bn. As well, if we set u=(b1,b2,,bn1) and v=(c1,c2,,cn1) and z=(a1,a2,,ak1,ak+1,,an+1,an+2), then fn(u)=fn(v)=z. By the inductive hypothesis, fn is bijective, and hence, it is injective, so u=v. This shows that x and w have the same first n1 integers, and since bn=cn as well, we have that x=w, which concludes the proof that fn+1 is injective.

    We have now shown that fn+1 is bijective, which proves that Tn1 and Sn have the same number of elements when n2. Therefore, the number of splendid sequences of length n is 1n(2n2n1) as claimed earlier.

    Proof of Claim 3. The proof is by induction on n. It was noted earlier that the only tame sequence of length 21=1 is x=(1) (b1=1), the only splendid sequence of length 2 is y=(0,1,1) (a1=0, a2=1, a3=1), and that f2(x)=y. The leftmost peak of y is a2 and 2=b1+1. This shows that Claim 3 is true when n=2.

    For the inductive hypothesis, we suppose, for some n2, that if y=(a1,a2,,an,an+1) is a splendid sequence of length n and x=(b1,b2,,bn1) is a tame sequence of length n1 such that fn(x)=y, then the leftmost peak of the y is am+1 where m=bn1.

    Suppose y=(a1,a2,,an,an+1,an+2) is a splendid sequence of length n+1 and that x=(b1,b2,,bn) is a tame sequence of length n with fn+1(x)=y. Because of how fn+1 is applied, am+1 is a peak of y. As well, z=(a1,a2,,am,am+2,,an+1,an+2) is a splendid sequence of length n such that fn(w)=z where w=(b1,b2,,bn1). For convenience, set bn=m and bn1=k. Suppose the leftmost peak of y is ar for some r. For now, assume r<m+1. It is not difficult to show that it is impossible for a splendid sequence to have two consecutive peaks. This means we must have rm1 since r must be at least two less than m+1. If this happens, ar is also a peak of z because am1 has exactly the same neighbours in z and y. By the inductive hypothesis, ak+1 is the leftmost peak of z, so r=k+1 and we get k+1m1. Since z is a tame sequence, bnbn1+1 or mk+1. This implies that mk+1m1 so mm1, which is impossible. Therefore, we cannot have r<m+1, which means am+1 is indeed the leftmost peak of y. This completes the induction and the proof. ◻

Appendix 1

Suppose X and Y 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 X, produces an element in the set Y. For instance, if the sets were X={(1,2),(5,3),(1,2)} and Y={(4,1),(5,2),(9,5)} (both sets of three ordered pairs), the "rule" might be "square the second entry, then reverse the order". With this rule, (1,2) becomes (4,1), (5,3) becomes (9,5), and (1,2) becomes (4,1), so every element of X is transformed into an element of Y. Such a rule is called a function. The set X is called its "domain" and Y is called its "codomain". If the function is named f, we would use f(x) to denote the function applied to an element x 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 f with domain X and codomain Y is called injective if for every two elements of the domain, x1 and x2, if x1x2, then f(x1)f(x2). 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 f(x1)=f(x2) and deduce that x1=x2. You might want to think about this logic.

Surjectivity: A function f with domain X and codomain Y is called surjective if for every yY there exists an xX so that f(x)=y. In other words, a function is surjective if every element of the codomain is the result of applying f to some element in the domain. [We might also say that the range equals the codomain to describe surjectivity.]

Bijectivity: A function f is with domain X and codomain Y 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 X and Y are finite sets and there is a bijective function f with domain X and codomain Y, then X and Y have the same number of elements. Indeed, if X has m elements and Y has n elements, then being injective implies that mn and being surjective implies that mn. Thus, being bijective implies that mnm, so m=n.

Observe that the example given at the beginning of this appendix is neither injective nor surjective, so it is not bijective. However, X and Y 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 X to Y, then they have the same number of elements. There are six bijective functions from X to Y, 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 n is equal to the nth Catalan number, 1n+1(2nn). 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 n, a sequence of 2n integers is called a jagged sequence of length 2n if properties P1 and P2 hold:

Claim 4: There are 1n+1(2nn) jagged sequences of length 2n.

Proof of Claim 4. Fix a positive integer n. Let X be the set of sequences of 2n integers that satisfy P1 and fail P2. Also, let Y be the set of sequences of 2n integers, n+1 of which equal 1 and n1 of which equal 1. We will show that X and Y have the same number of elements.

Suppose x=(a1,a2,,a2n) is in X. Since x fails P2, there must be some k with 1k2n and the property that the sum of the first k entries is negative. Let k be the smallest such position in the sequence. If a1=1, then k=1. This means n of the integers in the list a2,a3,,a2n are equal to 1, and n1 of them are equal to 1. Therefore, the sequence (a1,a2,a3,,a2n) has n+1 integers equal to 1 and n1 integers equal to 1, which means it is in Y.

If k1, then a10, a1+a20, and so on up to a1+a2++ak10, but a1+a2++ak<0. Since a1+a2++ak10 but a1+a2++ak1+ak<0, we must have that ak is negative, but ak=±1, so ak=1. As well, each of the ai are integers, so the two sums above are integers, which means a1+a2++ak1=0 and a1+a2++ak1+ak=1 (there is no other way to add 1 to a non negative integer and get a negative integer). The fact that a1+a2++ak1=0 implies that exactly half of the integers in the list a1,,ak1 are equal to 1, and so the number of 1’s in (a1,a2,,ak) is one more than the number of 1’s. Since the number of 1’s and 1’s is equal in x, this means the number of 1’s in (ak+1,,a2n) is one more than the number of 1’s. All of this implies that (a1,a2,,ak,ak+1,ak+2,,a2n) has two more 1’s than 1’s. Two numbers that differ by 2 and have a sum of 2n must be n1 and n+1, so the sequence above is in Y.

The above work defines a function, that we will call f, with domain X and codomain Y. Specifically, if x=(a1,a2,,a2n) in X and k the smallest integer such that a1+a2++ak<0, f(x)=(a1,a2,,ak,ak+1,,a2n). That is, f(x) is the sequence obtained by negating every integer from ak+1 to the end of the sequence. We will show that f is a bijection.

To see that f is injective, suppose w=(a1,a2,,a2n) and x=(b1,b2,,b2n) are in X with f(w)=f(x). We suppose that k is the smallest such that a1+a2++ak<0 and m is the smallest such that b1+b2++bm<0. We might as well assume that km. Our assumption says that the sequences (a1,a2,,ak,ak+1,ak+1,,a2n) and (b1,b2,,bk,bm+1,bm+1,,b2n) are equal. Since km, this means ai=bi when 1ik and when m+1i2n. Observe that a1+a2++ak=b1+b2++bk, and since a1+a2++ak<0 by assumption, we get that b1+b2++bk<0. This means mk as well and so k=m. Since ai=bi when 1ik and k+1i2n, we have that ai=bi for all i. In other words, w=x, so f is injective.

Now suppose y=(c1,c2,c3,,c2n) is a sequence is in Y. Because yY, exactly n+1 of the integers in y are equal to 1 and n1 of them are equal to 1. Consider the list of sums c1c1+c2c1+c2+c3c1+c2+c3++c2n The first "sum", c1, is either 1 or 1. The final sum is (n1)(n+1)=2. As we move from one sum to the next in the list above, we add ci for some i, which means the sums either increase or decrease by 1 as we move down the list. Therefore, there is at least one sum that equals 1 (it could be the first). Suppose k is the smallest such that c1+c2+c3++ck=1. Then the sequence x=(c1,c2,,ck,ck+1,ck+2,,c2n) is in X and f(x)=y. To see that xS, we have that c1+c2++ck=1 and c1+c2++c2n=2, ad so it must be that ck+1+ck+1++c2n=1. Therefore, c1+c2+c3++ck+(ck+1)+(ck+2)++(c2n)=0. This means x has the same number of 1’s and 1’s, which means there are n of each. As well, the sequence fails P2 because the first k integers have a negative sum. This shows that xX, and that f(x)=y is essentially by the definition of x. Therefore, f is surjective, which completes the proof that it is a bijection.

The number of sequences in Y is (2nn+1). This is because we can choose where to put the 1’s in (2nn+1) ways, and then there is no choice of where to place the 1’s. By what we have shown, we now know that there are (2nn+1) sequences in X as well.

We can now compute the number of jagged sequences. The number of sequences of 2n integers that satisfy P1 is (2nn) by reasoning similar to that in the previous paragraph. To get the number of jagged sequences of length 2n, we need to subtract from (2nn) the number of sequences that satisfy P1 but fail P2, which is exactly the number of sequences in X. Therefore, the number of jagged sequences is (2nn)(2nn+1)=(2n)!n!n!(2n)!(n+1)!(n1)!=(2n)!n!(n1)!(1n1n+1)=(2n)!n!(n1)!×1n(n+1)=1n+1×(2n)!n!n!=1n+1(2nn)

Claim 5: The number of tame sequences of length n is 1n+1(2nn).

Proof of Claim 5. We will find a bijection from the set of jagged sequences of length 2n to the number of tame sequences of length n.

Suppose x=(a1,a2,,a2n) is jagged and that i1<i2<<in are the indices where the 1’s occur. That is, ai1=ai2==ain=1 and all other integers in x are equal to 1. We will now define a sequence y=(b1,b2,b3,,bn) so that bk is the sum of the integers in x from a1 up to and including the kth integer equal to 1. In symbols, bk=a1+a2++aik.

Of the first ik integers in x, exactly k of them are equal to 1 and the other ikk of them are equal to 1. Therefore, their sum (which is bk by definition), is bk=k(ikk)=2kik. Thus, for a jagged sequence x=(a1,a2,,a2n), we define f(x) to be the sequence (b1,b2,,bn) where bk=2kik.

We will show that f is a bijection, but we first need to confirm that f(x) is always tame, which means we need to show that b1=1, bk1 for all k, and that bk+1bk+1 for all k<n. We know that a1=1 by P2, so this means i1=1 and b1=2(1)i1=21=1. Suppose ik2k. In x, there are only k 1’s up to and including aik, which means that among the first ik integers in x, there are at least as many 1’s as 1’s. This means the sum of the first ik integers cannot be positive. Therefore, we must have that ik<2k, and since both are integers, ik+12k, which rearranges to 12kik, which gives bk1. To see that bk+1bk+1, note that ik+1ik+1, so ikik+11. Then bk+1bk=2(k+1)ik+1(2kik)=2k+2ik+12k+ik=2+ikik+121=1 and so bk+1bk1 or bk+1bk+1. This completes the proof that f(x) is tame.

To see that f is injective, notice that bk=2kik can be rearranged to get ik=2kbk. In other words, if f(x)=y, then ik is uniquely determined from bk. This means that from y, the positions of the 1’s in x are uniquely determined, so the entirety of x is uniquely determined by y. This means there is only one x with the property that f(x)=y, so f is injective.

To see that f is surjective, suppose y=(b1,b2,,bn) is a tame sequence. For each k from 1 through n, define ik=2kbk, then define x=(a1,a2,,a2n) so that aj=1 if j=ik for some k, and aj=1 otherwise.

That f(x)=y follows by rearranging ik=2kbk to get bk=2kik. However, to conclude that f is surjective, we need to verify that x is indeed a jagged sequence.

By one of the conditions of tameness, b1=1, so so we have that i1=2(1)1=1. Using the assumption that bk+1bk+1 which can be rearranged to bkbk+11, we get that ik+1ik=2(k+1)bk+1(2kbk)=2k+2bk+12k+bk=2+bkbk+12+(1)=1 which means ik+1ik1 and it follows that ik+1>ik. Finally, since bn is positive, in=2nbn<2n. We have shown that 1=i1<i2<<in<2n. This shows that all of the ik are distinct, so x satisfies P1.

Rearranging ik=2kbk, we get bk=k(ikk), and by the reasoning from earlier, this means the sum of the first ik integers in x (always ending with the kth 1) is equal to bk, which is positive because y is tame. Now consider the sum a1+a2++am for some an arbitrary m with 1m2n. If m=ik for some k, then the sum is positive by the reasoning just given. Otherwise, there is some k for which ik<m<ik+1. Since every integer in x strictly between aik and aik+1 equals 1 by construction, we must have that a1+a2++ama1+a2++am+am+1++aik+11 because the latter is obtained from the former by adding some (possibly zero) 1’s. We know that aik+1=1 and that a1+a2++am+am+1++aik+11+aik+1 is positive, so this means a1+a2++am0.

We have shown that x satisfies P2 as well, so x is a jagged sequence with f(x)=y. Therefore, f is surjective, which completes the proof that it is bijective. Therefore, the number of tame sequences of length n is 1n+1(2nn). ◻