Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

A full sequence have to start with $1$ Because for all $k\geq2$ the first occurrence of $k-1$ comes before the last occurrence of $k$. The next term in the sequence can be $1$ or $2$. And if our term is $k$ the next term can be $k$ or $k+1$ - $2$ options each time we adding a term So for each $n$ the number of full sequences equal to ${2^{n-1}}$

The answer is $n!$. To prove it we'll find a bijection between the permutations of $1, 2, \ldots, n$ and the full sequences of length $n$. Take an arbitrary full sequence of length $n$ and assign it a permutation of $1, 2, \ldots, n$ as follows: first number the $1$s in the sequence from right to left, then the $2$s from right to left, and so on (for example, the full sequence $213244$ becomes $314265$). Now, it's easy to see that the transformation is reversible: take a permutation of $1, 2, \ldots, n$ and label the $1$ with a $1$. From then on, if the last number we've looked at is $k$ (suppose we've labeled it $m$), we look at $k+1$; if $k+1$ is to the right of $k$ in the permutation we label it $m+1$, otherwise we label it $m$. It is easy to check that this procedure gives a full sequence, and that if we apply the first transformation to it, we get back the original permutation. So this gives a bijection between the two sets and we're done.

Severius wrote: first number the $1$s in the sequence from right to left, then the $2$s from right to left, and so on (for example, the full sequence $213244$ becomes $314265$). I don't really understand your construction, HOW exactly are you assigning a permutation to a full sequence?

Well... you take the full sequence. First, you look at just its $1$s, and number them from right to left; that is, you assign $1$ to the rightmost $1$, $2$ to the following $1$ to the left, ..., $k$ to the leftmost $1$, where there are $k$ $1$s in the sequence. Then, you number the $2$s in the same fashion, but the first number you assign is $k+1$ (which goes to the rightmost $2$), then $k+2$, and so on; the leftmost $2$ is assigned $k+m$, where there are $m$ $2$s. We proceed like this until the whole sequence is numbered. Then, for example, $2211124334$ becomes $653214(10)879$, if I've done it right.

Oh, I get it. That's clever.

pavel25 wrote: A full sequence have to start with $1$ Because for all $k\geq2$ the first occurrence of $k-1$ comes before the last occurrence of $k$. The next term in the sequence can be $1$ or $2$. And if our term is $k$ the next term can be $k$ or $k+1$ - $2$ options each time we adding a term So for each $n$ the number of full sequences equal to ${2^{n-1}}$ Aha, I see the problem with your logic. Notice that the third term can be $1, 2$, or $3$ because the problem only stipulates the first and last occurrences of $k-1, k$ respectively, so there are $p$ possibilities for the $p^{th}$ term and the answer is $n!$ as stated above.

orl wrote: Let $n$ be a positive integer. A sequence of $n$ positive integers (not necessarily distinct) is called full if it satisfies the following condition: for each positive integer $k\geq2$, if the number $k$ appears in the sequence then so does the number $k-1$, and moreover the first occurrence of $k-1$ comes before the last occurrence of $k$. For each $n$, how many full sequences are there ? we want to determaine the $F_n$ we circle the place of the greatest number then we choose $i$ places from $n$ places and then we put the $n-i$ number4s left in $F{}_n{}_-{}_i$ ways and now the $i$ places: $i)$one of them be the greatest one $ii)$two of them be the greatest one . . . $\Rightarrow F_n=\sum\limits_{i=1}^n{{{n}\choose{i}}F{}_n{}_-{}_i}$

