Câu hỏi 24
Một câu lạc bộ có $n$ thành viên, mang các mã số $1,2, \ldots, n$. Thỉnh thoảng, họ gửi quà cho thành viên khác, kể cả quà đã nhận từ người khác. Để tránh việc một người nhận lại món quà mình từng gửi đi, câu lạc bộ đặt quy tắc:
“Thành viên mã số $a$ được gửi quà cho thành viên mã số $b$ khi và chỉ khi $a(b-1)$ là bội của $n$.”
Chứng minh nếu mọi thành viên tuân thủ, không ai nhận lại từ người khác món quà mình từng gửi đi.
Phát biểu tương đương: Cho đồ thị có hướng $G$ với $n$ đỉnh $v_{1}, v_{2}, \ldots, v_{n}$, có cạnh từ $v_{a}$ đến $v_{b}$ khi và chỉ khi $a$, $b$ khác nhau và $a(b-1)$ là bội của $n$. Chứng minh đồ thị không chứa chu trình có hướng.
“Thành viên mã số $a$ được gửi quà cho thành viên mã số $b$ khi và chỉ khi $a(b-1)$ là bội của $n$.”
Chứng minh nếu mọi thành viên tuân thủ, không ai nhận lại từ người khác món quà mình từng gửi đi.
Phát biểu tương đương: Cho đồ thị có hướng $G$ với $n$ đỉnh $v_{1}, v_{2}, \ldots, v_{n}$, có cạnh từ $v_{a}$ đến $v_{b}$ khi và chỉ khi $a$, $b$ khác nhau và $a(b-1)$ là bội của $n$. Chứng minh đồ thị không chứa chu trình có hướng.