Note này được mình viết trong lúc đọc sách Concrete Mathematics, phần 1.3. Khi đọc sách Toán, mình thấy không nên chỉ đọc sơ qua mà nên bắt tay vào làm cùng theo chỉ dẫn của sách, khi đó thì mình sẽ nhớ và nắm kĩ ý tưởng giải bài hơn. Ngoài ra, mình viết note này để phục vụ bản thân là chính: một số phần mình thấy dễ hiểu thì mình bỏ qua, phần khó hiểu mình note kĩ hơn, và vì thế một số bạn sẽ thấy note hữu ích và một số bạn sẽ không học được gì từ mấy note này.

Cho ~n~ người đứng thành một vòng tròn, mỗi người được đánh số từ 1 đến ~n~. Bắt đầu từ vị trí số 1, mỗi người sẽ đếm lần lượt 1, 2, ..., ~k~, người đếm ~k~ sẽ bị loại khỏi vòng tròn, và mọi người tiếp tục đếm lại từ ~1~ cho đến khi chỉ còn lại một người. Hỏi người đánh số nào là người ở lại vòng tròn cuối cùng.

Trong khuôn khổ bài viết này, ta nghiên cứu trường hợp ~k = 2~.

Gọi ~J(n)~ là số của người ở lại vòng tròn cuối cùng, ta sẽ thử tính ~J(n)~ với một số giá trị nhỏ của ~n~:

• ~J(1) = 1~
• ~J(2) = 1~
• ~J(3) = 3~ (thứ tự loại ~2, 1~)
• ~J(4) = 1~ (thứ tự loại ~2, 4, 3~)
• ~J(5) = 3~ (thứ tự loại ~2, 4, 1, 3~)
• ~J(6) = 5~ (thứ tự loại ~2, 4, 6, 1, 3~)

Qua những giá trị ban đầu, ta thấy ~J(n)~ là một số lẻ, điều này là do ở lần đi qua vòng tròn đầu tiên thì ta đã loại hết tất cả số chẵn. Ngoài ra, tùy vào tính chẵn lẻ của ~n~ mà ~1~ bị loại ngay sau lần duyệt đầu tiên, hoặc an toàn khá lâu, vì vậy ta nghĩ đến việc xét tính chẵn lẻ của ~n~.

Ta xét trường hợp có ~2n~ người. Sau một lần đi qua vòng tròn, vòng tròn trở thành ~1, 3, 5, ..., 2n-3, 2n-1~ (~n~ người). Ta thấy vòng tròn này giống hệt vòng tròn ~1, 2, 3, ..., n~, ngoại trừ việc số của người ~x~ trở thành ~2x-1~. Do đó, ~J(2n) = 2J(n) - 1~.

Xét trường hợp có ~2n+1~ người. Ta thấy sau khi người 1 đếm "2" thì vòng tròn còn ~n~ người ~3, 5, ..., 2n+1~. Vòng tròn này giống hệt vòng tròn ~n~ người của trò chơi ban đầu, ngoại trừ việc số của người ~x~ trở thành ~2x+1~. Do đó ~J(2n+1) = 2J(n)+1~.

Vậy ta có công thức truy hồi:

• ~J(1) = 1~
• ~J(2n) = 2J(n) - 1~
• ~J(2n+1) = 2J(n) + 1~

Liệu có công thức tổng quát cho công thức truy hồi này không?

Sử dụng công thức truy hồi này, ta sẽ tính được kết quả cho một số ~n~ lớn hơn một chút. Ta thấy được quy luật sau (các giá trị ~J(n)~ dưới đây được viết từ ~J(1)~ theo thứ tự từ trái qua phải, từ trên xuống dưới để thể hiện quy luật)

• ~1~ (~n=1~)
• ~1,3~ (~n=2..3~)
• ~1,3,5,7~ (~n=4..7~)
• ~1,3,5,7,11,13,15~ (~n=8..15~)

Ta thấy có một "chu kì" mới bắt đầu khi ~n = 2^m~, và các số trong "chu kì" có dạng ~1, 3, 5, 7, ...~. Ta có thể biểu diễn điều này dưới dạng toán học như sau

~J(2^m + l) = 2l+1~ với ~m \geq 0~ và ~0 \leq l < 2^m~ (cách kí hiệu này khá giống kí hiệu ~q, r~ trong định nghĩa phép chia hai số tự nhiên)

