41 Người Và Vị Trí 19: Từ Câu Chuyện Josephus Đến Thuật Toán Máy Tính

1. Câu chuyện: 41 người trong vòng tròn

Có 41 người bị bắt và bị xếp thành một vòng tròn, đánh số từ 1 đến 41.

Họ lần lượt đếm từ người số 1. Cứ hai người thì loại một người:

Người số 1 sống.

Người số 2 bị loại.

Người số 3 sống.

Người số 4 bị loại.

Cứ tiếp tục như vậy.

Khi đi hết một vòng, việc đếm tiếp tục từ những người còn sống. Quá trình lặp lại cho đến khi chỉ còn một người.

Câu hỏi: người sống sót cuối cùng đứng ở vị trí nào?

Đáp án là:

\boxed{19}

Bài toán này ngày nay được biết đến với tên gọi bài toán Josephus (Josephus problem).

2. Bối cảnh câu chuyện

Tên gọi Josephus xuất phát từ Flavius Josephus, một sử gia người Do Thái sống vào thế kỷ I.

Năm 67, trong cuộc chiến giữa người Do Thái và Đế quốc La Mã, Josephus cùng một nhóm chiến binh bị quân La Mã vây tại thành Jotapata.

Khi nhận thấy không còn khả năng chống cự, nhóm người quyết định tự sát thay vì đầu hàng.

Theo lời Josephus kể lại, họ thống nhất một quy tắc để lần lượt giết nhau.

Josephus không muốn chết. Ông cùng một người khác tìm cách sắp xếp vị trí để cả hai không bị chọn cho đến cuối cùng, sau đó đầu hàng quân La Mã.

Câu chuyện này trở thành nguồn gốc của một bài toán toán học nổi tiếng:

Cho $n$ người đứng thành vòng tròn, lần lượt loại mỗi người thứ $k$ . Người sống sót cuối cùng ở vị trí nào?

Trường hợp kinh điển với $n=41$ , $k=2$ , cho kết quả:

\boxed{19}

3. Các công trình toán học nói gì?

3.1. Mô phỏng trực tiếp

Với 41 người:

1,2,3,4,\ldots,41

Lần đầu tiên loại các vị trí chẵn:

2,4,6,8,\ldots,40

Còn lại:

1,3,5,7,\ldots,41

Sau đó tiếp tục đếm trên vòng tròn mới.

Nếu thực hiện toàn bộ quá trình bằng tay, cuối cùng người ở vị trí 19 sẽ là người sống sót.

Cách này dễ hiểu nhưng chỉ giải quyết trường hợp $n=41$ .

Toán học đặt câu hỏi tổng quát hơn:

Nếu có $n$ người thì sao?

3.2. Công thức Josephus

Gọi $J(n,k)$ là vị trí sống sót khi có $n$ người và cứ mỗi người thứ $k$ bị loại.

Nếu đánh số từ 0, ta có:

J(1,k)=0

và công thức truy hồi:

J(n,k)=\big(J(n-1,k)+k\big)\bmod n

Đây là công thức tổng quát của bài toán Josephus.

Với trường hợp mỗi lần loại người thứ hai:

k=2

nên:

J(n,2)=\big(J(n-1,2)+2\big)\bmod n

Áp dụng đến $n=41$ :

J(41,2)=18

Do đang đánh số từ 0, vị trí thực tế là:

18+1=19

Vậy:

\boxed{J(41,2)=19}

4. Điều đặc biệt của trường hợp $k=2$

Trường hợp $k=2$ có một cấu trúc toán học rất đẹp.

Tìm lũy thừa của 2 lớn nhất không vượt quá $n$ :

2^m\leq n<2^{m+1}

Đặt:

L=n-2^m

Khi đó vị trí sống sót được tính bằng:

\boxed{J(n,2)=2L+1}

Với:

n=41

ta có:

2^5=32

và:

41-32=9

Do đó:

J(41,2)=2(9)+1=19

Toàn bộ bài toán 41 người được rút gọn thành:

41\rightarrow32\rightarrow9\rightarrow19

Không cần mô phỏng 40 lần loại người.

5. Mối quan hệ với lũy thừa của 2

Công thức trên cho thấy một điều thú vị.

Khi:

n=32

ta có:

J(32,2)=1

Khi tăng số người lên:

33\rightarrow3

34\rightarrow5

35\rightarrow7

36\rightarrow9

...

40\rightarrow17

41\rightarrow19

...

63\rightarrow63

Đến:

64=2^6

thì:

J(64,2)=1

Nói cách khác, trong khoảng:

32\leq n<64

vị trí sống sót chạy qua toàn bộ các số lẻ:

1,3,5,7,\ldots,63

Khi đạt đến một lũy thừa mới của 2, chu kỳ quay trở lại vị trí 1.

