Dao di động là kiểu thuật toán chia công bằng trong đó một con dao được đưa chậm và liên tục qua chiếc bánh, ai thấy đủ phần thì hô "dừng". Quy trình Dubins–Spanier (1961) dùng một con dao để mỗi người được ít nhất 1/n. Quy trình Stromquist (1980) dùng bốn con dao để chia không ghen tị cho ba người, mỗi người một miếng liền. Austin (1982) dùng hai con dao để hai người cùng thấy một miếng đúng bằng nửa.
Ý tưởng: thay câu hỏi bằng chuyển động liên tục
Các thuật toán như cắt bớt cuối cùng hay Selfridge–Conway là chuỗi bước rời rạc: cắt, đánh giá, gọt, chọn. Dao di động thì khác. Một con dao được đưa từ trái sang phải trên chiếc bánh, đều đặn, không nhảy cóc. Mỗi người tự theo dõi giá trị phần bánh bên trái con dao theo đánh giá của mình, và hô khi tới ngưỡng. Vì con dao đi liên tục, giá trị phần bên trái tăng liên tục từ 0 lên cả chiếc bánh, nên chắc chắn tới một lúc nào đó có người chạm ngưỡng. Đây là định lý giá trị trung gian, bài học quen thuộc ở lớp giải tích.
Người đặt tên và phổ biến kiểu lập luận này là Lester Dubins và Edwin Spanier, trong bài "How to cut a cake fairly" đăng trên tạp chí American Mathematical Monthly năm 1961.
Dubins–Spanier: một con dao, n người
Các bước
- Một người trọng tài (hoặc bất kỳ ai) đưa dao từ đầu bánh sang phải, thật chậm.
- Ai thấy phần bên trái dao đáng đúng 1/n cả chiếc bánh thì hô "dừng". Bánh cắt tại đó, người hô nhận miếng bên trái và rời cuộc chia. Nếu hai người cùng hô, chọn ngẫu nhiên một người.
- Đưa dao tiếp trên phần còn lại với những người còn lại, mỗi người lại hô khi miếng mới đáng 1/n.
- Người cuối cùng nhận phần còn lại.
Người hô nhận đúng 1/n theo mình. Người chưa hô thấy miếng vừa cắt ra đáng chưa tới 1/n, nên phần còn lại vẫn đủ cho mình. Người cuối cùng nhận phần lớn hơn hoặc bằng 1/n. Lập luận giống hệt cắt bớt cuối cùng, chỉ là việc "gọt" được làm liên tục bởi con dao.
Ví dụ tính tay: chiếc bánh cuộn ba vị
Bánh dài 12 cm: sô-cô-la từ 0 đến 4, vani từ 4 đến 8, dâu từ 8 đến 12. An chấm đều 1 điểm mỗi cm (cả bánh 12, một phần ba là 4). Bình mê sô-cô-la: 2 điểm/cm ở sô-cô-la, 1 ở vani, 0,5 ở dâu (cả bánh 14, một phần ba khoảng 4,67). Chi mê dâu: 0,5 ở sô-cô-la, 1 ở vani, 2 ở dâu (cả bánh 14).
- Dao bắt đầu ở 0. Với Bình, phần bên trái tại vị trí x (trong đoạn sô-cô-la) đáng 2x. Đạt 4,67 khi x ≈ 2,33 cm. An lúc đó mới thấy 2,33 điểm, Chi thấy 1,17 điểm. Bình hô đầu tiên, nhận 0–2,33.
- Dao đi tiếp từ 2,33. An thấy đoạn mới đáng 1 điểm mỗi cm, đạt 4 điểm tại x ≈ 6,33. Chi thấy đoạn 2,33–4 đáng 0,83, rồi thêm 1 điểm mỗi cm vani; tại 6,33 Chi mới thấy 3,17, chưa tới 4,67. An hô, nhận 2,33–6,33.
- Chi nhận 6,33–12: theo Chi đáng 1,67 (vani) + 8 (dâu) = 9,67 điểm, khoảng 69% cả bánh.
| Phần | Theo An | Theo Bình | Theo Chi |
|---|---|---|---|
| Bình: 0–2,33 | 2,33 | 4,67 | 1,17 |
| An: 2,33–6,33 | 4 | 3,33 + 2,33 = 5,67 | 0,83 + 2,33 = 3,17 |
| Chi: 6,33–12 | 5,67 | 1,67 + 2 = 3,67 | 9,67 |
Ai cũng được ít nhất một phần ba theo mình. Nhưng đọc theo cột: Bình thấy miếng của An (5,67) hơn miếng mình (4,67), An thấy miếng của Chi (5,67) hơn miếng mình (4). Hai người ghen. Người hô sớm chỉ được đúng 1/n và mất quyền so bì với phần chia sau. Đây là giới hạn của mọi quy trình "ai đủ thì rời đi".
Stromquist: bốn con dao, ba người, không ai ghen
Năm 1980, Walter Stromquist công bố trên American Mathematical Monthly một quy trình dao di động cho ba người mà không ai ghen tị và mỗi người nhận một miếng liền. Nó dùng một thanh "kiếm" của trọng tài và ba con dao của ba người.
Các bước
- Trọng tài đưa kiếm từ trái sang phải. Kiếm chia bánh thành phần Trái (bên trái kiếm) và phần còn lại bên phải.
- Cùng lúc, mỗi người cầm dao của mình trên phần bên phải, giữ sao cho dao chia đôi phần bên phải thành hai nửa bằng nhau theo đánh giá của chính người đó. Kiếm di chuyển thì các dao cũng di chuyển theo, liên tục.
- Một người hô "cắt" khi thấy phần Trái đáng ít nhất bằng từng miếng mà cuộc cắt sẽ tạo ra. Bánh được cắt tại kiếm và tại con dao nằm giữa trong ba con dao.
- Người hô nhận phần Trái. Trong hai người còn lại, người có dao gần kiếm hơn nhận phần Giữa (từ kiếm tới dao giữa); người kia nhận phần Phải.
Vì sao không ai ghen
- Người hô chỉ hô khi Trái đáng ít nhất bằng Giữa và bằng Phải theo mình. Không ghen.
- Người im lặng có dao gần kiếm hơn: dao của họ nằm bên trái hoặc trùng dao giữa, nên phần Giữa chứa trọn nửa trái theo cách họ chia, tức Giữa đáng ít nhất một nửa phần bên phải theo họ, còn Phải đáng nhiều nhất một nửa. Họ chưa hô nên thấy Trái chưa bằng miếng tốt nhất, mà miếng tốt nhất theo họ là Giữa. Không ghen.
- Người im lặng còn lại: lập luận đối xứng, phần Phải chứa trọn nửa phải theo cách họ chia. Không ghen.
Điều đáng chú ý: cùng năm 1980, Stromquist và Douglas Woodall độc lập chứng minh rằng với số người bất kỳ luôn tồn tại cách chia không ghen tị bằng miếng liền. Nhưng năm 2008, chính Stromquist chứng minh không có quy trình hữu hạn kiểu hỏi đáp nào tìm được nó cho ba người trở lên. Dao di động liên tục đi được nơi mà các bước rời rạc không đi tới.
Austin: hai con dao cho phép chia đúng một nửa
Đôi khi cần mạnh hơn không ghen tị: cả hai người cùng thấy miếng chia ra đúng bằng một nửa, không ai được hơn. Năm 1982, A. K. Austin đưa ra quy trình hai dao.
- An đặt hai con dao: một ở đầu bánh, một ở điểm mà An thấy chia đôi bánh. Phần giữa hai dao đáng đúng một nửa theo An.
- An di chuyển cả hai dao sang phải, liên tục, luôn giữ cho phần giữa hai dao đáng đúng một nửa theo An. Khi dao trái tới chỗ dao phải lúc đầu, dao phải tới cuối bánh.
- Bình theo dõi. Lúc đầu phần giữa hai dao đáng với Bình một giá trị v nào đó; lúc cuối, phần giữa là đúng phần bù của phần giữa lúc đầu, nên đáng 1 − v. Nếu v nhỏ hơn một nửa thì 1 − v lớn hơn một nửa, và ngược lại. Theo định lý giá trị trung gian, có lúc phần giữa đáng đúng một nửa với Bình. Bình hô tại đó.
Lúc ấy phần giữa hai dao đáng đúng một nửa với cả hai người. Từ đây có thể bốc thăm hoặc cho mỗi người một phần mà không ai thấy hơn kém. Phép chia chính xác như vậy, với số người và số phần tổng quát, được Dubins và Spanier chứng minh là luôn tồn tại, nhưng tìm bằng thủ tục cụ thể thì khó hơn nhiều.
Bốn người với dao di động
Năm 1997, Steven Brams, Alan Taylor và William Zwicker công bố một quy trình dao di động cho bốn người, không ghen tị, dùng tối đa 11 nhát cắt. Quy trình này phức tạp hơn nhiều so với bản ba người, và các miếng không còn liền. Nó cho thấy dao di động đi được xa hơn các bước rời rạc ở thời điểm đó: phải tới năm 2016, Aziz và Mackenzie mới có quy trình rời rạc có giới hạn cho bốn người.
Dao di động có dùng được ngoài đời không
| Quy trình | Số dao | Bảo đảm | Khó khi làm thật |
|---|---|---|---|
| Dubins–Spanier | 1 | Tương xứng, miếng liền | Dễ: chỉ cần mỗi người biết khi nào "đủ" |
| Stromquist | 4 | Không ghen tị, miếng liền, ba người | Khó: ba người phải liên tục chỉnh dao chia đôi phần bên phải |
| Austin | 2 | Hai người cùng thấy đúng một nửa | Vừa: một người cầm hai dao giữ khoảng cách "một nửa" |
| Brams–Taylor–Zwicker | Nhiều | Không ghen tị, bốn người | Rất khó |
Dubins–Spanier thì làm được ngay: chia một khúc cá dài, một cuộn vải, một đoạn hàng rào phải sơn. Người cầm dao kéo từ từ, ai thấy đủ thì giơ tay. Với khoảng thời gian, như chia lượt dùng một chiếc xe chung trong một tháng, "dao" là ngày trên lịch: lật từng ngày, ai thấy đủ thì nhận khoảng thời gian từ đầu tới đó.
Các quy trình nhiều dao chủ yếu có giá trị lý thuyết. Chúng chứng minh rằng một cách chia tồn tại và cho thấy cấu trúc của nó; trên máy tính, người ta mô phỏng con dao bằng cách hỏi giá trị tại nhiều điểm rất gần nhau, chấp nhận sai số nhỏ.
Góc nhìn hôm nay
Ý tưởng dao di động còn sống ở những chỗ ít ngờ. Khi một nhóm kéo thanh trượt giá trên màn hình cho tới khi có người bấm nhận, đó là một con dao di động trên trục giá. Đấu giá đồng hồ giảm dần cũng là con dao chạy trên trục tiền. Muốn hiểu sâu, bài của Dubins và Spanier (1961) và bài của Stromquist (1980) trên American Mathematical Monthly đọc được với kiến thức giải tích năm nhất; cuốn Fair Division của Brams và Taylor có hình vẽ từng bước cho quy trình bốn dao.
Câu hỏi thường gặp
Dao di động trong chia công bằng là gì?
Là kiểu quy trình trong đó một hoặc vài con dao được đưa liên tục qua vật cần chia, và người tham gia hô dừng khi phần bên trái đạt giá trị họ muốn. Nhờ chuyển động liên tục, định lý giá trị trung gian bảo đảm luôn có lúc ai đó chạm ngưỡng.
Quy trình Dubins–Spanier hoạt động thế nào?
Một con dao đi từ trái sang phải, ai thấy phần bên trái đáng 1/n thì hô và nhận phần đó, những người còn lại tiếp tục với phần còn lại. Mỗi người được ít nhất 1/n theo đánh giá riêng, nhưng người hô sớm có thể ghen với người nhận sau. Quy trình do Dubins và Spanier công bố năm 1961.
Quy trình bốn dao của Stromquist là gì?
Là quy trình năm 1980 chia không ghen tị cho ba người, mỗi người một miếng liền. Trọng tài đưa một thanh kiếm, ba người mỗi người giữ một dao chia đôi phần bên phải theo mình; ai hô trước nhận phần trái, hai người còn lại nhận phần giữa và phần phải theo vị trí dao.
Vì sao dao di động làm được điều thuật toán rời rạc không làm được?
Stromquist chứng minh năm 2008 rằng không quy trình hữu hạn kiểu hỏi đáp nào luôn cho cách chia không ghen tị bằng miếng liền cho ba người trở lên. Dao di động không phải quy trình hữu hạn: nó dựa vào chuyển động liên tục và phản xạ hô đúng lúc, nên vượt qua được giới hạn đó.
Có thể chia để cả hai người thấy đúng một nửa không?
Có, với quy trình hai dao của Austin năm 1982. Một người giữ hai dao sao cho phần giữa luôn đúng một nửa theo mình rồi trượt dần; theo định lý giá trị trung gian, sẽ có lúc người kia cũng thấy phần giữa đúng một nửa.