VMO 2018 Problem 5

For two positive integers $n$ and $d$ , let $S_n(d)$ be the set of all ordered $d$ -tuples $(x_1,x_2,\dots ,x_d)$ that satisfy all of the following conditions: i. $x_i\in \{1,2,\dots ,n\}$ for every $i\in\{1,2,\dots ,d\}$ ; ii. $x_i\ne x_{i+1}$ for every $i\in\{1,2,\dots ,d-1\}$ ; iii. There does not exist $i,j,k,l\in\{1,2,\dots ,d\}$ such that $i<j<k<l$ and $x_i=x_k, x_j=x_l$ ; a. Compute $|S_3(5)|$ b. Prove that $|S_n(d)|>0$ if and only if $d\leq 2n-1$ .