Ta sẽ chứng minh công thức tổng quát này bằng quy nạp theo ~m~

Nếu ~m = 0~, khi đó do ~0 \leq l < 2^m = 1~ nên ~l = 0~. ~J(2^m + l) = J(1 + 0) = J(1) = 1 = 2(0) + 1 = 2l+1~, nên trường hợp khởi đầu đúng.

Nếu ~m \geq 1~, ta có hai trường hợp

• Nếu ~l~ chẵn, ~J(2^m + l) = 2J(\frac{2^m+l}{2}) - 1 = 2J(2^{m-1} + \frac{l}{2}) - 1 = 2(2(\frac{l}{2}) + 1) + 1 = 2l + 1~

• Nếu ~l~ lẻ, ~J(2^m + l) = 2J(\frac{2^m+l-1}{2}) + 1 = 2(2(\frac{l-1}{2}) + 1) + 1 = 2l+1~

Từ hai trường hợp trên, ta thấy trường hợp quy nạp cũng đúng.

Do đó theo nguyên lí quy nạp thì công thức đúng.

Bây giờ ta sẽ thử mở rộng bài toán để có thể giải được các bài toán khác.

Ta thấy công thức xuất hiện số ~2^m~, và vì thế ta nghĩ đến việc viết lại công thức dưới dạng hệ nhị phân xem có gì đặc biệt không.

Giả sử ~n = (b_mb_{m-1}...b_1b_0)_2 = b_m \cdot 2^m + b_{m-1} \cdot 2^{m-1} + ... + b_1 \cdot 2^1 + b_0 \cdot 2^0~.

Khi ~n = 2^m + l~ thì

~n = (1b_{m-1}...b_1b_0)_2~

~l = (0b_{m-1}...b_1b_0)_2~

~2l = (b_{m-1}...b_1b_00)_2~ (dịch bit sang trái)

~2l + 1 = (b_{m-1}...b_1b_01)_2~

Nói cách khác, ~J((1b_{m-1}...b_1b_0)_2) = (b_{m-1}...b_1b_01)_2~, tức ta chỉ cần cyclic left shift số ~n~ là tính được ~J(n)~

Một cách mở rộng bài toán khác là giả sử ta không may mắn gặp phải một công thức truy hồi có dạng sau:

~f(1) = \alpha~

~f(2n) = 2f(n) + \beta~

~f(2n+1) = 2f(n) + \gamma~

thì liệu ta có giải được không?

Đầu tiên, ta lại thử với ~n~ nhỏ để tìm quy luật:

• ~f(1) = 1\alpha + 0\beta + 0\gamma~
• ~f(2) = 2\alpha + 1\beta + 0\gamma~
• ~f(3) = 2\alpha + 0\beta + 1\gamma~
• ~f(4) = 4\alpha + 3\beta + 0\gamma~
• ~f(5) = 4\alpha + 2\beta + 1\gamma~
• ~f(6) = 4\alpha + 1\beta + 2\gamma~
• ~f(7) = 4\alpha + 0\beta + 3\gamma~

Ta thấy xuất hiện các chu kì giống như trong dãy Josephus.

Đặt ~f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma~. Khi viết ~n = 2^m + l~, dễ thấy

• ~A(n) = 2^m~
• ~B(n) = 2^m - l - 1~
• ~C(n) = l~

Nếu giả sử các hàm ~A(n), B(n), C(n)~ không dễ thấy như trên thì liệu ta có thể dùng kĩ thuật nào khác để mò ra các hàm nào không. Ta có thể sử dụng repertoire method, với tư tưởng chính là:

• Chọn các hàm ~f(n)~ đặc biệt, rồi lấy ~\alpha, \beta, \gamma~ ứng với các hàm đó.
• Các ~\alpha, \beta, \gamma, f(n)~ sẽ tạo ra hệ phương trình ẩn ~A(n), B(n), C(n)~
• Giải hệ phương trình.

Ở ví dụ này, ta dễ thấy ~\boxed{A(n) = 2^m}~ với ~n = 2^m + l~, nhưng có thể ta không thấy được ~B(n), C(n)~. Ta sẽ ứng dụng repertoire method để giải.

Đầu tiên, a muốn tìm ~\alpha, \beta, \gamma~ để ~f(n) = 1~. Thay vào

~f(1) = \alpha~

~f(2n) = 2f(n) + \beta~

