Câu hỏi 33
Một câu lạc bộ xã hội có $n$ thành viên. Các thành viên có số thứ tự lần lượt là $1, 2, \ldots, n$. Thỉnh thoảng các thành viên gửi quà cho các thành viên khác, kể cả những món đồ mà họ đã nhận được làm quà từ các thành viên khác. Để tránh tình huống khó xử là một thành viên có thể nhận một món quà mà chính mình đã gửi cho người khác, câu lạc bộ thêm quy định sau vào điều lệ tại một đại hội thường niên:
"Thành viên có số thứ tự $a$ được phép gửi quà cho thành viên có số thứ tự $b$ khi và chỉ khi $a(b-1)$ là bội của $n$."
Chứng minh rằng, nếu mỗi thành viên tuân theo quy định này, thì sẽ không ai nhận được từ một thành viên khác một món quà mà mình đã gửi cho những người khác.
Cách phát biểu khác: Cho $G$ là một đồ thị có hướng với $n$ đỉnh $v_{1}, v_{2}, \ldots, v_{n}$, sao cho có một cạnh đi từ $v_{a}$ tới $v_{b}$ khi và chỉ khi $a$ và $b$ phân biệt và $a(b-1)$ là bội của $n$. Chứng minh rằng đồ thị này không chứa chu trình có hướng.
"Thành viên có số thứ tự $a$ được phép gửi quà cho thành viên có số thứ tự $b$ khi và chỉ khi $a(b-1)$ là bội của $n$."
Chứng minh rằng, nếu mỗi thành viên tuân theo quy định này, thì sẽ không ai nhận được từ một thành viên khác một món quà mà mình đã gửi cho những người khác.
Cách phát biểu khác: Cho $G$ là một đồ thị có hướng với $n$ đỉnh $v_{1}, v_{2}, \ldots, v_{n}$, sao cho có một cạnh đi từ $v_{a}$ tới $v_{b}$ khi và chỉ khi $a$ và $b$ phân biệt và $a(b-1)$ là bội của $n$. Chứng minh rằng đồ thị này không chứa chu trình có hướng.