Định lý bánh mì dăm bông

Trong lý thuyết độ đo, định lý bánh mì dăm bông, còn gọi là định lý Stone–Tukey theo Arthur H. Stone và John Tukey, phát biểu rằng với mọi n "đối tượng" đo được trong không gian n chiều, có thể chia tất cả chúng thành hai nửa có cùng độ đo (hay thể tích) bằng một siêu phẳng (n − 1) chiều. Ở đây mỗi đối tượng là một tập hợp có độ đo hữu hạn để khái niệm chia thành hai nửa có cùng thể tích là có nghĩa.

Tên gọi

Tên gọi định lý bánh mì dăm bông xuất phát từ trường hợp n = 3 và ba đối tượng bao gồm một lát dăm bông và hai lát bánh mì tạo thành một bánh mì kẹp. Có thể cắt cả ba lát làm hai nửa bằng nhau bằng một nhát cắt (nghĩa là một mặt phẳng). Trong không gian hai chiều, định lý này được gọi là định lý bánh kếp do phải cắt hai bánh kếp mỏng trên đĩa bằng một nhát cắt thẳng (nghĩa là một đường thẳng).

Định lý bánh mì dăm bông đôi khi còn được gọi là "định lý bánh mì dăm bông và pho mát", theo trường hợp đặc biệt n = 3 và ba đối tượng là

1. một miếng dăm bông,
2. một lát pho mát, và
3. hai lát bánh mì (coi là một đối tượng không liên thông).

Định lý khẳng định rằng có thể cắt dăm bông và pho mát thành hai nửa sao cho mỗi nửa có cùng một lượng dăm bông, pho mát, và bánh mì. Có thể coi hai lát bánh mì là một đối tượng do định lý chỉ yêu cầu thể tích của đối tượng trên mỗi nửa biến thiên liên tục khi mặt phẳng cắt di chuyển trong không gian.

Định lý bánh mì dăm bông không liên quan đến định lý kẹp.

Quy về định lý Borsuk–Ulam

Định lý bánh mì dăm bông có thể được chứng minh bằng cách quy về định lý Borsuk–Ulam. Chứng minh dưới đây là của Steinhaus (1938) và một số người khác, trong đó trường hợp đặc biệt n = 3 đã được chứng minh bởi Stefan Banach.

Đặt A₁, A₂, …, A_n là n đối tượng ta muốn chia đôi. Đặt S là mặt cầu đơn vị n chiều trong không gian Euclid ${\displaystyle \mathbb {R} ^{n}}$, có tâm ở gốc tọa độ. Với mỗi điểm p trên mặt của S, ta xác định một lớp các siêu phẳng afin vuông góc với vectơ từ gốc tọa độ đến p. "Nửa dương" của mỗi siêu phẳng là nửa được vectơ đó chỉ tới. Theo định lý giá trị trung gian, mọi lớp các siêu phẳng xác định như trên đều chứa một siêu phẳng chia đôi đối tượng A_n: nếu tịnh tiến siêu phẳng vô hạn về một hướng, toàn bộ A_n nằm ở nửa dương, mặt khác nếu tịnh tiến siêu phẳng vô hạn về phía kia thì toàn bộ A_n nằm ở nửa âm, nên tồn tại một phép tịnh tiến sao cho độ đo của A_n ở nửa dương là đúng một nửa. Nếu có nhiều hơn một siêu phẳng thỏa mãn tính chất trên thì ta chọn điểm chính giữa của khoảng tịnh tiến trong đó A_n được chia đôi. Như vậy với mỗi điểm p trên mặt cầu S, ta chọn được một siêu phẳng π(p) vuông góc với vectơ từ gốc tọa độ tới p và chia đôi A_n.

Định nghĩa hàm f từ mặt cầu (n − 1) chiều S tới không gian Euclid (n − 1) chiều ${\displaystyle \mathbb {R} ^{n-1}}$ như sau:

f(p) = (độ đo của A₁ trên nửa dương của π(p), độ đo của A₂ trên nửa dương của π(p),..., độ đo của A_n−1 trên nửa dương của π(p)).

Hàm f là liên tục. Theo định lý Borsuk–Ulam, tồn tại hai điểm đối cực p và q trên mặt cầu S sao cho f(p) = f(q). Hai điểm đối cực p và q tương ứng với hai siêu phẳng π(p) và π(q) bằng nhau nhưng có nửa dương ngược nhau. Do đó, f(p) = f(q) nghĩa là A_i có cùng độ đo trên nửa dương và nửa âm của π(p) (hay π(q)), với mọi i = 1, 2,..., n − 1. Vì vậy π(p) (hay π(q)) là lát cắt cần tìm để chia đôi A₁, A₂, …, A_n.

