Problem

Source: Vietnam MO 2nd Day 1st Problem

Tags: combinatorics



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$.