MathDB

5

Part of 2018 Vietnam National Olympiad

Problems(1)

VMO 2018 P5

Source: Vietnam MO 2nd Day 1st Problem

1/12/2018
For two positive integers nn and dd, let Sn(d)S_n(d) be the set of all ordered dd-tuples (x1,x2,…,xd)(x_1,x_2,\dots ,x_d) that satisfy all of the following conditions: i. xi∈{1,2,…,n}x_i\in \{1,2,\dots ,n\} for every i∈{1,2,…,d}i\in\{1,2,\dots ,d\}; ii. xi≠xi+1x_i\ne x_{i+1} for every i∈{1,2,…,d−1}i\in\{1,2,\dots ,d-1\}; iii. There does not exist i,j,k,l∈{1,2,…,d}i,j,k,l\in\{1,2,\dots ,d\} such that i<j<k<li<j<k<l and xi=xk, xj=xlx_i=x_k,\, x_j=x_l; a. Compute ∣S3(5)∣|S_3(5)| b. Prove that ∣Sn(d)∣>0|S_n(d)|>0 if and only if d≤2n−1d\leq 2n-1.
combinatorics