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$.
Problem
Source: Vietnam MO 2nd Day 1st Problem
Tags: combinatorics
12.01.2018 14:07
b. See here:https://artofproblemsolving.com/community/c6h1573809_a_other_way_to_state_part_b_p5_vmo_2018
12.01.2018 19:26
Part a. is simply bashing. Part b. First, we prove that if $d\leq 2n-1$ then $|S_n(d)|>0$ by showing the following sequence: $$n,n-1,n-2,\dots ,3,2,1,2,3,\dots ,n-2,n-1,n$$To complete the proof, we show that if $d=2n$ then such sequence does not exist. We prove by induction. For $d=1$ the situation is clear. Suppose we have proved that for all $d\leq k$, the smallest number $n$ such that $|S_n(d)|>0$ is not smaller than $\frac{d+1}{2}$. Assume on the contrary that for $d=k+1$, there exists such a sequence with $n<\frac{k+2}{2}$. Then there must exist indices $i<j$ such that $x_i=x_j$ and $j-i$ smallest possible. But then any number that is sandwiched between $x_i,x_j$ must appear exactly once, then there must be a number $b$ appears three times. This number cuts the sequence into four disjoint subsequences, let them be $S_1,S_2,S_3,S_4$: $$\{S_1\}b\{S_2\}b\{S_3\}b\{S_4\}$$Let $\ell_i$ be the length of sequence $S_i$. Then by the induction hypothesis, the sequence is empty xor it has at least $v_i\geq \frac{\ell_i+1}{2}$ different values. We have the following scenarios: $\bullet\quad S_1\cap S_4=\varnothing$. Then there are at least$$\frac{1}{2}\sum_{i:S_i\ne\varnothing}{(\ell_i+1)}\geq\frac{1}{2}\left(\left(\sum_{i:S_i\ne\varnothing}{\ell_i}\right)+2\right)=\frac{1}{2}(k-2+2)>n-1$$different values beside $b$, contradiction. $\bullet\quad S_1\cap S_4\ne\varnothing$. If we concatenate $S_1,b,S_4$ to form a sequence with length $k-\ell_2-\ell_3-1$ then it has at least $\frac{1}{2}(k-\ell_2-\ell_3)$ different values. Thus there are at least$$\frac{1}{2}(\ell_2+\ell_3+2+k-\ell_2-\ell_3)=\frac{k+2}{2}>n$$different values beside $b$, contradiction.
13.01.2018 11:17
I've just noticed an easier approach :'( [...]Assume in the contrary that for $d=k+1$, there exist such a sequence with $n<\frac{k+2}{2}$. If $k$ is even, then $n\leq \frac{k}{2}$. But among any $k$ consecutive numbers are $\frac{k+1}{2}$ distinct values, contradiction. If $k$ is odd, then $n\leq\frac{k+1}{2}$. Then there must be $i\in\{1,2,\dots ,k-1\}$ such that $x_i=x_{k+1}$. From $x_1$ to $x_{i-1}$ they have at least $\frac{i}{2}$ distinct values, while from $x_{i+1}$ to $x_k$ they have at least $\frac{k-i}{2}$. but $\{x_1,\dots ,x_{i-1}\}\cap\{x_{i+1},\dots ,x_k\}=\varnothing$, then the sequence has $\lceil\frac{i+k-i}{2}\rceil=\frac{k+1}{2}$ distinct values not including $x_i$ and $x_{k+1}$, contradiction.
25.07.2019 12:01
Here is the solution for part a Solution We consider 2 cases: Case 1: If the first 3 numbers are distinct, we can consider $(x_1; x_2; x_3) = (1; 2; 3)$. If $x_4 = 1$ then there no way to choose $x_5$ Then: $x_4 = 2$ and we can choose $x_5 = 1$ Since there are 6 ways to choose $(x_1; x_2; x_3)$ so we have 6 sets which satisfy this case Case 2: If there are 2 numbers in the first 3 numbers which are equal, we can consider $(x_1; x_2; x_3) = (1; 2; 1)$. Then $x_4 \ne 1$, $x_4 \ne 2$ or $x_4 = 3$. So $x_5 = 1$ then we have 1 set satisfies. But there are 6 way to choose $(x_1; x_2; x_3)$ so we have 6 sets satisfy this case Hence: $|S_3(5)| = 12$