Phương pháp người chia đơn độc của Steinhaus chia một vật cho ba người sao cho mỗi người được ít nhất một phần ba theo đánh giá của chính mình. Một người cắt ba phần bằng nhau theo ý mình, hai người còn lại nói phần nào họ chấp nhận được, rồi tuỳ câu trả lời mà xếp thứ tự chọn hoặc gộp hai phần lại cho hai người chia đôi. Phương pháp bảo đảm công bằng tương xứng, nhưng không bảo đảm không ai ghen tị.
Hugo Steinhaus và bài toán chia ba
Hugo Steinhaus (1887–1972) là nhà toán học Ba Lan, người phát hiện tài năng của Stefan Banach, một trong những người lập nên trường phái toán học Lwów. Trong thời gian Ba Lan bị chiếm đóng ở Thế chiến thứ hai, ông phải sống ẩn danh, và chính trong những năm đó ông nghĩ về câu hỏi: chia một vật cho ba người, mỗi người đánh giá khác nhau, làm sao để ai cũng thấy mình được ít nhất một phần ba, mà không cần trọng tài?
Lời giải của ông được biết dưới tên lone divider, tạm dịch "người chia đơn độc", vì chỉ có một người cầm dao. Steinhaus trình bày bài toán và các lời giải cho ba người và nhiều người hơn (phần sau nhờ Banach và Knaster) trong bài "The Problem of Fair Division" đăng trên tạp chí Econometrica năm 1948. Năm 1967, Harold Kuhn mở rộng ý tưởng người chia đơn độc cho số người bất kỳ, dùng một định lý tổ hợp về ghép cặp gọi là định lý Frobenius–König.
Các bước cho ba người
Gọi ba người là An (người chia), Bình và Chi.
- An chia vật thành ba phần X, Y, Z mà An thấy bằng nhau, mỗi phần đúng một phần ba theo An.
- Bình và Chi, mỗi người độc lập đánh dấu những phần mà mình thấy đáng ít nhất một phần ba. Gọi đó là các phần chấp nhận được. Mỗi người luôn có ít nhất một phần chấp nhận được, vì ba phần cộng lại là cả vật, không thể cả ba đều dưới một phần ba.
- Xét ba trường hợp:
- Trường hợp A: Bình chấp nhận được ít nhất hai phần. Chi chọn trước phần mình thích nhất, Bình chọn tiếp (vẫn còn ít nhất một phần Bình chấp nhận), An lấy phần cuối.
- Trường hợp B: Chi chấp nhận được ít nhất hai phần. Làm như trên nhưng đảo vai: Bình chọn trước, Chi chọn tiếp, An lấy phần cuối.
- Trường hợp C: Bình và Chi mỗi người chỉ chấp nhận đúng một phần. Nếu hai phần đó khác nhau, mỗi người lấy phần của mình, An lấy phần còn lại. Nếu là cùng một phần, thì có ít nhất một phần mà cả hai đều không chấp nhận; đưa phần đó cho An. Hai phần còn lại ghép làm một, Bình và Chi chia đôi bằng cách một người cắt, một người chọn.
Vì sao ai cũng được ít nhất một phần ba
An luôn được một trong ba phần mình cắt, mỗi phần đúng một phần ba theo An. Xong phần của An.
Trường hợp A và B rõ ràng: người chọn đầu lấy phần mình thích nhất, mà phần thích nhất trong ba phần cộng lại thành cả vật thì ít nhất là một phần ba. Người chọn thứ hai còn ít nhất một phần chấp nhận được vì đã đánh dấu từ hai phần trở lên.
Trường hợp C có mẹo nhỏ. Phần đưa cho An là phần cả Bình và Chi đều thấy dưới một phần ba. Vậy hai phần còn lại, theo Bình, đáng hơn hai phần ba; theo Chi cũng vậy. Khi Bình và Chi chia đôi phần ghép bằng cắt và chọn, mỗi người được ít nhất một nửa của thứ đáng hơn hai phần ba, tức hơn một phần ba. Chính vì đưa cho An phần cả hai đều chê, phần còn lại mới đủ "béo" cho hai người.
Ví dụ: ba người thuê chung một mảnh vườn rau
Ba người bạn ở ven đô thuê chung một mảnh vườn dài, định chia thành ba luống liền để mỗi người tự trồng. Mảnh vườn có chỗ gần giếng nước, chỗ nắng nhiều, chỗ đất tơi; mỗi người coi trọng một thứ khác. An, người ít kén chọn nhất, cầm dây chia ba luống X, Y, Z mà An thấy ngang nhau. Bình và Chi chấm điểm theo phần trăm giá trị cả mảnh vườn.
Lần chia thứ nhất
| Người | Luống X (gần giếng) | Luống Y (giữa) | Luống Z (cuối, nhiều nắng) |
|---|---|---|---|
| An | 33,3 | 33,3 | 33,3 |
| Bình | 50 | 30 | 20 |
| Chi | 45 | 35 | 20 |
Bình chỉ chấp nhận X (50 ≥ 33,3); Y được 30, Z được 20, đều dưới một phần ba. Chi chấp nhận X (45) và Y (35). Chi có hai phần chấp nhận được, rơi vào trường hợp B: Bình chọn trước, lấy X. Chi chọn tiếp, lấy Y. An nhận Z.
Kết quả: An 33,3%, Bình 50%, Chi 35%. Ai cũng đạt một phần ba. Nhưng Chi nhìn sang luống X của Bình mà Chi chấm 45, hơn luống Y của mình (35) tới 10 điểm. Chi ghen. Đây là chỗ phương pháp Steinhaus dừng lại: nó hứa "đủ phần", không hứa "không kém ai".
Lần chia thứ hai, cùng mảnh vườn nhưng Chi đổi ý
Giả sử Chi coi trọng cái giếng hơn nữa và chấm X = 60, Y = 25, Z = 15. Bây giờ cả Bình lẫn Chi đều chỉ chấp nhận X. Đây là trường hợp C với cùng một phần.
- Luống Z bị cả hai chê (Bình 20, Chi 15). Đưa Z cho An.
- Ghép X và Y thành một dải dài. Theo Bình dải này đáng 80, theo Chi đáng 85.
- Bình cắt dải thành hai đoạn mà Bình thấy bằng nhau, mỗi đoạn 40 theo Bình. Chi chọn đoạn mình thích hơn. Vì Chi thấy cả dải đáng 85, đoạn Chi chọn đáng ít nhất 42,5 theo Chi.
Kết quả: An 33,3%, Bình 40%, Chi ít nhất 42,5%. Tất cả vượt một phần ba. Để ý dây chia của Bình sẽ nằm trong khu vực gần giếng, vì Bình chấm X cao, nên hai người chia nhau cái giếng một cách tự nhiên.
So với các cách chia ba khác
| Phương pháp | Bảo đảm | Số nhát cắt tối đa | Miếng liền? |
|---|---|---|---|
| Người chia đơn độc (Steinhaus) | Tương xứng | 3 (2 của người chia, 1 nếu phải chia đôi phần ghép) | Có thể không: phần ghép từ hai luống không kề nhau sẽ rời |
| Cắt bớt cuối cùng (Banach–Knaster) | Tương xứng | Vài nhát gọt mỗi vòng | Có |
| Dao di động (Dubins–Spanier) | Tương xứng | 2 | Có |
| Selfridge–Conway | Không ghen tị | 5 | Không |
Phương pháp người chia đơn độc có ưu điểm riêng: hai người không cầm dao chỉ cần trả lời câu hỏi "có/không" cho từng phần, không cần biết đo đạc chính xác. Với những người không quen ước lượng, hỏi "luống này có đáng một phần ba không" dễ hơn nhiều so với "cắt cho tôi đúng một phần ba".
Người chia có thiệt không
An luôn nhận phần mà người khác ít muốn nhất, nên An gần như chắc chắn chỉ được đúng một phần ba theo mình, trong khi Bình và Chi thường được hơn. Đây là cái giá của vai người chia. Vì thế, trong thực hành, người ta thường để người có đánh giá "phẳng" nhất, ít quan tâm sự khác biệt giữa các phần, đứng ra chia. Với người như vậy, thiệt thòi gần như bằng không. Nếu cả ba đều kén chọn, có thể bốc thăm vai người chia.
Một điểm tinh tế nữa: An phải chia thật bằng nhau theo ý mình. Nếu An cố tình chia lệch, hi vọng giữ phần to, An có thể bị dồn phần nhỏ, vì An luôn là người nhận phần cuối. Phương pháp không ép An phải trung thực, nhưng trung thực là chiến lược an toàn nhất cho An.
Mở rộng cho n người: Kuhn 1967
Với n người, người chia cắt n phần bằng nhau theo mình, mỗi người còn lại đánh dấu các phần chấp nhận được. Kuhn chứng minh rằng luôn có thể chọn ra một nhóm phần "không ai trong nhóm người còn lại cần gấp" để giao bớt, sao cho những người còn lại vẫn có phần chấp nhận được, hoặc gộp các phần thừa lại để chia tiếp cho nhóm nhỏ hơn bằng chính quy trình đó. Công cụ chứng minh là định lý về ghép cặp trong đồ thị hai phía, cùng họ với định lý hôn nhân của Hall. Phương pháp vì thế là một ví dụ sớm cho thấy tổ hợp học có mặt ngay trong bài toán chia bánh.
Góc nhìn hôm nay: khi nào nên dùng
- Khi chỉ có một người đủ kỹ năng hoặc dụng cụ để cắt, như chia một mảnh vườn bằng dây và cọc, chia một tấm vải, chia một bản đồ khu vực trực.
- Khi mục tiêu là "ai cũng đủ phần" và nhóm không quá so bì. Nếu nhóm hay so bì, dùng Selfridge–Conway để chặn ghen tị.
- Khi muốn dạy trẻ lớn hoặc học sinh về lập luận toán: trường hợp C là bài tập đẹp về "đưa phần cả hai chê cho người thứ ba".
Muốn đọc thêm, bài gốc của Steinhaus trên Econometrica (1948) rất ngắn và vẫn đọc được. Cuốn Cake-Cutting Algorithms (1998) của Robertson và Webb có chương riêng về các phương pháp người chia đơn độc và phép mở rộng của Kuhn.
Câu hỏi thường gặp
Phương pháp người chia đơn độc là gì?
Là cách chia của Hugo Steinhaus cho ba người: một người chia ba phần bằng nhau theo mình, hai người kia đánh dấu phần nào đáng ít nhất một phần ba, rồi xếp thứ tự chọn hoặc gộp hai phần cho hai người chia đôi. Mỗi người luôn được ít nhất một phần ba theo đánh giá riêng.
Phương pháp Steinhaus có bảo đảm không ghen tị không?
Không. Phương pháp chỉ bảo đảm mỗi người được ít nhất một phần ba. Một người có thể đủ phần mà vẫn thấy phần của người khác lớn hơn phần mình. Muốn chặn ghen tị cho ba người phải dùng quy trình như Selfridge–Conway.
Vì sao trong phương pháp Steinhaus người chia thường thiệt?
Vì người chia luôn nhận phần cuối cùng, phần mà hai người kia ít muốn nhất. Người chia gần như chỉ được đúng một phần ba theo mình, trong khi người khác thường được hơn. Nên để người ít kén chọn nhất đứng ra chia.
Steinhaus công bố bài toán chia công bằng năm nào?
Steinhaus nghĩ về bài toán trong Thế chiến thứ hai và công bố bài "The Problem of Fair Division" trên tạp chí Econometrica năm 1948. Bài trình bày cách chia cho ba người và nhắc tới lời giải nhiều người của Banach và Knaster.
Phương pháp người chia đơn độc dùng được cho bốn người không?
Được. Harold Kuhn mở rộng cho số người bất kỳ năm 1967, dùng định lý Frobenius–König về ghép cặp. Quy trình phức tạp hơn bản ba người nhưng vẫn bảo đảm mỗi người được ít nhất 1/n.