Câu hỏi 8
(USA 1) Từ một nhóm $n$ người, chọn $q$ đội hai người phân biệt và xếp hạng $1,\ldots,q$ (không đồng hạng). Gọi $m$ là số nguyên nhỏ nhất lớn hơn hoặc bằng $2q/n$. Chứng minh có thể liệt kê $m$ đội phân biệt sao cho (i) mỗi cặp đội liên tiếp trong danh sách có một thành viên chung và (ii) dãy đội trong danh sách theo thứ tự xếp hạng.
Cách phát biểu khác. Cho một đồ thị có $n$ đỉnh và $q$ cạnh được đánh số $1,\ldots,q$, chứng minh tồn tại một chuỗi gồm $m$ cạnh, $m\ge2q/n$, mỗi hai cạnh liên tiếp có một đỉnh chung, được sắp đơn điệu theo số thứ tự.
Cách phát biểu khác. Cho một đồ thị có $n$ đỉnh và $q$ cạnh được đánh số $1,\ldots,q$, chứng minh tồn tại một chuỗi gồm $m$ cạnh, $m\ge2q/n$, mỗi hai cạnh liên tiếp có một đỉnh chung, được sắp đơn điệu theo số thứ tự.