Here's a boring solution. Let $ a_{n}$ be the desired number of full sequences of length $ n$. We show that $ a_{n} = na_{n - 1}$. It will follow easily by induction that $ a_{n} = n!$ for all $ n$. Let our sequence be $ x_{1},x_{2},\ldots,x_{n}$. Clearly, some term in the sequence must be 1. Let $ x_{i} = 1$, such that $ i$ is maximal. We claim that the number of ways to fill in the other $ n - 1$ values of the sequence is $ a_{n - 1}$. This will prove the claim, as we just sum this from $ i = 1$ to $ i = n$ to get $ na_{n - 1}$. We will show a bijection between $ (x_{1},x_{2},\ldots,x_{i - 1},x_{i + 1},x_{i + 2},\ldots,x_{n})$ and full sequences of length $ n - 1$. If we take our full sequence of length $ n$, note that $ (x_{1},x_{2},\ldots,x_{i - 1},x_{i + 1},x_{i + 2},\ldots,x_{n})$ satisfies the full sequence conditions for $ k\ge3$, and if one of $ x_{1},x_{2},\ldots,x_{i - 1}$ is equal to 1 (since we took $ i$ maximal, none of the other terms are), then it satisfies the full sequence conditions for $ k\ge2$, and is a full sequence by itself. On the other hand, if $ x_{i}$ is the only 1 in our original full sequence, the minimum value of the other terms is 2 (note that there must be a 2, or else every term would be a 1), and we can subtract 1 from every term to get a full sequence of length $ n - 1$. Thus, each full sequence of length $ n$ with $ x_{i} = 1$ maps to a full sequence of length $ n - 1$. We see that no two full sequences of length $ n$ map to the same full sequence of length $ n - 1$: if they're the same, then either the full sequences of length $ n$ are the same, or if they are translations, we have a full sequence that is the result of adding 1 to every non $ x_{i}$ term of another full sequence, which is not possible because we need a 2 in $ (x_{i + 1},\ldots,x_{n})$, meaning we had a 1 in this subsequence in the original full sequence, contradicting the maximality of $ i$ (WOW that was run-on). For the other direction, we show that every full sequence of length $ n - 1$ maps to a unique full sequence of length $ n$. Things basically work backwards the same way, if there is a 1 in the last $ n - i$ terms of our full sequence of length $ n - 1$, add 1 to every term, and stick in a 1 in the appropriate place to get a full sequence of length $ n$. If not, stick in the 1 without doing anything. Note that the resulting full sequences are unique because if two sequences of length $ n - 1$ map to the same sequence of length $ n$, they must be translations of each other, and one doesn't contain a 1 and is not a full sequence. So we're done.

Here is another induction solution : Let $\chi_k ^n (i,j)$ denote the number of full sequences of length $n$, with maximal element $k$, first appearance of $k$ is at $i$, and last appearance is at $j$. Its easy to that $i=j$, then $k \ge 2$ ans if $k$ appears more than once in any of the full sequences in $\chi_k ^n (i,j)$, then $1 \le k \le n-1$. We want to find $T_n = \sum _{1 \le i \le j \le n} \sum_{k=1}^{n}\chi_k ^n (i,j) = \sum _{2 \le i = j \le n} \sum_{k=1}^{n}\chi_k ^n (i,j) + \sum _{1 < i \le j \le n} \sum_{k=1}^{n}\chi_k ^n (i,j)$ (*) Lemma 1: $\sum _{2 \le i = j \le n} \sum_{k=1}^{n}\chi_k ^n (i,j) = \sum _{2 \le i = j \le n} \sum_{k=2}^{n}\chi_k ^n (i,j)= \sum _{1 \le p \le q \le n-1}\sum_{k=2}^{n}(n-p) \chi_{k-1}^{n-1}(p,q)$ $ = \sum _{1 \le p \le q \le n-1}\sum_{k=1}^{n-1}(n-p) \chi_{k}^{n-1}(p,q) $ Proof: If we remove $k$, by a bijection we see the following : $\chi_k ^n (i,i) = \sum_{1 \le p \le i-1} \chi_{k-1}^{n-1}(p,q) $ $ \sum_{1 \le i \le n}\chi_k ^n (i,i) = \sum_{a=2}^{n}\sum_{p=1}^{a-1} \chi_{k-1}^{n-1}(p,q) = \sum _{1 \le p \le q \le n-1}(n-p) \chi_{k-1}^{n-1}(p,q)$ So indeed $ \sum _{2 \le i = j \le n} \sum_{k=2}^{n}\chi_k ^n (i,j)= \sum _{1 \le p \le q \le n-1}\sum_{k=2}^{n}(n-p) \chi_{k-1}^{n-1}(p,q)$ Lemma 2: $\sum_{k=1}^{n-1} \sum _{1 \le i < j \le n-1} \chi_k^n (i,j) = \sum _{1 \le p \le q \le n-1 } \sum_{k=1}^{n-1} p \; \chi_{k}^{n-1} (p,q)$ Proof : If we remove the first $k$, by a bijection we see the following : ${\chi_k ^n (i,j)}_{i<j} = \sum_{p=a}^{b-1} \chi_{k}^{n-1} (p, b-1) $ So $\sum _{1 \le i < j \le n-1 }\chi_k ^n (i,j) = \sum_{b=2}^{n} \sum_{a=1}^{b-1} \sum_{p=a}^{b-1} \chi_{k}^{n-1} (p, b-1) $ $= \sum_{b=2}^{n} \sum_{p=1}^{b-1} p \; \chi_{k}^{n-1} (p, b-1) $ $= \sum_{1 \le p \le q \le n-1} p \: \chi_k ^{n-1} (p,q)$ So summing over all $k$, we get $\sum_{k=1}^{n-1} \sum _{1 \le i < j \le n-1} \chi_k^n (i,j) = \sum _{1 \le p \le q \le n-1 } \sum_{k=1}^{n-1} p \; \chi_{k}^{n-1} (p,q)$ Using both the lemmas in (*) we get $T_n = \sum _{1 \le i \le j \le n} \sum_{k=1}^{n}\chi_k ^n (i,j) = n\; \sum _{1 \le p \le q \le n-1} \sum_{k=1}^{n-1}\chi_k ^{n-1} (p,q) = n T_{n-1} $ So $T_n = n!$

