VMO

a) To calculate $S_3(5)$, we need to count the number of $(a,b,c,d,e)$ such that $a,b,c,d,e\in \{1,2,3\}$ and satisfy the conditions ii), iii). We investigate these two cases.

If the first 3 terms are distinct, we consider the case where $(a,b,c)=(1,2,3)$ represents. For $(1,2,3,d,e)$ then $d=1$ or $d=2$, but if $d=1$ then there is no choice for $e$. Hence, $d=2$ and $e=1$. So this case has only one satisfying set. Note that there are $3!=6$ ways to choose for $(a,b,c)$ so there are 6 satisfying tuples.

If there are two identical numbers in the first 3 terms, we consider $(a,b,c)=(1,2,1)$ to represent. With set $(1,2,1,d,e)$, we see that $d$ cannot be 1 or 2 so $d=3$, thus $e=1$. Similarly, we can compute that there are exactly 6 satisfying sets.

Thus, $|S_3(5)|=6+6=12$.

b) Call a set beautiful if it satisfies the given conditions. We will prove that the necessary and sufficient conditions for the existence of a nice set of numbers in the set $S_n(d)$ are $d\le 2n-1$.

Sufficient condition. For $d=2n-1$, we consider a set of numbers of the form

$1,2,3,\dots ,n-1,n,n-1,\dots ,3,2,1.$

By direct checking, we obtain that the upper set is beautiful. It follows that for every $1\le d\le 2n-1$, the set $S_n(d)$ is non-empty.

Necessary condition. To prove $S_n(d)=\varnothing$ when $d\ge 2n$, we only need to prove that there is no satisfying tuple when $d=2n$. We will prove this by induction.

For $n=1,d=2$, the statement is clearly true. Assume that for every $1\le k\le n$, there does not exist a beautiful tuple when $d=2k$. We will show that this is also true for $k=n+1$. Suppose that there exists a beautiful tuple for $d=2k=2(n+1)$, which is $(x_1,x_2,\dots ,x_{2n+2})$ then let $S$ be the number of the occurrences of the element $n+1$ in that tuple, we have the following cases:

If $S=0$ then this nice tuple has length $2n+2$ but the elements only take values not exceed $n$, which is a contradiction.

If $S=1$. If $n+1$ is at the beginning or the end of the tuple, we delete it and the new set is also beautiful with the length is $2n+1$, which is a contradiction. Therefore, the position of $n+1$ must be centered with the form

$$(\ast \ast \ast ,u,n+1,v,\ast \ast \ast )$$

If $u\ne v$ then deleting $n+1$ again as above; and if $u=v$, removing $n+1$ along with $u$ or $v$ (so that no two equal numbers are next to each other), then the new set is also beautiful and has a length of $2n$, which is a contradiction.

From the above argument, we observe that it is impossible for any value to appear exactly one time. Therefore, if $S=2$ then all the values $1,2,3,\dots ,n+1$ appear exactly two times in the tuple. Let $T$ be the number between two elements $n+1$ in the form

$$\ast \ast \ast ,n+1,\underset{T\text{ numbers}}{\underbrace{\ast \ast \ast }},n+1,\ast \ast \ast$$

then it is clear that the outer numbers must be different from these $T$ numbers. Without loss of generality, suppose that these number takes the value of $\{1,2,\dots ,m\}$, then $T=2m<2n$ and these numbers form a new beautiful tuple, which is a contradiction.

If $S\ge 3$, by the above argument, this case does not happen.

Therefore, in all cases, the assertion is true. Thus, $|S_n(d)|>0$ if and only if $d\le 2n-1$. $\square$