Phiên bản rời rạc và trong hình học tính toán

Trong hình học rời rạc và hình học tính toán, định lý bánh mì dăm bông thường được dùng để chỉ trường hợp đặc biệt khi mỗi đối tượng là một tập hợp hữu hạn các điểm. Độ đo được dùng ở đây là độ đo đếm: đếm số lượng điểm nằm ở mỗi phía của siêu phẳng. Trong trường hợp hai chiều, định lý có thể phát biểu như sau:

Với một tập hợp hữu hạn bất kì các điểm trên mặt phẳng tô màu xanh và đỏ, tồn tại một đường thẳng đồng thời chia đôi tập các điểm đỏ và tập các điểm xanh, nghĩa là số điểm đỏ nằm ở hai phía của đường thẳng là như nhau và tương tự với các điểm xanh.

Trong trường hợp đặc biệt khi có các điểm nằm trên đường thẳng được chọn, "chia đôi" được hiểu là ở mỗi phía của đường thẳng có không quá một nửa số điểm. Trường hợp đặc biệt này là cần thiết chẳng hạn khi tất cả các điểm thẳng hàng và tất cả các điểm đỏ nằm ở một phía của đường thẳng và các điểm xanh nằm ở phía kia. Có thể xây dựng ví dụ sao cho số điểm ở hai phía không bằng nhau bằng cách thêm một điểm không nằm trên đường thẳng trong ví dụ trên.

Trong hình học tính toán, định lý bánh mì dăm bông dẫn tới bài toán bánh mì dăm bông. Trong không gian hai chiều, bài toán phát biểu như sau: cho n điểm trên mặt phẳng, mỗi điểm tô màu xanh hoặc đỏ, tìm một lát cắt bánh mì dăm bông. Đầu tiên, Megiddo (1985) mô tả thuật toán cho một trường hợp đặc biệt khi các điểm được tách rời, nghĩa là, có một đường thẳng sao cho mọi điểm đỏ nằm ở một phía và mọi điểm xanh nằm ở phía kia. Thuật toán của Megiddo giải quyết trường hợp này trong thời gian tuyến tính. Sau đó, Edelsbrunner & Waupotitsch (1986) đưa ra một thuật toán cho trường hợp tổng quát trong hai chiều chạy trong thời gian O(n log n), trong đó O là Ký hiệu O lớn. Cuối cùng, Lo & Steiger (1990) tìm ra một thuật toán tối ưu chạy trong thời gian O(n). Thuật toán này được mở rộng ra không gian nhiều chiều bởi Lo, Matoušek & Steiger (1994). Cho d tập hợp điểm ở vị trí tổng quát trong không gian d chiều, thuật toán tìm ra một siêu phẳng (d−1) chiều sao cho số lượng điểm của mỗi tập hợp ở hai phía của siêu phẳng là như nhau.

Tham khảo

• Beyer, W. A.; Zardecki, Andrew (2004), “The early history of the ham sandwich theorem”, American Mathematical Monthly, 111 (1): 58–61, doi:10.2307/4145019, JSTOR 4145019.
• Edelsbrunner, H.; Waupotitsch, R. (1986), “Computing a ham sandwich cut in two dimensions”, J. Symbolic Comput., 2: 171–178, doi:10.1016/S0747-7171(86)80020-7.
• Lo, Chi-Yuan; Steiger, W. L. (1990), “An optimal time algorithm for ham-sandwich cuts in the plane”, Proceedings of the Second Canadian Conference on Computational Geometry, tr. 5–9.
• Lo, Chi-Yuan; Matoušek, Jiří; Steiger, William L. (1994), “Algorithms for Ham-Sandwich Cuts”, Discrete and Computational Geometry, 11: 433–452, doi:10.1007/BF02574017.
• Megiddo, Nimrod (1985), “Partitioning with two lines in the plane”, Journal of Algorithms, 6: 430–433, doi:10.1016/0196-6774(85)90011-2.
• Steinhaus, Hugo (1938), “A note on the ham sandwich theorem”, Mathesis Polska, 9: 26–28.
• Stone, A. H.; Tukey, J. W. (1942), “Generalized "sandwich" theorems”, Duke Mathematical Journal, 9: 356–359, doi:10.1215/S0012-7094-42-00925-6.

Tham khảo

Liên kết ngoài

• Weisstein, Eric W., "Ham Sandwich Theorem" từ MathWorld. (tiếng Anh)
• ham sandwich theorem trên trang Earliest known uses of some of the words of mathematics (tiếng Anh)
• Ham Sandwich Cuts bởi Danielle MacNevin (tiếng Anh)
• Minh họa tương tác trong không gian 2 chiều (tiếng Anh)