Câu hỏi 6
Một hội thảo có $n\ge10$ người tham dự. Biết rằng:
1. Mỗi người quen ít nhất $\left\lfloor\frac{n+2}{3}\right\rfloor$ người tham dự khác.
2. Hai người bất kỳ $A,B$ nếu không quen nhau thì quen gián tiếp: có $k\ge1$ người $A_1,\ldots,A_k$ sao cho $A$ quen $A_1$, $A_i$ quen $A_{i+1}$ với $i=1,\ldots,k-1$, và $A_k$ quen $B$.
3. Không thể xếp cả $n$ người thành một hàng ngang sao cho mọi cặp cạnh nhau đều quen nhau.
Chứng minh có thể chia thành hai nhóm: nhóm thứ nhất xếp được quanh một bàn tròn sao cho mọi cặp cạnh nhau đều quen nhau, nhóm thứ hai gồm những người đôi một không quen nhau. (Dấu ngoặc vuông trong nguồn chỉ phần nguyên.)
Nguồn được cung cấp không ghi điểm từng bài. Mỗi bài dùng 1 điểm biên tập để tương thích khi nhập; đây không phải thang điểm chính thức.
1. Mỗi người quen ít nhất $\left\lfloor\frac{n+2}{3}\right\rfloor$ người tham dự khác.
2. Hai người bất kỳ $A,B$ nếu không quen nhau thì quen gián tiếp: có $k\ge1$ người $A_1,\ldots,A_k$ sao cho $A$ quen $A_1$, $A_i$ quen $A_{i+1}$ với $i=1,\ldots,k-1$, và $A_k$ quen $B$.
3. Không thể xếp cả $n$ người thành một hàng ngang sao cho mọi cặp cạnh nhau đều quen nhau.
Chứng minh có thể chia thành hai nhóm: nhóm thứ nhất xếp được quanh một bàn tròn sao cho mọi cặp cạnh nhau đều quen nhau, nhóm thứ hai gồm những người đôi một không quen nhau. (Dấu ngoặc vuông trong nguồn chỉ phần nguyên.)
Nguồn được cung cấp không ghi điểm từng bài. Mỗi bài dùng 1 điểm biên tập để tương thích khi nhập; đây không phải thang điểm chính thức.