Đị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à

 một miếng dăm bông,
 một lát pho mát, và
 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  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 , 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  như sau:
độ đo của  trên nửa dương của , độ đo của  trên nửa dương của ,..., độ đo của  trên nửa dương của .
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:

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  đ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.

Tham khảo
.
.
.
.
.
.
.

Tham khảo

Liên kết ngoài
  (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)

Định lý trong lý thuyết độ đo
Bánh mì