Câu hỏi 21
$n$ là số nguyên dương. Một chuỗi độ dài phổ quát $m$ là một chuỗi $m$ mỗi số nguyên giữa $1$ và $n$ để người ta có thể có được bất kỳ sự hoán vị nào của $1, 2, \ldots, n$ bằng cách xóa các thành viên phù hợp của trình tự. Ví dụ, $1, 2, 3, 1, 2, 1, 3$ là một chuỗi phổ quát có độ dài $7$ cho $n = 3$. Nhưng $1, 2, 3, 2, 1, 3, 1$ không phải là phổ quát, bởi vì người ta không thể có được hoán vị $3, 1, 2$. Chứng minh rằng người ta luôn có thể có được một chuỗi phổ quát cho $n$ có độ dài $n^2 - n + 1$. Chứng minh rằng một chuỗi phổ quát cho $n$ phải có độ dài ít nhất là $n(n + 1) / 2$. Chứng minh rằng trình tự ngắn nhất cho $n = 4$ có thành viên $12$. [Bạn được cho biết, nhưng không cần phải chứng minh rằng có một chuỗi phổ quát cho $n$ có độ dài $n^2 - 2n + 4$.]