Muốn chia một vật cho n người sao cho ai cũng được ít nhất 1/n theo đánh giá riêng, có hai thuật toán kinh điển. "Cắt bớt cuối cùng" của Banach và Knaster cho từng người lần lượt gọt một miếng, ai gọt sau cùng thì nhận miếng đó. "Chia đôi" của Even và Paz cho mọi người đánh dấu điểm giữa, cắt đôi nhóm rồi lặp lại, nhanh hơn hẳn khi đông người. Cả hai đều bảo đảm tương xứng, nhưng không bảo đảm không ghen tị.
Bài toán chia n người
Với hai người, một người cắt một người chọn là xong. Với ba người, Steinhaus đưa ra phương pháp người chia đơn độc. Nhưng khi có bốn, năm, hay một trăm người, cần một quy trình có thể lặp lại máy móc. Stefan Banach và Bronisław Knaster, hai đồng nghiệp của Steinhaus ở Ba Lan, tìm ra một quy trình như vậy, được Steinhaus giới thiệu trong bài "The Problem of Fair Division" năm 1948. Gần bốn mươi năm sau, năm 1984, hai nhà khoa học máy tính Shimon Even và Azaria Paz đưa ra một quy trình theo kiểu "chia để trị", dùng ít bước hơn nhiều.
Ở đây, vật cần chia được hình dung như một đoạn thẳng: một chiếc bánh mì que dài, một dải bờ biển, một khoảng thời gian. Mỗi người có một cách đánh giá riêng cho từng đoạn, và mọi phép đo "1/n" đều theo đánh giá của chính người đó.
Cắt bớt cuối cùng (Banach–Knaster)
Các bước
- Người thứ nhất cắt từ đầu đoạn ra một miếng mà mình thấy đáng đúng 1/n.
- Miếng này được chuyền lần lượt qua những người còn lại. Mỗi người, khi cầm miếng, xem nó đáng bao nhiêu theo mình. Nếu thấy nó hơn 1/n, người đó được quyền gọt bớt cho còn đúng 1/n theo mình, phần gọt trả về phần bánh chung. Nếu thấy nó bằng hoặc kém 1/n, người đó chuyền đi mà không gọt.
- Khi miếng đã qua tay mọi người, ai là người gọt sau cùng (hoặc người thứ nhất nếu không ai gọt) nhận miếng đó và rời cuộc chia.
- Lặp lại với n − 1 người và phần bánh còn lại, đo theo 1/(n − 1) phần còn lại. Khi còn hai người, dùng cắt và chọn.
Vì sao ai cũng được ít nhất 1/n
Người nhận miếng ở mỗi vòng là người gọt sau cùng, nên theo họ miếng đó đúng 1/n. Những người còn lại, mỗi người hoặc đã không gọt vì thấy miếng không hơn 1/n, hoặc đã gọt nhưng sau đó có người gọt tiếp làm miếng nhỏ thêm. Dù thế nào, theo mỗi người còn lại, miếng đi ra đáng không quá 1/n, nên phần còn lại đáng ít nhất (n − 1)/n theo họ. Chia phần ấy cho n − 1 người, mỗi người lại được ít nhất 1/(n − 1) của (n − 1)/n, tức ít nhất 1/n. Lập luận quy nạp này đi trọn tới người cuối cùng.
Ví dụ: bốn nhóm cắm trại chia một dải bờ biển
Một dải bờ biển dài 100 m, đánh số từ 0 đến 100. Bốn nhóm An, Bình, Chi, Dũng muốn mỗi nhóm một đoạn liền. Đoạn đầu gần bãi đỗ xe, đoạn giữa có hàng phi lao, đoạn cuối gần ghềnh đá; mỗi nhóm coi trọng thứ khác nhau. Mỗi nhóm cho biết điểm mà từ đầu bãi tới đó là "đúng một phần tư" theo họ:
| Vòng | Phần còn lại | Điểm đánh dấu của từng nhóm | Diễn biến | Ai nhận |
|---|---|---|---|---|
| 1 (4 nhóm, 1/4) | 0–100 | An 30, Bình 22, Chi 27, Dũng 25 | An cắt ở 30. Bình thấy 0–30 hơn một phần tư (vì điểm của Bình là 22), gọt về 22. Chi thấy 0–22 chưa tới một phần tư (điểm của Chi là 27), chuyền. Dũng cũng vậy (điểm 25), chuyền. | Bình: 0–22 |
| 2 (3 nhóm, 1/3 phần còn lại) | 22–100 | An 50, Chi 48, Dũng 55 | An cắt ở 50. Chi gọt về 48. Dũng thấy 22–48 chưa đủ (điểm 55), chuyền. | Chi: 22–48 |
| 3 (2 nhóm) | 48–100 | An chia đôi theo mình tại 74 | Dũng chọn đoạn mình thích hơn, giả sử 74–100 gần ghềnh đá. | Dũng: 74–100; An: 48–74 |
Kiểm tra với Dũng: ở vòng 1, Dũng thấy 0–22 chưa tới một phần tư; ở vòng 2, Dũng thấy 22–48 chưa tới một phần ba của phần còn lại. Vậy phần 48–100 còn lại cho Dũng và An đáng với Dũng ít nhất một nửa giá trị cả bãi, và Dũng chọn trong hai nửa nên được ít nhất một phần tư. Đúng như lập luận.
Giờ nhìn sang ghen tị. An không ghen Bình: An cắt vòng 1 tại 30, nghĩa là theo An đoạn 0–22 đáng chưa tới một phần tư, trong khi An được ít nhất một phần tư. Nhưng Bình thì khác. Bình rời cuộc chia từ vòng 1 với đúng một phần tư theo mình, và không có tiếng nói gì về cách ba nhóm kia chia 78 m còn lại. Nếu Bình chấm đoạn 74–100 gần ghềnh đá đáng tới 35% cả bãi, Bình sẽ ghen với Dũng. Thuật toán không quan tâm điều đó.
Chia đôi (Even–Paz)
Các bước, với số người chẵn cho dễ hình dung
- Mọi người cùng đánh dấu điểm chia đôi phần đang xét theo đánh giá của mình.
- Xếp các điểm đánh dấu từ trái sang phải. Cắt tại điểm thứ n/2.
- Nhóm n/2 người có điểm đánh dấu ở bên trái (kể cả điểm cắt) nhận đoạn bên trái; nhóm còn lại nhận đoạn bên phải.
- Mỗi nhóm lặp lại quy trình trên đoạn của mình, cho tới khi mỗi nhóm chỉ còn một người.
Với số người lẻ, người ta chia nhóm thành phần nhỏ và phần lớn theo tỉ lệ, chẳng hạn 2 và 3 với năm người, và mỗi người đánh dấu điểm cắt theo tỉ lệ 2/5 thay vì 1/2. Ý tưởng giữ nguyên.
Vì sao đúng
Người ở nhóm trái có điểm đánh dấu nằm bên trái điểm cắt hoặc trùng nó, nghĩa là theo họ đoạn trái đáng ít nhất một nửa. Người ở nhóm phải có điểm đánh dấu từ điểm cắt trở sang phải, nên theo họ đoạn phải đáng ít nhất một nửa. Vậy mỗi nhóm n/2 người cầm một đoạn mà ai trong nhóm cũng thấy đáng ít nhất một nửa. Lặp lại quy trình, mỗi người được ít nhất (1/2) chia cho (n/2), tức ít nhất 1/n.
Ví dụ với bốn nhóm trên cùng dải bờ biển
Các điểm chia đôi: Bình 42, Chi 47, An 55, Dũng 60. Cắt tại điểm thứ hai, 47 m. Bình và Chi nhận 0–47, An và Dũng nhận 47–100. Mỗi cặp chia đôi đoạn của mình bằng cắt và chọn. Toàn bộ chỉ cần bốn điểm đánh dấu ở vòng đầu và hai lần cắt chọn ở vòng sau.
Đếm số bước: vì sao Even–Paz nhanh hơn
Các nhà khoa học máy tính đo độ phức tạp của chia bánh bằng số "câu hỏi" phải đặt cho người tham gia: "hãy đánh dấu điểm mà từ đây tới đó đáng x" hoặc "đoạn này đáng bao nhiêu theo bạn". Mô hình này do Jack Robertson và William Webb hệ thống hoá trong cuốn sách năm 1998.
- Cắt bớt cuối cùng: vòng đầu có thể cần n − 1 lần xem xét, vòng sau n − 2, cứ thế. Tổng lại khoảng n(n − 1)/2, tức bậc n bình phương.
- Chia đôi: mỗi tầng, mỗi người đánh dấu một lần; số tầng là khoảng log cơ số 2 của n. Tổng lại khoảng n nhân log2(n).
| Số người n | Cắt bớt cuối cùng, khoảng n(n − 1)/2 | Chia đôi, khoảng n × log2(n) |
|---|---|---|
| 4 | 6 | 8 |
| 8 | 28 | 24 |
| 16 | 120 | 64 |
| 64 | 2.016 | 384 |
| 1.024 | 523.776 | 10.240 |
Với vài người, hai cách ngang nhau; với hàng nghìn người, chia đôi nhanh gấp hàng chục lần. Năm 2006, Jeff Edmonds và Kirk Pruhs chứng minh rằng trong mô hình câu hỏi này, mọi thuật toán chia tương xứng đều cần ít nhất bậc n log n câu hỏi trong trường hợp xấu nhất. Nghĩa là Even–Paz đã đạt tốc độ tốt nhất có thể về bậc độ lớn.
Chỗ yếu chung: tương xứng chứ không phải không ghen tị
Cả hai thuật toán cho ra miếng liền, dùng đúng n − 1 nhát cắt cuối cùng, và bảo đảm 1/n. Cái chúng không làm được là chặn ghen tị. Người rời cuộc chia sớm, như Bình trong ví dụ cắt bớt cuối cùng, chỉ được bảo đảm đúng 1/n và không có tiếng nói gì về cách những người sau chia phần còn lại. Muốn không ai ghen với bốn người trở lên thì phải dùng những quy trình phức tạp hơn nhiều, như Brams–Taylor (1995) hay Aziz–Mackenzie (2016).
Một điểm nữa: với cắt bớt cuối cùng, người gọt có động cơ trung thực. Nếu gọt quá tay, miếng nhỏ hơn 1/n theo mình mà không ai gọt tiếp, mình sẽ nhận miếng nhỏ. Nếu gọt quá nhẹ, người sau có thể gọt tiếp và lấy mất. Gọt đúng 1/n theo mình là cách an toàn nhất.
Góc nhìn hôm nay: dùng ngoài đời
- Cắt bớt cuối cùng hợp với nhóm nhỏ, ngồi cạnh nhau, chuyền tay một vật cụ thể: chia luống vườn, chia đoạn hàng rào phải sơn, chia khúc suối để cắm câu. Người ta hiểu ngay luật "ai gọt sau cùng thì lấy".
- Chia đôi hợp khi có thể thu điểm đánh dấu của mọi người cùng lúc, chẳng hạn qua một bảng tính: mỗi người ghi điểm giữa theo ý mình, sắp xếp, cắt, rồi lặp lại cho từng nửa.
- Với khoảng thời gian, như chia lịch dùng chung một căn nhà nghỉ dưỡng trong mùa hè, đoạn thẳng là trục ngày tháng; hai thuật toán áp dụng y nguyên.
Đọc thêm: bài của Even và Paz đăng trên tạp chí Discrete Applied Mathematics năm 1984 rất ngắn; chương về độ phức tạp trong Handbook of Computational Social Choice (2016) có phần chia bánh do Ariel Procaccia viết, tóm tắt các kết quả về số câu hỏi.
Câu hỏi thường gặp
Phương pháp cắt bớt cuối cùng là gì?
Là thuật toán của Banach và Knaster: người thứ nhất cắt một miếng mình thấy đúng 1/n, miếng được chuyền qua mọi người, ai thấy to hơn 1/n thì gọt bớt, người gọt sau cùng nhận miếng đó. Lặp lại với những người còn lại cho tới hết. Mỗi người được ít nhất 1/n theo đánh giá riêng.
Thuật toán Even–Paz hoạt động thế nào?
Mọi người cùng đánh dấu điểm chia đôi theo ý mình, cắt tại điểm đánh dấu ở giữa, nửa số người bên trái nhận đoạn trái, nửa bên phải nhận đoạn phải, rồi lặp lại trong từng nhóm. Thuật toán do Even và Paz công bố năm 1984, cần khoảng n log n câu hỏi.
Even–Paz nhanh hơn cắt bớt cuối cùng bao nhiêu?
Cắt bớt cuối cùng cần khoảng n(n − 1)/2 câu hỏi trong trường hợp xấu nhất, còn Even–Paz khoảng n log2(n). Với 1.024 người, đó là hơn 500 nghìn so với khoảng 10 nghìn. Edmonds và Pruhs chứng minh năm 2006 rằng không thuật toán chia tương xứng nào làm tốt hơn bậc n log n.
Hai thuật toán này có chia không ghen tị không?
Không. Cả hai chỉ bảo đảm mỗi người được ít nhất 1/n. Người nhận phần sớm có thể ghen với người nhận sau. Chia không ghen tị cho bốn người trở lên cần các quy trình phức tạp hơn như Brams–Taylor hoặc Aziz–Mackenzie.
Ai là Banach và Knaster?
Stefan Banach và Bronisław Knaster là hai nhà toán học Ba Lan thế kỷ 20, cùng thời và cùng trường phái với Hugo Steinhaus. Banach nổi tiếng với giải tích hàm, Knaster với tô-pô học. Thuật toán chia bánh của họ được Steinhaus giới thiệu năm 1948.