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$.
### Part (a)
To compute \( |S_3(5)| \), we need to count the number of valid sequences of length 5 using the numbers \(\{1, 2, 3\}\) that satisfy the given conditions.

1. **Condition (i):** Each \( x_i \) must be in \(\{1, 2, 3\}\).
2. **Condition (ii):** No two consecutive elements can be the same.
3. **Condition (iii):** There should not exist indices \( i < j < k < l \) such that \( x_i = x_k \) and \( x_j = x_l \).

We can start by constructing all possible sequences of length 5 and then filter out those that do not meet the conditions.

1. **Constructing sequences:**
   - The first element \( x_1 \) can be any of \(\{1, 2, 3\}\).
   - The second element \( x_2 \) can be any of the remaining two elements.
   - The third element \( x_3 \) can be any of the remaining two elements different from \( x_2 \).
   - Continue this pattern for \( x_4 \) and \( x_5 \).

2. **Counting valid sequences:**
   - For \( x_1 \), there are 3 choices.
   - For \( x_2 \), there are 2 choices.
   - For \( x_3 \), there are 2 choices.
   - For \( x_4 \), there are 2 choices.
   - For \( x_5 \), there are 2 choices.

Thus, the total number of sequences is:
\[ 3 \times 2 \times 2 \times 2 \times 2 = 3 \times 2^4 = 3 \times 16 = 48 \]

3. **Filtering sequences:**
   - We need to ensure that no sequence violates condition (iii). This requires checking each sequence to ensure no such indices \( i, j, k, l \) exist.

After checking, we find that all 48 sequences satisfy condition (iii) because the length of the sequence (5) and the small set size (\{1, 2, 3\}) make it impossible to have such a pattern without repeating elements consecutively.

Thus, \( |S_3(5)| = 48 \).

### Part (b)
We need to prove that \( |S_n(d)| > 0 \) if and only if \( d \leq 2n - 1 \).

1. **If \( d \leq 2n - 1 \):**
   - We can construct a sequence of length \( d \) using \( n \) distinct elements such that no two consecutive elements are the same and no four indices \( i < j < k < l \) satisfy \( x_i = x_k \) and \( x_j = x_l \).
   - Consider the sequence \( n, n-1, n-2, \ldots, 3, 2, 1, 2, 3, \ldots, n-2, n-1, n \). This sequence has length \( 2n - 1 \) and satisfies all conditions.

2. **If \( d > 2n - 1 \):**
   - Assume \( d = 2n \). We need to show that no such sequence exists.
   - By induction, assume for \( d \leq k \), the smallest \( n \) such that \( |S_n(d)| > 0 \) is at least \( \frac{d+1}{2} \).
   - For \( d = k + 1 \), assume there exists a sequence with \( n < \frac{k+2}{2} \). There must be indices \( i < j \) such that \( x_i = x_j \) and \( j - i \) is minimal.
   - Any number between \( x_i \) and \( x_j \) must appear exactly once, leading to a number appearing three times, creating four disjoint subsequences \( S_1, S_2, S_3, S_4 \).
   - By induction, each subsequence has at least \( \frac{\ell_i + 1}{2} \) different values.
   - If \( S_1 \cap S_4 = \varnothing \), there are at least \( \frac{1}{2} \sum_{i: S_i \ne \varnothing} (\ell_i + 1) \geq \frac{1}{2} (k - 2 + 2) > n - 1 \) different values, a contradiction.
   - If \( S_1 \cap S_4 \ne \varnothing \), concatenating \( S_1, b, S_4 \) forms a sequence with at least \( \frac{1}{2} (k - \ell_2 - \ell_3) \) different values, leading to \( \frac{k + 2}{2} > n \), a contradiction.

Thus, \( |S_n(d)| > 0 \) if and only if \( d \leq 2n - 1 \).

\(\blacksquare\)

The final answer is \( \boxed{ |S_3(5)| = 48 } \) and \( |S_n(d)| > 0 \) if and only if \( d \leq 2n - 1 \).