Đây là lý do cấu trúc nhị phân xuất hiện rất tự nhiên trong bài toán Josephus.

6. Từ toán học đến Computer Science

Bài toán Josephus không chỉ là một bài toán đố.

Nó là một ví dụ kinh điển để nghiên cứu cách máy tính biểu diễn và xử lý một cấu trúc dữ liệu có tính tuần hoàn.

6.1. Circular Linked List

Có thể biểu diễn 41 người bằng một circular linked list:

1\rightarrow2\rightarrow3\rightarrow4\rightarrow5\rightarrow\cdots\rightarrow41\rightarrow1

Mỗi người trỏ tới người tiếp theo.

Khi loại người số 2, liên kết:

1\rightarrow2\rightarrow3

được thay bằng:

1\rightarrow3

Chỉ cần thay đổi liên kết, vòng tròn vẫn được duy trì.

Đây là một ví dụ trực quan cho cấu trúc circular linked list.

6.2. Array và List

Nếu dùng array hoặc dynamic array, việc loại một phần tử ở giữa có thể khiến các phần tử phía sau phải dịch chuyển.

Ví dụ:

[

[1,2,3,4,5]

]

Xóa phần tử 2:

[

[1,3,4,5]

]

Các phần tử phía sau vị trí bị xóa phải được dịch chuyển để lấp khoảng trống.

Với linked list, thao tác xóa có thể chỉ cần thay đổi liên kết giữa các node.

Josephus problem vì thế trở thành một ví dụ trực quan để so sánh:

Array

Linked List

Circular Linked List

Index

Modulo

Recursion

Time Complexity

7. Josephus problem và thuật toán

Có thể giải bài toán bằng nhiều mức độ khác nhau.

Cách 1: Mô phỏng

Lưu toàn bộ danh sách người còn sống và lần lượt xóa phần tử.

Đây là cách gần với câu chuyện ban đầu nhất.

Cách 2: Circular Linked List

Duy trì một vòng liên kết và loại từng node.

Cấu trúc dữ liệu phản ánh trực tiếp cấu trúc của bài toán.

Cách 3: Công thức truy hồi

Sử dụng:

J(n,k)=\big(J(n-1,k)+k\big)\bmod n

Không cần xây dựng vòng tròn thực tế.

Cách 4: Công thức đóng

Với $k=2$ :

J(n,2)======2\left(n-2^{\lfloor\log_2 n\rfloor}\right)+1

Khi đó vị trí sống sót có thể được tính trực tiếp.

Với:

n=41

chỉ cần:

2^{\lfloor\log_2 41\rfloor}=32

41-32=9

2\times9+1=19

8. Ứng dụng trong Computer Science

8.1. Round-robin scheduling

Trong hệ thống round-robin scheduling, các process lần lượt được cấp thời gian xử lý:

P_1\rightarrow P_2\rightarrow P_3\rightarrow P_4\rightarrow P_1\rightarrow\cdots

Sau khi một process được xử lý, hệ thống chuyển sang process tiếp theo.

Đây là cùng một kiểu tư duy với Josephus:

duyệt tuần hoàn, duy trì vị trí hiện tại và chuyển sang phần tử tiếp theo.

8.2. Circular Buffer

Circular buffer sử dụng vùng nhớ theo dạng vòng:

0\rightarrow1\rightarrow2\rightarrow3\rightarrow4\rightarrow0

Khi đạt đến cuối buffer, con trỏ quay lại đầu.

Phép modulo thường được sử dụng:

i=(i+1)\bmod n

Đây chính là loại phép toán xuất hiện liên tục trong Josephus problem.

8.3. Ring Buffer và hệ thống xử lý dữ liệu

Ring buffer được sử dụng để quản lý các luồng dữ liệu liên tục mà không cần liên tục dịch chuyển toàn bộ dữ liệu trong bộ nhớ.

Tư tưởng cốt lõi là:

có một vùng dữ liệu hữu hạn;

có vị trí hiện tại;

khi đi đến cuối thì quay lại đầu;

thao tác được thực hiện theo chu kỳ.

Đây chính là tư duy cấu trúc vòng được thể hiện rất rõ trong bài toán Josephus.

8.4. Token Passing

Trong một hệ thống gồm nhiều node:

A\rightarrow B\rightarrow C\rightarrow D\rightarrow A

một token có thể lần lượt được truyền qua từng node.

Mỗi node nhận token, xử lý công việc rồi chuyển token sang node kế tiếp.

Mô hình này có cấu trúc tuần hoàn tương tự vòng tròn của Josephus.

9. Từ một câu chuyện đến một thuật toán

Điều thú vị nhất của Josephus problem nằm ở hành trình của nó.

Một câu chuyện cổ về 41 người tạo ra một câu hỏi:

