火腿三明治定理

命名

当 n=3 时，就像一个三明治一样——这里的三个“物体”则是两片面包和中间的火腿。用一个平面可以同时把三个“物体”截断。

二维版本的证明：“旋转刀片”

二维版本的证明比任意维度的证明较为简单，流程如下：

对任何角度 α ∈ [0,π ]，均存在一条与 X 轴成角度 α 的直线平分第一个物体。（需使用介值定理）

令 α 由 0 增加到 π，再使用介值定理，则存在一条直线同时平分第二个物体。

定理的离散版本

离散版本可以视为定理的特例，当中每一个＂物体＂都是用有限个点组成的集合，并使用计数测度。但需要考虑点刚好落左超平面上时的情况。

In mathematical measure theory, for every positive integer n the ham sandwich theorem states that given n measurable "objects" in n-dimensional Euclidean space, it is possible to divide each one of them in half (with respect to their measure, e.g. volume) with a single (n − 1)-dimensional hyperplane. This is possible even if the objects overlap.

It was proposed by Hugo Steinhaus and proved by Stefan Banach (explicitly in dimension 3, without stating the theorem in the n-dimensional case), and also years later called the Stone–Tukey theorem after Arthur H. Stone and John Tukey.

Naming

The ham sandwich theorem takes its name from the case when n = 3 and the three objects to be bisected are the ingredients of a ham sandwich. Sources differ on whether these three ingredients are two slices of bread and a piece of ham (Peters 1981), bread and cheese and ham (Cairns 1963), or bread and butter and ham (Dubins & Spanier 1961). In two dimensions, the theorem is known as the pancake theorem to refer to the flat nature of the two objects to be bisected by a line (Cairns 1963).

History

According to Beyer & Zardecki (2004), the earliest known paper about the ham sandwich theorem, specifically the n = 3 case of bisecting three solids with a plane, is a 1938 note in a Polish mathematics journal (Editors 1938). Beyer and Zardecki's paper includes a translation of this note, which attributes the posing of the problem to Hugo Steinhaus, and credits Stefan Banach as the first to solve the problem, by a reduction to the Borsuk–Ulam theorem.

Two-dimensional variant: proof using a rotating-knife

The two-dimensional variant of the theorem (also known as the pancake theorem) can be proved by an argument which appears in the fair cake-cutting literature (see e.g. Robertson–Webb rotating-knife procedure).

For each angle α ∈ [0,180^(∘)], a straight line ("knife") of angle α can bisect pancake #1. To see this, translate along its normal a straight line of angle α from -∞ ∞; the fraction of pancake #1 covered by the line changes continuously from 0 to 1, so by the intermediate value theorem it must be equal to 1/2 somewhere along the way.

n-dimensional variant: proof using the Borsuk–Ulam theorem

The ham sandwich theorem can be proved as follows using the Borsuk–Ulam theorem. This proof follows the one described by Steinhaus and others (1938), attributed there to Stefan Banach, for the n = 3 case. In the field of Equivariant topology, this proof would fall under the configuration-space/tests-map paradigm.

Let A1, A2,..., An denote the n compact (or more generally bounded and Lebesgue-measurable) subsets of R ⁿ that we wish to simultaneously bisect. Let （公式略） be the unit (n − 1)-sphere in R ⁿ.

Measure theoretic versions

In measure theory, Stone & Tukey (1942) proved two more general forms of the ham sandwich theorem. Both versions concern the bisection of n subsets X1, X2,..., Xn of a common set X, where X has a Carathéodory outer measure and each Xi has finite outer measure.

Their first general formulation is as follows: for any continuous real function f: Sⁿ× X→ R, there is a point p of the n-sphere Sn and a real number s0 such that the surface f(p,x) = s0 divides X into f(p,x) < s0 and f(p,x) > s0 of equal measure and simultaneously bisects the outer measure of X1, X2,..., Xn.

Discrete and computational geometry versions

In discrete geometry, the ham sandwich theorem usually refers to the special case in which each of the sets being divided is a finite set of points. Here the relevant measure is the counting measure, which simply counts the number of points on either side of the hyperplane. In two dimensions, the theorem can be stated as follows:

Generalization to algebraic surfaces

The original theorem works for at most n collections, where n is the number of dimensions. To bisect a larger number of collections without going to higher dimensions, one can use, instead of a hyperplane, an algebraic surface of degree k, i.e., an (n−1)–dimensional surface defined by a polynomial function of degree k:

Given （公式略） measures in an n–dimensional space, there exists an algebraic surface of degree k which bisects them all. (Smith & Wormald (1998)).