Câu hỏi 19
Trong một cuộc thi toán, một số thí sinh là bạn của nhau; tình bạn luôn tương hỗ: nếu $A$ là bạn của $B$ thì $B$ cũng là bạn của $A$. Ta nói $n\ge3$ thí sinh khác nhau $A_1,A_2,\ldots,A_n$ tạo thành một chu trình thân thiện yếu nếu $A_i$ không là bạn của $A_{i+1}$ với $1\le i\le n$ (quy ước $A_{n+1}=A_1$), và không có cặp không là bạn nào khác giữa các thành viên của chu trình.
Giả sử: với mọi thí sinh $C$ và mọi chu trình thân thiện yếu $\mathcal S$ không chứa $C$, có nhiều nhất một thành viên $D$ của $\mathcal S$ không là bạn của $C$.
Chứng minh có thể xếp tất cả thí sinh vào ba phòng sao cho hai người bất kỳ trong cùng phòng đều là bạn.
Bài toán (bản tiếng Romania được lặp lại trong nguồn):
Trong một cuộc thi toán, một số học sinh tham gia là bạn; tình bạn luôn tương hỗ, nghĩa là nếu $A$ là bạn của $B$ thì $B$ cũng là bạn của $A$. Ta nói $n$ học sinh khác nhau ($n\ge3$) $A_1,A_2,\ldots,A_n$ tạo thành một chu trình thân thiện yếu nếu $A_i$ không là bạn của $A_{i+1}$ với $1\le i\le n$ (quy ước $A_{n+1}=A_1$), và trong chu trình không có cặp không là bạn nào khác.
Giả sử tính chất sau được thỏa mãn: với mỗi học sinh $C$, mỗi chu trình thân thiện yếu $\mathcal S$ không chứa $C$ có nhiều nhất một học sinh không là bạn của $C$.
Chứng minh tất cả học sinh có thể được chia vào ba phòng sao cho hai học sinh bất kỳ trong cùng phòng là bạn.
Giả sử: với mọi thí sinh $C$ và mọi chu trình thân thiện yếu $\mathcal S$ không chứa $C$, có nhiều nhất một thành viên $D$ của $\mathcal S$ không là bạn của $C$.
Chứng minh có thể xếp tất cả thí sinh vào ba phòng sao cho hai người bất kỳ trong cùng phòng đều là bạn.
Bài toán (bản tiếng Romania được lặp lại trong nguồn):
Trong một cuộc thi toán, một số học sinh tham gia là bạn; tình bạn luôn tương hỗ, nghĩa là nếu $A$ là bạn của $B$ thì $B$ cũng là bạn của $A$. Ta nói $n$ học sinh khác nhau ($n\ge3$) $A_1,A_2,\ldots,A_n$ tạo thành một chu trình thân thiện yếu nếu $A_i$ không là bạn của $A_{i+1}$ với $1\le i\le n$ (quy ước $A_{n+1}=A_1$), và trong chu trình không có cặp không là bạn nào khác.
Giả sử tính chất sau được thỏa mãn: với mỗi học sinh $C$, mỗi chu trình thân thiện yếu $\mathcal S$ không chứa $C$ có nhiều nhất một học sinh không là bạn của $C$.
Chứng minh tất cả học sinh có thể được chia vào ba phòng sao cho hai học sinh bất kỳ trong cùng phòng là bạn.