Ai sẽ là người cuối cùng sống sót?

Từ đó xuất hiện một bài toán mô phỏng.

Từ bài toán mô phỏng xuất hiện công thức truy hồi.

Từ công thức truy hồi xuất hiện một công thức đóng đặc biệt cho trường hợp

k=2

Từ cấu trúc của công thức lại xuất hiện mối quan hệ với lũy thừa của 2 và biểu diễn nhị phân.

Cuối cùng, cùng một tư duy được gặp lại trong Computer Science:

circular linked list;

modulo;

recursion;

scheduling;

circular buffer;

ring buffer;

token passing;

các thuật toán xử lý cấu trúc tuần hoàn.

Một câu chuyện về 41 người vì thế trở thành một bài học nhỏ về cách toán học và Computer Science nhìn cùng một vấn đề từ những góc độ khác nhau.

Và đáp án của câu hỏi ban đầu vẫn là:

\boxed{19}

1. Câu chuyện: 41 người trong vòng tròn

Bài toán này ngày nay được biết đến với tên gọi bài toán Josephus (Josephus problem).

2. Bối cảnh câu chuyện

Trường hợp kinh điển với n=41, k=2, cho kết quả:

3. Các công trình toán học nói gì?

3.1. Mô phỏng trực tiếp

3.2. Công thức Josephus

Gọi J(n,k) là vị trí sống sót khi có n người và cứ mỗi người thứ k bị loại.

Nếu đánh số từ 0, ta có:

và công thức truy hồi:

Đây là công thức tổng quát của bài toán Josephus.

Với trường hợp mỗi lần loại người thứ hai:

nên:

Áp dụng đến n=41:

Do đang đánh số từ 0, vị trí thực tế là:

Vậy:

4. Điều đặc biệt của trường hợp k=2

Trường hợp k=2 có một cấu trúc toán học rất đẹp.

Tìm lũy thừa của 2 lớn nhất không vượt quá n:

Đặt:

Khi đó vị trí sống sót được tính bằng:

Với:

ta có:

và:

Do đó:

Toàn bộ bài toán 41 người được rút gọn thành:

Không cần mô phỏng 40 lần loại người.

5. Mối quan hệ với lũy thừa của 2

Đây là lý do cấu trúc nhị phân xuất hiện rất tự nhiên trong bài toán Josephus.

6. Từ toán học đến Computer Science

Nó là một ví dụ kinh điển để nghiên cứu cách máy tính biểu diễn và xử lý một cấu trúc dữ liệu có tính tuần hoàn.

6.1. Circular Linked List

Đây là một ví dụ trực quan cho cấu trúc circular linked list.

6.2. Array và List

7. Josephus problem và thuật toán

Có thể giải bài toán bằng nhiều mức độ khác nhau.

Cách 1: Mô phỏng

Lưu toàn bộ danh sách người còn sống và lần lượt xóa phần tử.

Đây là cách gần với câu chuyện ban đầu nhất.

Cách 2: Circular Linked List

Duy trì một vòng liên kết và loại từng node.

Cấu trúc dữ liệu phản ánh trực tiếp cấu trúc của bài toán.

Cách 3: Công thức truy hồi

Sử dụng:

Không cần xây dựng vòng tròn thực tế.

Cách 4: Công thức đóng

Với k=2:

Khi đó vị trí sống sót có thể được tính trực tiếp.

Với:

chỉ cần:

8. Ứng dụng trong Computer Science

8.1. Round-robin scheduling

8.2. Circular Buffer

Circular buffer sử dụng vùng nhớ theo dạng vòng:

Khi đạt đến cuối buffer, con trỏ quay lại đầu.

Phép modulo thường được sử dụng:

Đây chính là loại phép toán xuất hiện liên tục trong Josephus problem.

8.3. Ring Buffer và hệ thống xử lý dữ liệu

Đây chính là tư duy cấu trúc vòng được thể hiện rất rõ trong bài toán Josephus.

8.4. Token Passing

Trong một hệ thống gồm nhiều node:

một token có thể lần lượt được truyền qua từng node.

Mỗi node nhận token, xử lý công việc rồi chuyển token sang node kế tiếp.

Mô hình này có cấu trúc tuần hoàn tương tự vòng tròn của Josephus.

9. Từ một câu chuyện đến một thuật toán

Trường hợp kinh điển với $n=41$ , $k=2$ , cho kết quả:

Gọi $J(n,k)$ là vị trí sống sót khi có $n$ người và cứ mỗi người thứ $k$ bị loại.

Áp dụng đến $n=41$ :

4. Điều đặc biệt của trường hợp $k=2$

Trường hợp $k=2$ có một cấu trúc toán học rất đẹp.

Tìm lũy thừa của 2 lớn nhất không vượt quá $n$ :

Với $k=2$ :