Đị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 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 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à
Đị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 và một số người khác, trong đó trường hợp đặc biệt đã được chứng minh bởi Stefan Banach.
Đặt 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 formula_1, 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 : nếu tịnh tiến siêu phẳng vô hạn về một hướng, toàn bộ 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ộ nằm ở nửa âm, nên tồn tại một phép tịnh tiến sao cho độ đo của ở 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 đó đượ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 vuông góc với vectơ từ gốc tọa độ tới "p" và chia đôi .
Định nghĩa hàm "f" từ mặt cầu chiều "S" tới không gian Euclid chiều formula_2 như sau:
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 . Hai điểm đối cực "p" và "q" tương ứng với hai siêu phẳng và bằng nhau nhưng có nửa dương ngược nhau. Do đó, nghĩa là có cùng độ đo trên nửa dương và nửa âm của (hay ), với mọi . Vì vậy (hay ) là lát cắt cần tìm để chia đôi .
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:
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 đ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, 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 đó, đư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 , trong đó là Ký hiệu O lớn. Cuối cùng, tìm ra một thuật toán tối ưu chạy trong thời gian . Thuật toán này được mở rộng ra không gian nhiều chiều bởi . Cho tập hợp điểm ở vị trí tổng quát trong không gian chiều, thuật toán tìm ra một siêu phẳng 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.