There is a quick bijection between these sequences and the permutations of $1,2,...,n$!! For such a sequence with numbers from $1$ to $k$, we write: the position of the first $k$, then the position of the second $k$, ..., then the position of the last $k$, then the position of the first $k-1$, ..., then the position of the last $k-1$, ..., then the position of the first $1$, ..., then the position of the last $1$. For any permutation, look at its first number and write a $k$ in that position. If the next number is bigger, write a second $k$ in that position, otherwise write a $k-1$ in that position. Continue like this. Everytime the number increases, rewrite the number you just wrote in that position. Otherwise, write that number minus $1$, in that position. at the end you can deduce value of $k$ This is thus a bijection so $\boxed{n!}$ is answer!

Severius wrote: The answer is $n!$. To prove it we'll find a bijection between the permutations of $1, 2, \ldots, n$ and the full sequences of length $n$. Take an arbitrary full sequence of length $n$ and assign it a permutation of $1, 2, \ldots, n$ as follows: first number the $1$s in the sequence from right to left, then the $2$s from right to left, and so on (for example, the full sequence $213244$ becomes $314265$). Now, it's easy to see that the transformation is reversible: take a permutation of $1, 2, \ldots, n$ and label the $1$ with a $1$. From then on, if the last number we've looked at is $k$ (suppose we've labeled it $m$), we look at $k+1$; if $k+1$ is to the right of $k$ in the permutation we label it $m+1$, otherwise we label it $m$. It is easy to check that this procedure gives a full sequence, and that if we apply the first transformation to it, we get back the original permutation. So this gives a bijection between the two sets and we're done. What is the motivation for this bijection? Thank you very much! Also, does the following solution work? By removing the largest integer that first appears from a full sequence of length $n$, we get a full sequence with length $n-1$. For each full sequence with length $n-1$, there are $n$ ways to make it a full sequence with length $n$, so $a_n=na_{n-1}$, where $a_n$ is the number of full sequences, so $a_n=n!$

We will show that if there are $s_n$ full sequences, then $s_{n+1}=(n+1)s_n$, which will show $s_n=n!$. Consider the $s_n$ sequences, and consider any arbitrary full sequence $a_1\ldots a_n$. For any $0\le i\le n$, consider the new sequence $a_1\ldots a_iba_{i+1}\ldots a_{n}$, where $b=\max(1+\max(a_1,\ldots, a_i),\max(a_{i+1},\ldots, a_{n}))$ (Here, let the maximum of $0$ numbers to be $0$). We will show that this new sequence is a full sequence of length $n+1$. The first condition is fulfilled because $\max(a_1,\ldots, a_n,b)\le \max(a_1,\ldots, a_n)+1$. Also, the first occurrence of any number $k\le \max(a_1,\ldots, a_n)$, the second condition is fulfilled. We only need to check if $b=\max(a_1,\ldots, a_n)+1$ and $k=b$, but then we must have $b=1+\max(a_1,\ldots, a_i)$ so then our second condition is filled. Hence, each full sequence of length $n$, there are $n+1$ corresponding full sequences of length $n+1$. It suffices to show that for any full sequence of length $n+1$, say $c_1\ldots c_{n+1}$ there is a unique number in the $c_{j+1}$, $1\le j\le n+1$, such that $c_{j+1}=\max(1+\max(c_1,\ldots, c_j), \max(c_{j+2},\ldots, c_{n+1}))$ (Once again, the maximum of $0$ numbers is $0$), and that this sequence $c_1\ldots c_jc_{j+2}\ldots c_{n+1}$ is still full. We will show that $c_{j+1}$ is in fact the first occurrence of $\max(c_1,\ldots c_{n+1})$. If $c_{j+1}$ is not the maximum, then there is an occurrence of $c_{j+1}+1$ after it by assumption, which contradicts that $c_{j+1}< \max(c_{j+2},\ldots, c_{n+1})$. If $c_{j+1}$ is not the first occurrence of the maximum, then clearly $c_{j+1}<1+\max(c_1,\ldots, c_j)$. Now, we show that if $c_{j+1}$ is the first occurrence of the maximum, then $c_{j+1}=\max(1+\max(c_1,\ldots, c_j), \max(c_{j+2},\ldots, c_{n+1}))$. In fact, if there is only one occurrence of the maximum, then, $c_{j+1}=1+\max(c_1,\ldots, c_j)$ by assumption, and if there is more than one occurrence, then $c_{j+1}=\max(c_{j+2},\ldots, c_{n+1})$. Furthermore, it's clear that the sequence $c_1\ldots c_jc_{j+2}\ldots c_{n+1}$ is a full sequence of length $n$, so we are done.

