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

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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. StoneJohn 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độ đ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[sửa | sửa mã nguồn]

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[sửa | sửa mã nguồn]

Đị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 A1, A2, …, Ann đố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 \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 An: nếu tịnh tiến siêu phẳng vô hạn về một hướng, toàn bộ An 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ộ An nằm ở nửa âm, nên tồn tại một phép tịnh tiến sao cho độ đo của An ở 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 đó An đượ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 An.

Đị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 \mathbb{R}^{n-1} như sau:

f(p) = (độ đo của A1 trên nửa dương của π(p), độ đo của A2 trên nửa dương của π(p),..., độ đo của An−1 trên nửa dương của π(p)).

Hàm fliên tục. Theo định lý Borsuk–Ulam, tồn tại hai điểm đối cực pq trên mặt cầu S sao cho f(p) = f(q). Hai điểm đối cực pq tương ứng với hai siêu phẳng π(p)π(q) bằng nhau nhưng có nửa dương ngược nhau. Do đó, f(p) = f(q) nghĩa là Ai 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 A1, A2, …, An.

Phiên bản rời rạc và trong hình học tính toán[sửa | sửa mã nguồn]

Trong hình học rời rạchì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 đó OKí 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.

Tài liệu tham khảo[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]