Tổng quan
Câu đố được đặt tên theo nhà sử học Flavius Josephus, người — theo lời kể của chính ông — đã sống sót qua một cuộc vây thành của người La Mã bằng cách đứng đúng vị trí trong một vòng tròn tự sát.
Cách giải Bài Toán Josephus từng bước
- Hãy mô phỏng một lần để thấy hình dạng của nó: vòng quét đầu tiên loại mọi chỗ chẵn.
- Sau vòng quét đó, bạn gặp lại đúng bài toán với một nửa số người, nên đáp án có tính đệ quy.
- Viết n = 2^m + L với 0 ≤ L < 2^m. Người sống sót là 2L + 1: với n = 10 = 8 + 2 thì đó là chỗ 5.
Mấu chốt
Trong hệ nhị phân, đáp án là một phép xoay một bit: viết n ở dạng nhị phân rồi chuyển bit 1 dẫn đầu ra cuối. 10 = 1010₂ thành 0101₂ = 5. Lũy thừa của hai là các điểm bất động — nếu n = 2^m thì người sống sót luôn là chỗ 1.
Biến thể & liên hệ
- Với bước nhảy k tổng quát, hệ thức là J(n) = (J(n−1) + k) mod n, tính được trong O(n) mà không có dạng đóng.
- Cùng cấu trúc loại trừ đó xuất hiện trong lập lịch vòng tròn và trong bộ đệm vòng.
Câu hỏi thường gặp
Đáp án có đổi nếu bắt đầu đếm ở chỗ khác?
Chỉ đổi theo một phép xoay: chỗ của người sống sót dịch đi đúng khoảng lệch đó, vì vòng tròn không có điểm nào đặc biệt ngoài chỗ bạn bắt đầu đếm.