Câu hỏi 91
Trong một buổi tiệc có $n$ bạn nam $a_1,\ldots,a_n$ và $n$ bạn nữ $b_1,\ldots,b_n$. Không có hai bạn nam bắt tay nhau, không có hai bạn nữ bắt tay nhau, và với mỗi $i\in\{1,\ldots,n\}$, $a_i$ không bắt tay $b_i$. Ta muốn chia cả $2n$ người thành các nhóm thỏa:
1. Mỗi nhóm có số bạn nam bằng số bạn nữ.
2. Trong mỗi nhóm không có hai người đã bắt tay nhau.
Gọi $m$ là số cặp $(a_i,b_j)$ đã bắt tay. Chứng minh có thể chia sao cho số nhóm không vượt quá $2$ hoặc $2m/n+1$.
1. Mỗi nhóm có số bạn nam bằng số bạn nữ.
2. Trong mỗi nhóm không có hai người đã bắt tay nhau.
Gọi $m$ là số cặp $(a_i,b_j)$ đã bắt tay. Chứng minh có thể chia sao cho số nhóm không vượt quá $2$ hoặc $2m/n+1$.