Thuật toán Selfridge–Conway chia một chiếc bánh cho ba người sao cho không ai ghen tị với ai, chỉ cần tối đa năm nhát cắt. Người thứ nhất cắt ba phần bằng nhau theo mình, người thứ hai gọt bớt miếng to nhất, ba người chọn theo thứ tự ngược, rồi phần vụn gọt ra được chia thêm một vòng nhỏ. Đây là lời giải hữu hạn đầu tiên cho bài toán chia không ghen tị ba người, tìm ra khoảng năm 1960.
Bài toán và lịch sử
Với hai người, "một người cắt, một người chọn" đã đủ. Với ba người, các phương pháp của nhóm Steinhaus thập niên 1940 chỉ bảo đảm mỗi người được ít nhất một phần ba, không bảo đảm khỏi ghen. Khoảng năm 1960, nhà lý thuyết số John Selfridge ở Mỹ tìm ra một quy trình không ghen tị cho ba người. John Horton Conway ở Cambridge, người sau này nổi tiếng với mô hình tự động tế bào mang tên Life, tìm ra cùng quy trình một cách độc lập. Cả hai đều không công bố thành bài báo; quy trình được truyền miệng trong giới toán, về sau được ghi lại trong các tài liệu về chia công bằng và được Brams và Taylor trình bày kỹ trong cuốn Fair Division (1996).
Điểm khác biệt quan trọng: các miếng cuối cùng không nhất thiết liền một khối. Mỗi người có thể nhận một miếng chính cộng một mẩu nhỏ từ phần vụn. Năm 2008, Stromquist chứng minh rằng nếu đòi miếng liền thì không có quy trình hữu hạn nào chia không ghen tị cho ba người, nên chấp nhận miếng rời là cái giá phải trả.
Các bước, viết gọn
Gọi ba người là P1, P2, P3.
Giai đoạn 1: chia phần chính
- P1 cắt bánh thành ba miếng mà P1 thấy bằng nhau.
- P2 xếp hạng ba miếng theo đánh giá của mình. Nếu hai miếng to nhất đã bằng nhau theo P2, không gọt gì, nhảy sang bước 3. Nếu không, P2 gọt miếng to nhất cho tới khi nó bằng miếng to thứ hai. Phần gọt ra gọi là phần vụn, để riêng.
- P3 chọn trước một trong ba miếng (một miếng đã bị gọt).
- P2 chọn tiếp. Luật đặc biệt: nếu P3 chưa lấy miếng bị gọt, P2 bắt buộc phải lấy miếng bị gọt.
- P1 lấy miếng còn lại. Miếng này chắc chắn chưa bị gọt.
Giai đoạn 2: chia phần vụn
- Trong hai người P2 và P3, ai đã nhận miếng bị gọt thì gọi là người giữ miếng gọt; người kia gọi là người cắt vụn.
- Người cắt vụn chia phần vụn thành ba mẩu mà mình thấy bằng nhau.
- Thứ tự chọn mẩu vụn: người giữ miếng gọt chọn trước, P1 chọn thứ hai, người cắt vụn lấy mẩu cuối.
Đếm nhát cắt: hai nhát của P1, một nhát gọt của P2, hai nhát chia vụn. Tổng cộng năm.
Vì sao không ai ghen: lập luận từng người
Sau giai đoạn 1
- P3 chọn trước nên lấy miếng mình thích nhất. Không ghen.
- P2: sau khi gọt, theo P2 có hai miếng cùng to nhất (miếng gọt và miếng to thứ hai). P3 lấy nhiều nhất một trong hai, nên còn ít nhất một miếng to nhất cho P2. Luật "bắt buộc lấy miếng gọt" không làm P2 thiệt, vì miếng gọt chính là một trong hai miếng to nhất theo P2. Không ghen.
- P1: cắt ba miếng bằng nhau theo mình, một miếng bị gọt nên nhỏ hơn, hai miếng nguyên bằng nhau. P1 nhận một miếng nguyên, nên không kém ai. Không ghen.
Sau giai đoạn 2
- Người giữ miếng gọt chọn mẩu vụn trước, nên không ghen trong phần vụn; cộng với giai đoạn 1 cũng không ghen, tổng lại không ghen.
- Người cắt vụn chia ba mẩu bằng nhau theo mình, nhận mẩu nào cũng như nhau. Không ghen.
- P1 chọn trước người cắt vụn, nên không ghen người cắt vụn. Còn với người giữ miếng gọt, P1 có một lợi thế mà các nhà nghiên cứu gọi là ưu thế không thể đảo ngược: theo P1, miếng gọt cộng toàn bộ phần vụn đúng bằng một phần ba, bằng miếng nguyên của P1. Vậy dù người giữ miếng gọt có được cả phần vụn, P1 cũng không ghen; huống hồ người đó chỉ được một mẩu.
Ý tưởng "ưu thế không thể đảo ngược" là chìa khoá của cả ngành. Thuật toán Brams–Taylor năm 1995 cho số người bất kỳ và thuật toán Aziz–Mackenzie năm 2016 đều xây trên việc tạo ra những ưu thế như vậy rồi tận dụng chúng.
Ví dụ tính tay trên một chiếc bánh cuộn
Một chiếc bánh cuộn dài 12 cm, ba đoạn hương vị: sô-cô-la từ 0 đến 4 cm, vani từ 4 đến 8 cm, dâu từ 8 đến 12 cm. Mỗi người chấm điểm trên mỗi xăng-ti-mét như sau:
| Người | Sô-cô-la (0–4) | Vani (4–8) | Dâu (8–12) | Cả bánh |
|---|---|---|---|---|
| An (P1) | 1 điểm/cm | 1 điểm/cm | 1 điểm/cm | 12 |
| Bình (P2) | 2 điểm/cm | 1 điểm/cm | 0,5 điểm/cm | 14 |
| Chi (P3) | 0,5 điểm/cm | 1 điểm/cm | 2 điểm/cm | 14 |
Bước 1. An thích đều mọi vị, nên cắt tại 4 cm và 8 cm. Ba miếng: X = sô-cô-la, Y = vani, Z = dâu. Theo An mỗi miếng đáng 4 điểm.
Bước 2. Bình chấm: X = 4 × 2 = 8, Y = 4, Z = 4 × 0,5 = 2. Miếng to nhất X (8), to thứ hai Y (4). Bình gọt X cho còn 4 điểm, tức bỏ ra 2 cm sô-cô-la. Bình gọt đoạn 2–4 cm. Miếng gọt X' = 0–2 cm, phần vụn V = 2–4 cm.
Bước 3. Chi chấm: X' = 2 × 0,5 = 1, Y = 4, Z = 8. Chi lấy Z.
Bước 4. Bình thấy X' = 4 và Y = 4, bằng nhau. Vì Chi không lấy miếng gọt, Bình bắt buộc lấy X'.
Bước 5. An nhận Y, đáng 4 điểm theo An.
Kiểm tra giữa chừng: An thấy X' = 2, Y = 4, Z = 4, An giữ Y nên không kém ai. Bình thấy X' = 4, Y = 4, Z = 2, không kém ai. Chi thấy Z = 8 hơn Y = 4 và X' = 1.
Bước 6–8. Bình giữ miếng gọt, nên Chi là người cắt vụn. Phần vụn là 2 cm sô-cô-la, Chi chấm đều 0,5 điểm/cm, nên cắt ba mẩu dài 2/3 cm. Bình chọn trước, An chọn sau, Chi lấy mẩu cuối. Vì sô-cô-la đồng đều với cả ba người, mẩu nào cũng như nhau.
| Người | Nhận | Theo An | Theo Bình | Theo Chi |
|---|---|---|---|---|
| An | Y + 2/3 cm sô-cô-la | 4 + 0,67 = 4,67 | 4 + 1,33 = 5,33 | 4 + 0,33 = 4,33 |
| Bình | X' + 2/3 cm sô-cô-la | 2 + 0,67 = 2,67 | 4 + 1,33 = 5,33 | 1 + 0,33 = 1,33 |
| Chi | Z + 2/3 cm sô-cô-la | 4 + 0,67 = 4,67 | 2 + 1,33 = 3,33 | 8 + 0,33 = 8,33 |
Đọc theo cột: An thấy phần mình 4,67, bằng phần Chi và hơn phần Bình. Bình thấy phần mình 5,33, bằng phần An và hơn phần Chi. Chi thấy phần mình 8,33, hơn hẳn hai người kia. Không ai ghen. Để ý hai chỗ "bằng nhau": thuật toán chỉ bảo đảm không ai thấy mình kém, chứ không bảo đảm ai cũng thấy mình hơn.
Tính theo tỉ lệ trên cả chiếc bánh theo từng người: An được 4,67/12 ≈ 39%, Bình 5,33/14 ≈ 38%, Chi 8,33/14 ≈ 60%. Ai cũng hơn một phần ba, đúng như lý thuyết dự đoán, vì không ghen tị kéo theo tương xứng.
Những chỗ hay hiểu sai
- "P2 gọt rồi được chọn trước". Sai. P3 chọn trước, P2 chọn thứ hai. Nếu để P2 chọn trước, P3 có thể ghen.
- "P2 được tự do chọn". Không hẳn. Nếu miếng gọt còn đó, P2 phải lấy nó. Nếu bỏ luật này, P1 có thể phải nhận miếng gọt, và P1 sẽ ghen vì miếng gọt nhỏ hơn một phần ba theo P1.
- "Người cắt vụn luôn là P3". Không. Người cắt vụn là người không giữ miếng gọt, có thể là P2 nếu P3 đã lấy miếng gọt.
- "Thuật toán bảo đảm ai cũng được như nhau". Không. Trong ví dụ, Chi thấy mình được 60% còn Bình thấy mình được 38%. Không ghen tị không phải là ngang bằng.
Đổi sang chia việc nhà thì sao
Nếu thứ cần chia là việc không ai muốn làm, như ca trực đêm hay danh sách việc nhà, mọi chiều so sánh đảo ngược: ai cũng muốn phần nhỏ nhất. Quy trình Selfridge–Conway không đảo ngược máy móc được, vì "gọt bớt miếng nặng nhất" ở đây sẽ tạo ra phần vụn mà không ai muốn nhận, và thứ tự chọn phải sắp lại. Các nhà nghiên cứu đã đưa ra những quy trình riêng cho chia việc không ghen tị, chẳng hạn quy trình ba người của Oskui được Robertson và Webb ghi lại năm 1998, và quy trình dao di động cho bốn người của Peterson và Su năm 2002.
Góc nhìn hôm nay: dùng thật trên bàn ăn
Ngoài đời, khó ai ngồi chấm điểm từng xăng-ti-mét. Nhưng nhịp của thuật toán dùng được ngay khi ba anh em chia một chiếc bánh kem có hoa trang trí ở một góc:
- Người cắt khéo nhất cắt ba miếng mình thấy ngang nhau.
- Người thứ hai nói miếng nào "hơn hẳn", rồi tự gọt bớt chỗ hơn đó để riêng ra đĩa.
- Người thứ ba chọn trước, người thứ hai chọn sau và phải lấy miếng vừa gọt nếu còn, người cắt lấy miếng cuối.
- Đĩa vụn: người không giữ miếng gọt chia ba, người giữ miếng gọt chọn trước, người cắt ban đầu chọn sau.
Muốn hiểu sâu, có thể đọc chương về ba người trong Fair Division của Brams và Taylor, hoặc tự cầm bút vẽ một đoạn thẳng, chia ba vùng màu, gán mỗi người một mật độ điểm như ví dụ trên rồi chạy lại từng bước. Đổi mật độ vài lần sẽ thấy thuật toán chưa bao giờ hỏng.
Câu hỏi thường gặp
Thuật toán Selfridge–Conway là gì?
Là quy trình chia một vật chia được như bánh cho ba người sao cho không ai ghen tị, dùng tối đa năm nhát cắt. Người thứ nhất cắt ba phần bằng nhau, người thứ hai gọt miếng to nhất, ba người chọn theo thứ tự P3, P2, P1, rồi phần vụn được chia thêm một vòng.
Ai tìm ra thuật toán Selfridge–Conway và năm nào?
John Selfridge và John Horton Conway tìm ra độc lập với nhau vào khoảng năm 1960. Cả hai không công bố thành bài báo riêng; quy trình được lan truyền trong giới toán và về sau được trình bày trong các sách về chia công bằng, nổi bật là sách của Brams và Taylor năm 1996.
Vì sao Selfridge–Conway cần đúng năm nhát cắt?
Hai nhát để cắt ba miếng ban đầu, một nhát để gọt miếng to nhất, và hai nhát để chia phần vụn thành ba mẩu. Nếu hai miếng to nhất đã bằng nhau theo người thứ hai thì không cần gọt, khi đó chỉ cần hai nhát.
Selfridge–Conway có cho mỗi người một miếng liền không?
Không. Người được mẩu vụn sẽ có một miếng chính và một mẩu nhỏ rời. Stromquist đã chứng minh năm 2008 rằng với ba người trở lên, không quy trình hữu hạn nào luôn cho cách chia không ghen tị bằng miếng liền.
Có thể dùng Selfridge–Conway cho bốn người không?
Không trực tiếp. Bài toán bốn người trở lên khó hơn nhiều; lời giải hữu hạn đầu tiên cho mọi số người là của Brams và Taylor năm 1995, nhưng số nhát cắt không bị chặn trước. Phải tới năm 2016, Aziz và Mackenzie mới đưa ra quy trình có giới hạn trên cho mọi số người.