The answer is $n!$. We will establish a bijection between permutations of $1,2,\ldots,n$ and full sequences of length $n$. Take a full sequence, and suppose that $i$ appears $a_i$ times. Replace the $j$th occurrence of $i$ in the full sequence with $a_1+a_2+\ldots+a_i+j$. The resulting sequence is clearly a permutation of $1,2,\ldots,n$ since every number we write is different and ranges from 1 to n. Also, this process is reversible and this shows that this is a bijection. Just take a permutation and let $1,2,\ldots,a_1$ be a subsequence, with $a_1$ as large as possible and replace all of those numbers with 1. Then, let $a_1+1,a_1+2,\ldots,a_1+a_2$ be a subsequence, with $a_2$ as large as possible and replace all of those numbers with 2, and so on. Clearly, the last $k-1$ must occur after the first $k$, or else the first $k$ would be a $k-1$ instead, so this is a full sequence. Hence, we have the answer is $n!$.

I really liked CantonMathGuy's solution.But can someone check this solution?(Because recursive solutions for this problem dont seem easy .) MathPanda1 wrote: Also, does the following solution work? By removing the largest integer that first appears from a full sequence of length $n$, we get a full sequence with length $n-1$. For each full sequence with length $n-1$, there are $n$ ways to make it a full sequence with length $n$, so $a_n=na_{n-1}$, where $a_n$ is the number of full sequences, so $a_n=n!$

Wait, $n!$ sequences? Am I misreading the problem or what? Somebody, please tell me which sequences am I missing.

.

@below Thanks

Wizard_32 wrote: Wait, $n!$ sequences? Am I misreading the problem or what? Somebody, please tell me which sequences am I missing.

.

. You are missing a lot of them. 1121,1211,1221,2121,1213,1231,1232,2312,2132 And for the other one you didnt write 121

I claim there are $n!$ full sequences. To do this, we establish a bijection between the set of full sequences of length $n$ and the set of permutations of $\{1,2,\ldots,n\}$. Begin with a permutation $P$ of $\{1,2,\ldots,n\}$ and partition it into decreasing subsequences of consecutive integers. For example, the permutation $13542$ would be partitioned into $[1], [3,2], [5,4]$. Number these subsequences $s_1,s_2,\ldots,s_k$ by increasing order of maximal element. Now, each $1 \leq i \leq n$ is in exactly one $s_j$. For each $i$ in the permutation, replace $i$ with $j$ where $i \in s_j$. In the above example, $13542$ would map to $12332$. We now prove that this sequence is full. Take some permutation $P$ and two subsequences $s_k$ and $s_{k-1}$ in its partition. We must show that the first element of $s_{k-1}$ comes before the last element of $s_k$. However, the last element of $s_k$ is one greater than the first element of $s_{k-1}$. This means that if the first element of $s_{k-1}$ came after the last element of $s_k$, the last element of $s_k$ would be in $s_{k-1}$, contradiction. Thus, the produced sequence is full. This process is easily reversible: begin with a full sequence of length $n$ and say there are $a_i$ occurrences of $i$ for each $i$. Then, create a permutation of $\{1,2,\ldots,n\}$ by, for each $i$, first numbering each occurrence of $i$ in descending order then adding $\sum_{j=1}^{i-1} a_j$ to the result. For example, the sequence $12332$ gives $a_1=1,a_2=2,a_3=3$, so it corresponds to the permutation $1(1+2)(3+2)(3+1)(1+1)=13542$, as desired.

