Định lý vòng cổ chia ngọc (necklace splitting) nói rằng: một chuỗi hạt mở hai đầu có k loại ngọc, mỗi loại có số hạt chẵn, thì hai người luôn chia đều được mọi loại ngọc chỉ bằng không quá k nhát cắt, giữ nguyên thứ tự các hạt. Ba loại ngọc thì 3 nhát là đủ, dù hạt xếp lộn xộn thế nào. Con số k không thể giảm, và tổng quát cho q người thì cần (q − 1) × k nhát.
Câu chuyện hai tên trộm
Cách kể quen thuộc: hai tên trộm lấy được một chuỗi ngọc quý, gồm hồng ngọc, lam ngọc, lục bảo… xếp theo một thứ tự nào đó. Chúng muốn chia sao cho mỗi người được đúng nửa số hạt của từng loại. Đứt dây thì hạt rơi, nên phải cắt càng ít càng tốt. Các đoạn cắt ra được phân cho người này hoặc người kia, không cần xen kẽ. Hỏi cần mấy nhát?
Câu trả lời: số nhát bằng số loại ngọc. Chuỗi có thể dài một nghìn hạt, xếp bừa bãi, nhưng nếu chỉ có 3 loại thì 3 nhát vẫn đủ.
Thử với hai loại: một cửa sổ trượt
Trường hợp hai loại ngọc giải được bằng một mẹo đơn giản mà ai cũng kiểm tra được. Giả sử chuỗi có 2m hạt hồng ngọc và một số chẵn hạt lục bảo, tổng cộng 2N hạt. Mỗi người cần N hạt, trong đó m hạt hồng ngọc.
- Lấy một "cửa sổ" gồm N hạt liên tiếp, bắt đầu ở đầu chuỗi. Đếm số hồng ngọc trong cửa sổ, gọi là h.
- Trượt cửa sổ sang phải từng hạt một. Mỗi bước, một hạt rời cửa sổ và một hạt vào, nên h thay đổi nhiều nhất 1.
- Khi cửa sổ trượt tới cuối, nó đúng là nửa sau của chuỗi. Số hồng ngọc ở nửa sau bằng 2m trừ số ở nửa đầu. Nếu nửa đầu nhiều hơn m thì nửa sau ít hơn m, và ngược lại.
- h đi từ trên m xuống dưới m (hoặc ngược lại) từng bước một, nên phải đi qua đúng m. Ở vị trí đó, cửa sổ có m hồng ngọc và N − m lục bảo, đúng một nửa mỗi loại.
Cắt hai nhát ở hai đầu cửa sổ: người thứ nhất lấy đoạn giữa, người thứ hai lấy hai đoạn hai đầu. Xong với 2 nhát, đúng như định lý hứa. Đây chính là lập luận giá trị trung gian, phiên bản đếm hạt.
Thử với ba loại: một ví dụ cụ thể
Gọi H là hồng ngọc, L là lam ngọc, B là lục bảo. Chuỗi 12 hạt sau có mỗi loại 4 hạt:
B H H L L H B L B B H L
Mỗi người cần 2 H, 2 L, 2 B. Thử bằng máy tính mọi cách cắt cho thấy với chuỗi này 1 nhát hay 2 nhát đều không đủ; cần đúng 3 nhát. Một lời giải:
| Đoạn | Các hạt | Giao cho |
|---|---|---|
| Đoạn 1 | B | Người thứ nhất |
| Đoạn 2 | H | Người thứ hai |
| Đoạn 3 | H L L H B | Người thứ nhất |
| Đoạn 4 | L B B H L | Người thứ hai |
Người thứ nhất được B + H L L H B = 2 H, 2 L, 2 B. Người thứ hai được H + L B B H L = 2 H, 2 L, 2 B. Ba nhát cắt nằm sau hạt thứ 1, thứ 2 và thứ 7.
Vì sao không thể ít hơn k nhát
Có một cách xếp chuỗi buộc phải dùng đủ k nhát: xếp các loại thành từng khối liền nhau. Ví dụ với ba loại:
H H H H L L L L B B B B
Khối 4 hồng ngọc phải bị chia đôi, nên phải có ít nhất một nhát cắt nằm bên trong khối đó. Tương tự cho khối lam ngọc và khối lục bảo. Ba khối rời nhau, cần ít nhất ba nhát. Lời giải đúng là cắt ngay giữa mỗi khối: H H | H H L L | L L B B | B B, giao đoạn 1 và 3 cho một người, đoạn 2 và 4 cho người kia. Như vậy k nhát vừa đủ trong mọi trường hợp và có lúc không thể ít hơn.
Lịch sử và chứng minh
Bài toán được Charles Goldberg và Douglas West chứng minh năm 1985 cho hai người. Năm 1986, Noga Alon và West đưa ra chứng minh ngắn gọn dựa trên định lý Borsuk–Ulam, chính công cụ tô-pô dùng để chứng minh định lý bánh kẹp. Năm 1987, Alon mở rộng cho q người: với k loại ngọc, mỗi loại có số hạt chia hết cho q, thì (q − 1) × k nhát luôn đủ.
| Số người | Số loại ngọc | Số nhát luôn đủ |
|---|---|---|
| 2 | 1 | 1 |
| 2 | 3 | 3 |
| 2 | 10 | 10 |
| 3 | 3 | 6 |
| 4 | 5 | 15 |
Ý tưởng chứng minh qua Borsuk–Ulam
Coi chuỗi hạt như một đoạn thẳng dài 1, mỗi loại ngọc phân bố trên đó như một lớp "sơn" có độ dày. Một cách cắt k nhát cho ra k + 1 đoạn với độ dài cộng lại bằng 1. Gán dấu cộng cho đoạn thuộc người thứ nhất, dấu trừ cho đoạn thuộc người thứ hai. Mỗi cách cắt kèm cách giao như vậy tương ứng với một điểm trên mặt cầu k chiều: toạ độ là căn bậc hai độ dài các đoạn, kèm dấu. Đổi dấu toàn bộ, tức đổi vai hai người, là đi tới điểm đối xứng. Hàm "người thứ nhất được hơn người thứ hai bao nhiêu, theo từng loại ngọc" cho ra k con số và đổi dấu khi đi tới điểm đối xứng. Borsuk–Ulam bảo đảm có một điểm mà k con số này đồng thời bằng 0: đó là cách cắt chia đều mọi loại.
Kết quả cho bản liên tục, với "sơn" phân bố tuỳ ý trên đoạn thẳng, được Charles Hobby và John Rice chứng minh năm 1965 trong một bài toán về xấp xỉ hàm, trước khi ai nghĩ tới chuyện chuỗi ngọc.
Tìm nhát cắt có dễ không
Biết chắc nhát cắt tồn tại không có nghĩa là tìm ra nhanh. Trong hai công trình năm 2018 và 2019, Aris Filos-Ratsikas và Paul Goldberg chứng minh bài toán tìm cách chia chuỗi ngọc cho hai người thuộc lớp độ phức tạp PPA và là một trong những bài "khó nhất" của lớp này. Nói nôm na: với số loại ngọc lớn, người ta tin là không có thuật toán nhanh nào bảo đảm tìm ra lời giải, dù lời giải chắc chắn có.
Với chuỗi ngắn và ít loại thì khác: thử mọi vị trí cắt là đủ. Chuỗi 12 hạt, 3 nhát chỉ có 165 cách đặt vị trí cắt, mỗi cách thử 16 cách giao đoạn, tổng cộng vài nghìn phép thử.
Không chỉ là ngọc
- Chia một lịch trực: một chuỗi ngày trong năm có ngày thường, cuối tuần, ngày lễ. Muốn chia thành vài khoảng liên tục cho hai nhóm sao cho mỗi nhóm có đúng nửa số ngày mỗi loại, định lý nói 3 điểm ngắt là đủ.
- Chia một con đường: đoạn đường cần bảo trì có đoạn đèo, đoạn đồng bằng, đoạn qua khu dân cư. Hai đội nhận các đoạn liên tục sao cho mỗi đội có nửa chiều dài mỗi loại.
- Chia một cuộn vải in hoa: cuộn vải có ba họa tiết rải rác, cắt thành các đoạn cho hai thợ may sao cho mỗi người được nửa mỗi hoạ tiết.
- Chia đồng thuận (consensus halving): trong lý thuyết chia công bằng, khi n người có đánh giá khác nhau về một dải tài nguyên, n nhát cắt đủ để chia thành hai phần mà ai cũng thấy đều nhau. Đây đúng là định lý vòng cổ đội lốt khác.
Góc nhìn hôm nay: tự thử bằng hạt cườm
Xâu 12 đến 20 hạt cườm ba màu theo thứ tự tuỳ ý, mỗi màu số chẵn hạt. Đặt chuỗi lên bàn, dùng que tăm đánh dấu nhát cắt thay vì cắt thật. Thử tìm cách chia với 3 que. Sau vài chuỗi, bạn sẽ thấy mẹo cửa sổ trượt giúp tìm nhanh hai nhát đầu, nhát thứ ba để chỉnh màu còn lệch. Muốn đọc sâu, cuốn Using the Borsuk–Ulam Theorem của Jiří Matoušek có một chương trình bày gọn chứng minh của Alon và West.
Câu hỏi thường gặp
Định lý vòng cổ chia ngọc là gì?
Định lý nói rằng một chuỗi hạt mở có k loại ngọc, mỗi loại số hạt chẵn, luôn chia đều cho hai người được bằng không quá k nhát cắt, giữ nguyên thứ tự hạt. Với q người và số hạt mỗi loại chia hết cho q, cần không quá (q − 1) × k nhát.
Ai chứng minh định lý chia chuỗi ngọc?
Goldberg và West chứng minh năm 1985 cho hai người. Alon và West đưa ra chứng minh ngắn bằng định lý Borsuk–Ulam năm 1986. Alon mở rộng cho nhiều người năm 1987. Bản liên tục đã có từ định lý Hobby–Rice năm 1965.
Vì sao chia chuỗi ngọc cần đủ k nhát?
Nếu mỗi loại ngọc xếp thành một khối liền nhau, mỗi khối phải bị chia đôi nên cần một nhát nằm trong nó. Có k khối rời nhau thì cần ít nhất k nhát. Vì vậy con số k trong định lý là tốt nhất có thể.
Chia chuỗi hai loại hạt cho hai người làm thế nào?
Lấy một cửa sổ gồm nửa số hạt liên tiếp, trượt dọc chuỗi và đếm số hạt loại thứ nhất. Con số này thay đổi từng đơn vị và đi từ trên một nửa xuống dưới một nửa, nên có vị trí đúng bằng một nửa. Cắt hai đầu cửa sổ, một người lấy đoạn giữa, người kia lấy hai đầu.
Định lý vòng cổ liên quan gì đến định lý bánh kẹp?
Cả hai đều được chứng minh bằng định lý Borsuk–Ulam: một hàm liên tục đổi dấu khi đi tới điểm đối xứng trên mặt cầu thì phải bằng 0 ở đâu đó. Định lý bánh kẹp chia đôi vật thể bằng một mặt phẳng, định lý vòng cổ chia đôi nhiều loại tài nguyên trên một đoạn thẳng bằng nhiều nhát cắt.