~f(2n+1) = 2f(n) + \gamma~

Ta có: ~\alpha = 1~, ~1 = 2 + \beta \Rightarrow \beta = -1~, ~1 = 2 + \gamma \Rightarrow \gamma = -1~. Thay các giá trị ~\alpha, \beta, \gamma~, và ~f(n) = 1~ vào ~f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma~, ta được: ~\boxed{A(n) - B(n) - C(n) = 1}~

Lấy ~f(n) = n~. Thay vào hệ thức truy hồi, ta có:

~\alpha = 1~

~2n = 2n + \beta \Rightarrow \beta = 0~

~2n + 1 = 2n + \gamma \Rightarrow \gamma = 1~

Thay các giá trị này cùng với ~f(n) = n~ vào ~f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma~, ta được ~\boxed{A(n) + C(n) = n}~

Giải hệ ~\begin{cases} A(n) = 2^m \\ A(n) - B(n) - C(n) = 1 \\ A(n) + C(n) = n \end{cases}~, ta ra được ~A(n), B(n), C(n)~ như quan sát ở trên.

Số ~2^m~ lại xuất hiện trong ~A(n)~ và ~B(n)~. Điều này khiến ta nghĩ tới việc giải công thức truy hồi dạng tổng quát dưới dạng hệ nhị phân.

Để thuận tiện, ta viết lại

~f(1) = \alpha~

~f(2n) = 2f(n) + \beta~

~f(2n+1) = 2f(n) + \gamma~

thành

~f(1) = \alpha~

~f(2n + j) = 2f(n) + \beta_j~ với ~j \in \{0,1\}~ (~\beta_0 = \beta, \beta_1 = \gamma~)

Khi đó

~f((b_mb_{m-1}...b_1b_0)_2) = 2f((b_mb_{m-1}...b_1)_2) + \beta_{b_0}~

~f((b_mb_{m-1}...b_1b_0)_2) = 4f((b_mb_{m-1}...b_2)_2) + 2\beta_{b_1} + \beta_{b_0}~

~f((b_mb_{m-1}...b_1b_0)_2) = 8f((b_mb_{m-1}...b_3)_2) + 2^2\beta_{b_2} + 2^1\beta_{b_1} + \beta_{b_0}~

...

~f((b_mb_{m-1}...b_1b_0)_2) = 2^mf((b_m)_2) + 2^{m-1}\beta_{b_{m-1}} + ... + 2^1\beta_{b_1} + \beta_{b_0}~

~f((b_mb_{m-1}...b_1b_0)_2) = 2^m\alpha + 2^{m-1}\beta_{b_{m-1}} + ... + 2^1\beta_{b_1} + \beta_{b_0}~

Nếu ta cho phép các chữ số trong kí hiệu hệ nhị phân được lấy giá trị bất kì, ta có thể viết

~f((b_mb_{m-1}...b_1b_0)_2) = (\alpha\beta_{b_{m-1}}...\beta_{b_1}\beta_{b_0})_2~

(cho ~\alpha~ làm số đầu tiên trong đáp án, với ~m-1~ số còn lại, đổi chữ số ~i~ thành ~\beta_i~)

Ví dụ, với bài toán Josephus ban đầu (~\alpha = 1, \beta_0 = -1, \beta_1 = 1~), để tính ~J(100)~, ta có thể làm như sau:

~100 = (1100100)_2~

Cho ~\alpha = 1~ ở đầu, trong ~m-1~ số còn lại, thay số 0 bằng -1 và thay số 1 bằng 1, ta có:

~J(100) = ((1)(1)(-1)(-1)(1)(-1)(-1))_2 = 64 + 32 - 16 - 8 + 4 - 2 - 1 = 73~

Ta thấy công thức truy hồi trên còn số 2 ta chưa tổng quát. Giả sử ta có hệ thức truy hồi sau

~f(j) = \alpha_j~ với ~1 \leq j < d~

~f(dn + j) = cf(n) + \beta_j~ với ~0 \leq j < d~ và ~n \geq 1~

thì bằng cách viết ~n~ dưới dạng hệ cơ số ~d~ và viết đáp án dưới dạng hệ cơ số ~c~, ta cũng ra được kết quả

~f((b_mb_{m-1}...b_1b_0)_d) = (\alpha_{b_m}\beta_{b_{m-1}}...\beta_{b_1}\beta_{b_0})_c~