Bài toán Josephus

Bài toán Josephus, hay hoán vị Josephus, là một câu hỏi toán lý thuyết trong khoa học máy tính và toán học.

Có $n$ người đang đứng thành một vòng tròn. Và, bắt đầu từ vị trí $s$, bài toán sẽ đếm từ người đó theo một hướng nhất định. Sau khi có $p$ người được bỏ qua, người thứ $p+1$ sẽ bị xử tử. Quy luật sẽ lặp đi lặp lại với số người còn lại trong vòng tròn đó, bắt đầu với người tiếp theo, theo cùng một chiều quay, và bỏ qua cùng số người p cho đến khi nào chỉ còn một người sống sót.

Điều cốt lõi của bài toán, chính là tìm ra vị trí trong vòng tròn để có thể là người sống sót.

Lịch sử

Bài toán được đặt tên theo Flavius Josephus, một sử gia người Do Thái sinh sống vào thế kỷ thứ nhất. Theo bản tường trình của Josephus về cuộc bao vây Yodfat, ông và 40 người lính bị những người lính La mã vây trong một hang động. Họ thà tự tử còn hơn là bị bắt giữ và giải quyết cách tự tử bằng cách rút thăm. Josephus tuyên bố rằng bằng may mắn hoặc có thể là do bàn tay của Thiên Chúa, ông và một người khác còn sống cho đến cuối cùng và đầu hàng người La Mã thay vì tự tử. Đây là câu chuyện được đưa ra trong Sách 3, chương 8, phần 7 của Chiến tranh Do Thái của Josephus (viết về bản thân mình với ngôi thứ ba):bài toán này được sử dụng với mọi cấp độ

Liên kết ngoài

• Armin Shams-Baragh Formulating The Extended Josephus Problem
• Josephus Flavius game (Java Applet) at cut-the-knot allowing selection of every n^th out of 50 (maximum).
• Josephus Problem at the MathWorld encyclopedia