Cắt bánh tròn bằng n nhát thẳng, không xếp chồng, nhiều nhất được n(n+1)/2 + 1 miếng: 1 nhát được 2 miếng, 2 nhát được 4, 3 nhát được 7, 4 nhát được 11, 10 nhát được 56. Dãy số này có tên tiếng Anh vui là lazy caterer's sequence, "dãy số của người phục vụ tiệc lười". Bí quyết là mỗi nhát mới phải cắt qua mọi nhát cũ, và không có ba nhát nào gặp nhau tại cùng một điểm.
Bảng số: n nhát được bao nhiêu miếng
| Số nhát | Tối đa trên mặt bánh (2D) | Tối đa trong khối bánh (3D, cắt cả ngang) |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 2 | 2 |
| 2 | 4 | 4 |
| 3 | 7 | 8 |
| 4 | 11 | 15 |
| 5 | 16 | 26 |
| 6 | 22 | 42 |
| 7 | 29 | 64 |
| 8 | 37 | 93 |
| 10 | 56 | 176 |
Cột giữa là dãy lazy caterer, trong bộ bách khoa dãy số OEIS mang mã A000124. Cột phải gọi là "số bánh" (cake numbers), mã A000125: khi được cắt bằng mặt phẳng nghiêng tuỳ ý xuyên qua khối bánh, chứ không chỉ cắt dọc từ trên xuống.
Vì sao công thức là n(n+1)/2 + 1
Lập luận chỉ cần đếm, không cần đại số. Giả sử đã có k − 1 nhát. Nhát thứ k là một đường thẳng chạy từ mép này sang mép kia. Nếu nó cắt qua tất cả k − 1 nhát cũ, tại k − 1 điểm khác nhau, thì các giao điểm chia nó thành k đoạn. Mỗi đoạn chạy qua một miếng cũ và tách miếng đó làm đôi. Vậy nhát thứ k thêm đúng k miếng.
Bắt đầu từ 1 miếng (bánh nguyên), cộng lần lượt 1, 2, 3, …, n:
Số miếng = 1 + (1 + 2 + 3 + … + n) = 1 + n(n+1)/2.
Ví dụ 4 nhát: 1 + 1 + 2 + 3 + 4 = 11. Ví dụ 6 nhát: 1 + 21 = 22.
Lập luận cũng cho thấy khi nào bị hụt miếng. Nếu nhát mới song song với một nhát cũ, nó mất một giao điểm, thêm ít đi một miếng. Nếu nhát mới đi qua đúng giao điểm của hai nhát cũ, hai giao điểm gộp làm một, lại hụt một miếng. Đó là lý do cách cắt "đẹp" mọi nhát qua tâm chỉ cho 2n miếng: 4 nhát qua tâm được 8 miếng thay vì 11.
Kiểm bằng tay với 3 nhát
Vẽ một vòng tròn. Nhát 1 cắt ngang, được 2 miếng. Nhát 2 cắt chéo qua nhát 1, được 4 miếng. Nhát 3 phải cắt cả hai nhát cũ nhưng không đi qua giao điểm của chúng: kẻ một đường gần mép, xiên sao cho nó băng qua cả hai đường. Bạn sẽ đếm được 7 miếng: một tam giác nhỏ ở giữa, ba miếng giáp ba cạnh của tam giác và ba miếng giáp ba đỉnh của nó. Đổi tam giác giữa thành một điểm (ba nhát đồng quy) là tụt về 6 miếng.
Lên ba chiều: số bánh và công thức tổ hợp
Khi được cắt bằng mặt phẳng tuỳ ý xuyên khối, nhát thứ k là một mặt phẳng. Nó gặp k − 1 mặt phẳng cũ theo k − 1 đường thẳng, và các đường này chia chính mặt phẳng mới thành nhiều mảnh, nhiều nhất bằng số miếng lazy caterer với k − 1 nhát. Mỗi mảnh tách một miếng bánh cũ làm đôi. Cộng dồn được công thức:
Số miếng tối đa = (n³ + 5n + 6) / 6, viết bằng chữ là (n mũ ba cộng 5n cộng 6) chia 6.
Có một cách viết đẹp hơn, nối hai chiều với nhau. Gọi C(n, k) là số cách chọn k phần tử từ n phần tử. Khi đó:
- Trên đoạn thẳng (1 chiều), n điểm cắt chia đoạn thành C(n,0) + C(n,1) = 1 + n phần.
- Trên mặt phẳng, n đường thẳng chia thành C(n,0) + C(n,1) + C(n,2) phần. Với n = 4: 1 + 4 + 6 = 11.
- Trong không gian, n mặt phẳng chia thành C(n,0) + C(n,1) + C(n,2) + C(n,3) phần. Với n = 4: 1 + 4 + 6 + 4 = 15.
Công thức số miền do n đường thẳng tạo ra được Jakob Steiner nghiên cứu năm 1826, cùng với bài toán mặt phẳng chia không gian. Còn cái tên "người phục vụ tiệc lười" là tên gọi vui đời sau, ý nói người phục vụ chỉ muốn ít nhát dao mà vẫn đủ miếng cho cả bàn.
Bẫy quy luật: chia hình tròn bằng dây cung
Có một bài toán anh em rất hay bị nhầm với bài trên, và nó dạy một bài học đắt giá: đừng tin quy luật khi chưa chứng minh. Đặt n điểm trên vòng tròn, nối mọi cặp điểm bằng dây cung, sao cho không có ba dây nào đồng quy bên trong. Đếm số miền:
| Số điểm | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Số miền | 1 | 2 | 4 | 8 | 16 | 31 | 57 |
Năm số đầu là 1, 2, 4, 8, 16, ai cũng đoán số tiếp theo là 32. Nhưng đếm cẩn thận với 6 điểm chỉ được 31. Công thức đúng là C(n,4) + C(n,2) + 1: mỗi bộ bốn điểm trên vòng tròn cho đúng một giao điểm của hai dây chéo, và mỗi giao điểm cùng mỗi dây cung góp thêm miền. Với n = 6: 15 + 15 + 1 = 31. Bài toán thường được gọi là bài toán chia hình tròn của Moser, theo tên Leo Moser.
Thêm ràng buộc thì sao
Miếng phải bằng nhau
Muốn n miếng bằng nhau trên mặt bánh, cách đơn giản nhất là cắt qua tâm, và lúc đó n/2 nhát qua tâm cho n miếng (n chẵn). Đổi lại số nhát tăng gấp đôi so với cách cắt tối đa. Cách cắt lazy caterer cho nhiều miếng nhưng miếng to miếng nhỏ chênh nhau rất xa; với 4 nhát, miếng nhỏ nhất ở giữa có khi chỉ bằng vài phần trăm miếng to nhất.
Được xếp chồng sau mỗi nhát
Nếu được nhấc các miếng lên, xếp chồng rồi mới cắt nhát tiếp, số miếng có thể gấp đôi sau mỗi nhát: 2, 4, 8, 16, …, tức 2 mũ n. Với 10 nhát, xếp chồng cho tới 1.024 miếng so với 56 miếng nếu không xếp. Bài toán cắt khối lập phương thành 27 khối nhỏ bằng 6 nhát cũng xoay quanh chuyện xếp chồng có giúp được hay không.
Bánh không tròn
Hình bánh không ảnh hưởng tới con số tối đa, miễn bánh là hình lồi (vuông, chữ nhật, tam giác, bầu dục). Với hình lõm như bánh hình chữ C hay hình sao, một nhát thẳng có thể đi ra rồi lại vào bánh, tạo nhiều miếng hơn công thức. Một nhát cắt qua chiếc bánh hình chữ U có thể cho 3 miếng ngay từ đầu.
Ở đâu ngoài bàn tiệc
- Quy hoạch đường: n con đường thẳng xuyên một vùng phẳng, không đường nào song song và không ba đường gặp nhau một chỗ, tạo tối đa n(n+1)/2 + 1 khu. Con số này cho biết các nút giao "chéo" sinh ra bao nhiêu mảnh đất lẻ.
- Học máy: mỗi đơn vị tuyến tính trong mạng nơ-ron đơn giản chia không gian dữ liệu bằng một siêu phẳng; đếm số miền tối đa giúp ước lượng khả năng phân loại, và công thức tổng C(n,0) + … + C(n,d) là đúng họ hàng của công thức lazy caterer.
- Tổ hợp: các bài đếm miền là bài tập kinh điển để học quy nạp: chứng minh đúng với n − 1 nhát, rồi xem nhát thứ n thêm bao nhiêu.
Góc nhìn hôm nay: một bài tập cho cả nhà
Lấy một chiếc bánh tráng hoặc tờ giấy tròn và một cây bút. Thử 4 nhát để được 11 miếng. Hầu hết mọi người ra 9 hoặc 10 lần đầu, vì vô thức cho hai nhát gần song song hoặc ba nhát gần đồng quy. Sau đó thử bài dây cung với 6 điểm và đếm cho tới khi chắc chắn là 31. Hai bài này đủ dạy trẻ lớp 6, lớp 7 chuyện quy nạp và chuyện đếm cẩn thận hơn mọi bài giảng.
Người muốn đọc thêm có thể tra mã A000124 và A000125 trên trang OEIS (Bách khoa toàn thư trực tuyến về dãy số nguyên), nơi liệt kê các công thức, cách chứng minh và tài liệu tham khảo cho từng dãy.
Câu hỏi thường gặp
Cắt bánh 3 nhát được tối đa bao nhiêu miếng?
Nếu chỉ cắt thẳng đứng trên mặt bánh, 3 nhát được tối đa 7 miếng, với điều kiện ba nhát cắt nhau đôi một và không gặp nhau tại một điểm. Nếu cho phép cắt ngang qua chiều dày bánh, 3 nhát được 8 miếng, ví dụ hai nhát dọc vuông góc và một nhát ngang ở giữa.
Công thức số miếng tối đa khi cắt bánh n nhát là gì?
Trên mặt phẳng là n(n+1)/2 + 1, gọi là dãy lazy caterer: 2, 4, 7, 11, 16, 22… Trong không gian ba chiều là (n³ + 5n + 6)/6, gọi là số bánh: 2, 4, 8, 15, 26, 42… Cả hai bằng tổng các số tổ hợp C(n, 0) + C(n, 1) + … tới số chiều.
Vì sao cắt qua tâm lại được ít miếng hơn?
Vì mọi nhát qua tâm đều gặp nhau tại cùng một điểm. Mỗi nhát mới chỉ có một giao điểm với các nhát cũ nên chỉ thêm 2 miếng, thay vì thêm k miếng ở nhát thứ k. Bốn nhát qua tâm được 8 miếng, bốn nhát cắt khéo được 11.
Bài toán nối điểm trên đường tròn vì sao ra 31 chứ không phải 32?
Với n điểm trên đường tròn nối đôi một, số miền là C(n,4) + C(n,2) + 1. Năm giá trị đầu trùng với 1, 2, 4, 8, 16 nên dễ tưởng là luỹ thừa của 2, nhưng với 6 điểm công thức cho 15 + 15 + 1 = 31. Đây là ví dụ kinh điển về việc đoán quy luật từ vài số đầu.
Lazy caterer nghĩa là gì?
Lazy caterer là "người phục vụ tiệc lười", tên gọi vui của dãy số n(n+1)/2 + 1, ý nói người cắt bánh muốn có nhiều miếng nhất với ít nhát dao nhất. Dãy này còn gọi là số đa giác trung tâm (central polygonal numbers).