Câu hỏi 7
$n$ cầu thủ của một đội khúc côn cầu tập trung để bầu đội trưởng. Ban đầu, họ đứng thành một vòng tròn, và mỗi người bỏ phiếu cho người đứng bên trái mình.
Các cầu thủ sẽ cập nhật phiếu bầu của mình qua một loạt các vòng. Trong một vòng, mỗi cầu thủ $a$ lần lượt cập nhật phiếu bầu của mình theo quy tắc sau: Tại thời điểm cập nhật, nếu $a$ đang bầu cho $b$, và $b$ đang bầu cho $c$, thì $a$ đổi phiếu bầu sang $c$. (Chú ý rằng $a$, $b$ và $c$ không nhất thiết phân biệt; nếu $b = c$ thì phiếu của $a$ không thay đổi trong lần cập nhật này.) Mỗi cầu thủ cập nhật phiếu đúng một lần trong mỗi vòng, theo một thứ tự do các cầu thủ quyết định (có thể khác nhau giữa các vòng).
Họ lặp lại quy trình cập nhật này trong $n$ vòng. Chứng minh rằng khi đó, tất cả $n$ cầu thủ đều bầu cho cùng một người.
Các cầu thủ sẽ cập nhật phiếu bầu của mình qua một loạt các vòng. Trong một vòng, mỗi cầu thủ $a$ lần lượt cập nhật phiếu bầu của mình theo quy tắc sau: Tại thời điểm cập nhật, nếu $a$ đang bầu cho $b$, và $b$ đang bầu cho $c$, thì $a$ đổi phiếu bầu sang $c$. (Chú ý rằng $a$, $b$ và $c$ không nhất thiết phân biệt; nếu $b = c$ thì phiếu của $a$ không thay đổi trong lần cập nhật này.) Mỗi cầu thủ cập nhật phiếu đúng một lần trong mỗi vòng, theo một thứ tự do các cầu thủ quyết định (có thể khác nhau giữa các vòng).
Họ lặp lại quy trình cập nhật này trong $n$ vòng. Chứng minh rằng khi đó, tất cả $n$ cầu thủ đều bầu cho cùng một người.