tenplusten wrote: I really liked CantonMathGuy's solution.But can someone check this solution?(Because recursive solutions for this problem dont seem easy .) MathPanda1 wrote: Also, does the following solution work? By removing the largest integer that first appears from a full sequence of length $n$, we get a full sequence with length $n-1$. For each full sequence with length $n-1$, there are $n$ ways to make it a full sequence with length $n$, so $a_n=na_{n-1}$, where $a_n$ is the number of full sequences, so $a_n=n!$ This is exactly what i did! To elaborate more, one takes a full sequence of length $n$ and remove the first occurrence of the largest number in the sequence giving us a $n-1$ number sequence which is obviously also full. Then notice that for a $n-1$ number full sequence, there are $n$ places where we can put a new number, however this number is fixed with respect to this position since it has to be the first occurrence of the largest number in the $n$ number sequence it is going to be a part of.

We solve this question by recurrence. Take any full sequence of length $n-1.$ Now, consider any one of the integers in the sequence. Now, we want to place a number to the right of it so that it is the first time the largest number appears in the new sequence. For example, in $212332$ we can place a $4$ between the two $3$'s to get $2123432.$ Now, we claim that in each of these integers, there is exactly one integer you can insert such that the resulting sequence is full. $~$ Obviously, this number you are inserting, it must be at most one more than the largest integer currently on the list, and it must be at least the largest integer currently on the list. Suppose $k$ is the current largest integer. If there are any $k$'s to the left of where you are inserting the new number, then inserting a $k$ won't work. On the other hand, if there aren't any $k$'s to the left and you insert a $k+1$ then the sequence won't be full. $~$ Now, note that the left-most space cannot have a number inserted in this way, so for each full sequence of length $n-1$ you can make $n$ full sequences of length $n.$ Also note that each full sequence of length $n$ there is only one full sequence of length $n-1$ that can be made into this sequence, because you must remove the first time the large integer appears. Now, since there is $1$ full sequence of length $1$ there are $n!$ full sequences of length $n.$

@above why does the newly inserted integer need to be at least the largest integer in the old sequence?

DAM. The answer is $n!$. We construct a bijection between full sequences with largest term k and terms $a_1,a_2,\dots,a_n$ in those spots, with permutations of $1,2,\dots,n$. Break the permutation of 1->n into maximal increasing subsequences; suppose there are $k$ of them. Then, for $1\le i\le k$, the indices $j$ for which $a_j=i$ in our full sequence are exactly the numbers in the $i$th maximal increasing subsequence, where increasing subsequences are read left to right but the order of each subsequence block is read right to left. As an example, (6)(4)(237)(5)(1) goes to 1334253 ((1) goes to 1, (5) goes to 5th place in the second sequence with value 2 since it's the second subsequence, etc.), and (56{10})(7)(24)(39)(8)(1) goes to 1434665236; it's obvious that this works and that it's reversible, since the first occurrence of k-1 in the full sequence is the k-1th subsequence, which indeed occurs before the kth subsequence. The problem is now evident, since there are n! ways for the permutations. also when awesomeming just gets nodiffed by a user who has 1 post :skull: jk dont block me like calvin is threatening to its a joke you probably dont check feed cuz u have too many isls that they would all be unread and you cant read all them

We give a bijection between full sequences and permutations of $\{1,\dots,n\}$, proving the answer is $n!$. Take a full sequence. For each number $i$ in the sequence from the largest number $k$ first down to $1$ last, repeat the following algorithm: Take the first appearance of $i$ not already processed. In the permutation of $\{1,\dots,n\}$, assign to this position the smallest number not already assigned. Hence a sequence $\{3,5,1,2,3,4,4,6,5,5\}$ is reassigned to $\{7,2,10,9,8,5,6,1,3,4\}$. Now take a permutation of $\{1,\dots,n\}$. Repeat the following algorithm: Sweep from left to right, appending the position of the smallest unprocessed number to a temporary list if we encounter it. These positions will all contain the same value. Specifically, the $k$th-to-last sweep contains the value $k$. Notice that the last occurrence in the $k-1$th sweep comes after the first occurrence in the $k$th sweep; that is, the first occurrence of $a-1$ in the new sequence comes before the last occurrence of $a$. Hence the sequence is indeed full. Injectivity is proved by this argument---there is a bijection. $\blacksquare$