햄 샌드위치 정리

수학의 측도론에서, 모든 양의 정수 n에 대해 **햄 샌드위치 정리**(ham sandwich theorem)는 n-차원 유클리드 공간에 있는 n개의 가측 "객체"가 주어졌을 때, 하나의 (n − 1)-차원 초평면으로 각각의 객체를 절반(해당 측도, 예를 들어 부피에 따라)으로 나눌 수 있다고 말한다. 이 객체들이 겹쳐 있어도 이것은 가능하다. 이 정리는 후고 스테인하우스에 의해 제안되었고 스테판 바나흐에 의해 증명되었으며 (명시적으로 3차원인 경우에, n-차원인 경우는 언급하지 않았다), 수년 후 아서 H. 스톤과 존 투키의 이름을 따서 **스톤-투키 정리**라고도 불렸다.
# 이름
햄 샌드위치 햄 샌드위치 정리는 1=n = 3일 때 세 개의 이등분될 객체가 햄 샌드위치의 재료일 경우에서 이름이 유래했다. 이 세 가지 재료가 빵 두 조각과 햄 한 조각인지 1981, 빵과 치즈와 햄인지 1963, 아니면 빵과 버터와 햄인지 1961에 대해서는 출처마다 다르다. 2차원에서 이 정리는 두 개의 객체가 선에 의해 이등분되는 평평한 성질을 나타내기 위해 **팬케이크 정리**로 알려져 있다 1963.
# 역사
2004에 따르면, 햄 샌드위치 정리에 대한 가장 초기의 알려진 논문은, 특히 평면으로 세 개의 입체를 이등분하는 1=n = 3의 경우에 대해, 1938년 폴란드 수학 저널의 한 노트이다 1938. 바이어와 자르데키의 논문은 이 노트의 번역을 포함하고 있으며, 문제의 제기를 후고 스테인하우스에게, 문제 해결을 스테판 바나흐에게 돌리는데, 이는 보르수크-울람 정리로의 환원을 통해 이루어졌다. 이 노트는 문제를 두 가지 방식으로 제기한다: 첫째, 공식적으로 "임의로 위치한 세 개의 입체를 적절한 평면을 사용하여 항상 이등분할 수 있는가?" 그리고 둘째, 비공식적으로 "고기 자르는 기계 아래에 햄 조각을 놓아 고기, 뼈, 지방이 절반으로 잘리도록 할 수 있는가?" 이 노트는 이어서 정리의 증명을 제시한다. 더 현대적인 참고 자료는 1942인데, 이는 "스톤-투키 정리"라는 이름의 근거가 된다. 이 논문은 측도를 포함하는 더 일반적인 설정에서 정리의 n-차원 버전을 증명한다. 이 논문은 심사위원의 정보를 바탕으로 1=n = 3의 경우를 스타니스와프 울람에게 귀속시키지만, 2004는 위에서 언급된 노트를 고려할 때 이것이 부정확하다고 주장한다. 비록 "울람이 보르수크-울람 정리를 제안하는 데 근본적인 기여를 했지만" 말이다.
# 2차원 변형: 회전하는 칼을 이용한 증명
서로 인접하지 않은 영역에 대한 2차원 햄 샌드위치 정리 예시: 5° 간격의 선이 비슷한 색의 영역(분홍색 햄과 녹색 야채)을 두 개의 동일한 면적으로 이등분하며, 검은 선은 두 영역의 공통 이등분선을 나타낸다. 정리의 2차원 변형 (**팬케이크 정리**라고도 알려짐)은 케이크 공평하게 자르기 문헌에 나타나는 논증(예: Robertson–Webb rotating-knife procedure)으로 증명될 수 있다. 각도 \alpha\in[0,180^\circ]에 대해, 각도 \alpha를 가진 직선("칼")은 팬케이크 #1을 이등분할 수 있다. 이를 확인하려면, 각도 \alpha를 가진 직선을 -\infty에서 \infty까지 그 법선을 따라 이동시킨다. 직선으로 덮인 팬케이크 #1의 비율은 0에서 1로 연속적으로 변하므로, 중간값 정리에 의해 어느 지점에서는 1/2이 되어야 한다. 우리 선의 전체 번역 범위가 1/2의 비율을 산출할 수 있으며; 이 경우, 그러한 모든 번역 중 가운데 것을 선택하는 것이 표준적인 선택이다. 칼이 0도 각도에 있을 때, 팬케이크 #2도 자르지만 조각들은 아마도 같지 않을 것이다 (운 좋게 조각들이 같으면, 끝난 것이다). 칼의 '양의' 쪽을 팬케이크 #2의 비율이 더 큰 쪽으로 정의한다. 이제 칼을 돌리고 위에서 설명한 대로 이동시킨다. 각도가 \alpha일 때, p(\alpha)를 칼의 양의 쪽에 있는 팬케이크 #2의 비율로 정의한다. 처음에는 p(0) > 1/2이다. 각도의 작은 변화가 칼의 위치에 작은 변화를 가져오므로, 함수 p는 연속이다. 칼이 180도 각도에 있을 때, 칼은 거꾸로 되어 있으므로 p(180) c\\}를 E_{v,c}의 "양의 측면"이라고 부르며, 이는 벡터 v가 가리키는 측면이다. 중간값 정리에 의해, 그러한 초평면의 모든 계열은 유계 집합 An을 이등분하는 적어도 하나의 초평면을 포함한다. 한 극단적인 이동에서는 An의 부피가 양의 측면에 전혀 없고, 다른 극단적인 이동에서는 An의 모든 부피가 양의 측면에 있으므로, 그 사이에는 c\in\mathbb{R}의 가능한 값들의 닫힌 구간 Iv이 존재해야 하며, 이 구간에 대해 E_{v,c}는 An의 부피를 이등분한다. 만약 An의 부피가 0이라면, 모든 v\in S에 대해 c=0을 선택한다. 그렇지 않으면, 구간 Iv은 콤팩트하고, 각 v\in S에 대해 c=\frac12(\inf I_v+\sup I_v)를 그 중점으로 정규적으로 선택할 수 있다. 따라서 우리는 구 S의 각 점 v에 대해 초평면 E_{v,\alpha(v)}가 An을 이등분하도록 하는 연속 함수 \alpha\colon S\to\mathbb{R}를 얻는다. 또한, 모든 v\in S에 대해 I_{-v}=-I_v이고 따라서 \alpha(-v)=-\alpha(v)임을 주목한다. 이제 함수 f\colon S\to\mathbb{R}^{n-1}을 다음과 같이 정의한다: :f(v)=(vol(A_1\cap E^+_{v,\alpha(v)}),\ldots,vol(A_{n-1}\cap E^+_{v,\alpha(v)})). 이 함수 f는 연속이다 (지배 수렴 정리로 증명될 수 있다). 보르수크-울람 정리에 의해, 구 S에는 f(v)=f(-v)인 대척점 v와 -v가 존재한다. 대척점은 초평면 E_{v,\alpha(v)}와 E_{-v,\alpha(-v)}=E_{-v,-\alpha(v)}에 해당하며, 이들은 양의 측면이 반대라는 점을 제외하고는 같다. 따라서, f(v)=f(-v)는 i=1,\ldots,n에 대해 Ai의 부피가 E_{v,\alpha(v)}의 양의 측면과 음의 측면에서 동일하다는 것을 의미한다. 그러므로 E_{v,\alpha(v)}는 A1, ..., An의 부피를 동시에 이등분하는 원하는 햄 샌드위치 절단이다.
# 측도론적 버전
측도론에서, 1942는 햄 샌드위치 정리의 두 가지 더 일반적인 형태를 증명했다. 두 버전 모두 공통 집합 X의 n개의 부분집합 X1, X2, ..., Xn을 이등분하는 것에 관한 것이며, 여기서 X는 카라테오도리 외측도를 가지며 각 Xi는 유한한 외측도를 가진다. 그들의 첫 번째 일반적인 공식화는 다음과 같다: 임의의 연속 실함수 f \colon S^n \times X \to \mathbb{R}에 대해, n-초구 Sn의 점 p와 실수 s0가 존재하여 표면 1=f(p,x) = s0가 X를 f(p,x) s0로 동일한 측도를 가지도록 나누고 동시에 X1, X2, ..., Xn의 외측도를 이등분한다. 증명은 다시 보르수크-울람 정리로의 환원이다. 이 정리는 1=f(s,x) = s1x1 \+ ... + snxn을 설정함으로써 표준 햄 샌드위치 정리를 일반화한다. 그들의 두 번째 공식화는 다음과 같다: X에 대한 n + 1개의 가측 함수 f0, f1, ..., fn가 양의 측도를 갖는 모든 부분집합에 대해 선형 독립이라면, 선형 결합 1=f = a0f0 \+ a1f1 \+ ... + anfn이 존재하여 표면 1=f(x) = 0이 X를 f(x) 0으로 나누면서 동시에 X1, X2, ..., Xn의 외측도를 이등분한다. 이 정리는 1=f0(x) = 1과 i > 0에 대해 fi(x)를 x의 i-번째 좌표로 설정함으로써 표준 햄 샌드위치 정리를 일반화한다.
# 이산 기하 및 계산 기하 버전
평면에서 여덟 개의 빨간 점과 일곱 개의 파란 점을 자르는 햄 샌드위치 절단 이산기하학에서 햄 샌드위치 정리는 일반적으로 나누어지는 각 집합이 점들의 유한 집합인 특수한 경우를 의미한다. 여기서 관련 측도는 셈측도이며, 이는 단순히 초평면의 양쪽에 있는 점의 수를 센다. 2차원에서 이 정리는 다음과 같이 표현될 수 있다: :평면에서 "빨간색" 또는 "파란색"으로 색칠된 유한한 점들의 집합에 대해, 빨간색 점들을 동시에 이등분하고 파란색 점들을 동시에 이등분하는 선이 존재한다. 즉, 선의 양쪽에 있는 빨간색 점의 수는 동일하고 파란색 점의 수도 동일하다. 점이 선 위에 놓이는 예외적인 경우가 있다. 이 상황에서는 각 점을 선의 한쪽, 다른 쪽 또는 어느 쪽에도 없는 것으로 간주한다 (점마다 다를 수 있음). 즉, "이등분"은 실제로 각 측면에 전체 점 수의 절반 미만이 포함된다는 의미이다. 이 예외적인 경우는 정리의 성립을 위해 실제로 필요하며, 물론 빨간색 점이나 파란색 점의 수가 홀수일 때뿐만 아니라, 점의 수가 짝수일 때도 특정 구성에서 필요하다. 예를 들어 모든 점이 같은 선 위에 있고 두 색깔이 서로 분리되어 있을 때 (즉, 선을 따라 색깔이 교차하지 않을 때) 그렇다. 각 측면의 점의 수가 서로 일치할 수 없는 상황은 이전 구성에서 선 밖에 추가 점을 추가함으로써 발생한다. 계산기하학에서 이 햄 샌드위치 정리는 계산 문제인 **햄 샌드위치 문제**로 이어진다. 2차원에서 이 문제는 다음과 같다: 평면에서 각각 "빨간색" 또는 "파란색"으로 색칠된 n개의 유한한 점 집합이 주어졌을 때, 이들을 위한 햄 샌드위치 절단을 찾는 것이다. 먼저, 1985는 특별한 분리된 경우에 대한 알고리즘을 설명했다. 여기서 모든 빨간색 점은 어떤 선의 한쪽에 있고 모든 파란색 점은 다른 쪽에 있는데, 이러한 상황에서는 유일한 햄 샌드위치 절단이 존재하며, 메기도는 이를 선형 시간 내에 찾을 수 있었다. 나중에, 1986는 일반적인 2차원 경우에 대한 알고리즘을 제시했다. 그들의 알고리즘의 실행 시간은 O(n log n)이며, 여기서 기호 O는 점근 표기법의 사용을 나타낸다. 마지막으로, 1990는 최적의 O(n) 시간 알고리즘을 발견했다. 이 알고리즘은 1994에 의해 더 높은 차원으로 확장되었으며, 여기서 실행 시간은 o(n^{d-1})이다. d-차원 공간에서 일반 위치에 있는 d개의 점 집합이 주어졌을 때, 이 알고리즘은 각 집합의 점들이 반공간 모두에 같은 수를 갖는 (d−1)-차원 초평면, 즉 주어진 점들에 대한 햄 샌드위치 절단을 계산한다. 만약 d가 입력의 일부라면, 다항 시간 알고리즘이 존재할 것으로 예상되지 않는다. 왜냐하면 점들이 모멘트 곡선 위에 있다면, 문제는 목걸이 분할 문제와 동등해지며, 이는 PPA-완전이다. 서로 다른 두 개의 볼록 다각형의 면적을 이등분하는 선형 시간 알고리즘은 1991에 의해 설명된다.
# 대수곡면으로의 일반화
원래의 정리는 최대 n개의 모음에 대해 작동하는데, 여기서 n은 차원의 수이다. 더 많은 수의 모음을 더 높은 차원으로 가지 않고 이등분하려면, 초평면 대신 k차 대수곡면을 사용할 수 있다. 즉, k차 다항 함수로 정의된 (n−1)차원 곡면을 사용하는 것이다. n차원 공간에 \binom{k+n}{n}-1개의 측도가 주어졌을 때, 이들 모두를 이등분하는 k차 대수곡면이 존재한다. (1998). 이 일반화는 n차원 평면을 \binom{k+n}{n}-1차원 평면으로 매핑한 다음, 원래의 정리를 적용하여 증명된다. 예를 들어, 1=n = 2이고 1=k = 2일 때, 2차원 평면은 다음을 통해 5차원 평면으로 매핑된다: :(x, y) → (x, y, x2, y2, xy).