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

Từ testwiki
Bước tới điều hướng Bước tới 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. 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 Bản mẫu:Math 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 Bản mẫu:Math 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 Bản mẫu:Harvtxt và một số người khác, trong đó trường hợp đặc biệt Bản mẫu:Math đã được chứng minh bởi Stefan Banach.

Đặt Bản mẫu:Math 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 ℝ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 Bản mẫu:Math: nếu tịnh tiến siêu phẳng vô hạn về một hướng, toàn bộ Bản mẫu:Math 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ộ Bản mẫu:Math nằm ở nửa âm, nên tồn tại một phép tịnh tiến sao cho độ đo của Bản mẫu:Math ở 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 đó Bản mẫu:Math đượ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 Bản mẫu:Math vuông góc với vectơ từ gốc tọa độ tới p và chia đôi Bản mẫu:Math.

Định nghĩa hàm f từ mặt cầu Bản mẫu:Math chiều S tới không gian Euclid Bản mẫu:Math chiều ℝn−1 như sau:

Bản mẫu:Mathđộ đo của Bản mẫu:Math trên nửa dương của Bản mẫu:Math, độ đo của Bản mẫu:Math trên nửa dương của Bản mẫu:Math,..., độ đo của Bản mẫu:Math trên nửa dương của Bản mẫu:Math.

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 Bản mẫu:Math. Hai điểm đối cực p và q tương ứng với hai siêu phẳng Bản mẫu:Math và Bản mẫu:Math bằng nhau nhưng có nửa dương ngược nhau. Do đó, Bản mẫu:Math nghĩa là Bản mẫu:Math có cùng độ đo trên nửa dương và nửa âm của Bản mẫu:Math (hay Bản mẫu:Math), với mọi Bản mẫu:Math. Vì vậy Bản mẫu:Math (hay Bản mẫu:Math) là lát cắt cần tìm để chia đôi Bản mẫu:Math.

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 Bản mẫu:Mvar đ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, Bản mẫu:Harvtxt 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 đó, Bản mẫu:Harvtxt đư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 Bản mẫu:Math, trong đó Bản mẫu:Mvar là Ký hiệu O lớn. Cuối cùng, Bản mẫu:Harvtxt tìm ra một thuật toán tối ưu chạy trong thời gian Bản mẫu:Math. Thuật toán này được mở rộng ra không gian nhiều chiều bởi Bản mẫu:Harvtxt. Cho Bản mẫu:Mvar tập hợp điểm ở vị trí tổng quát trong không gian Bản mẫu:Mvar chiều, thuật toán tìm ra một siêu phẳng Bản mẫu:Math 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

Bản mẫu:Tham khảo

Liên kết ngoài

Lấy từ “https://vi.wiki.beta.math.wmflabs.org/w/index.php?title=Định_lý_bánh_mì_dăm_bông&oldid=1554”