브람스-테일러 절차

브램스–테일러 시술(BTP)은 시샘 없는 케이크 커팅을 위한 시술이다.그것은 어떤 양의 정수 선수들 사이에서 케이크에 대한 부러움이 없는 분배를 만들어내기 위한 최초의 유한한 절차를 설명했다.^[1]

역사

1988년 BTP의 발견에 앞서 솔 가펑클은 정리, 즉 n인칭 시샘 없는 케이크 커팅으로 해결된 문제가 20세기 수학에서 가장 중요한 문제 중 하나라고 주장했다.^[2]

BTP는 Steven Brams와 Alan D에 의해 발견되었다. 테일러1995년 1월호 《American Mathemical Monthly》에 처음 발표되었고,^[3] 이후 1996년 저자들의 저서에 발표되었다.^[4]

Brams와 Taylor는 BTP와 관련하여 1999년부터 미국 공동 특허를 보유하고 있다.^[5]

설명

BTP는 케이크를 부분별로 나눈다.BTP의 대표적인 중간 상태는 다음과 같다.

• 케이크의 일부인 $X{\displaystyle }$ ${\displaystyle X}$은$($는) 모든 파트너에게 부러움이 없는 방식으로 나누어진다.
• $나머지{\displaystyle }$ 케이크는 Y {\$displaystyle Y}$라고 하지만 $-$
• 앨리스라고 하는 한 파트너는 $Y{\displaystyle }$ ${\displaystyle Y}$에 대해 밥은 다른 파트너에 비해 돌이킬 수 없는 우위(IA)를 가지고 있다고 말한다$.$ $이$는 Y ${\displaysty$ Y$}$이(가) 어떻게 나누어져$$ 있든 상관없이 $우리$가 Y ${\\\displaysty Y$}를 밥에게 전적으로$$ 주더라도 앨리스는 여전히 밥이 부러워하지 않는다는 것을 의미한다.

IA 생성 방법의 예로서 Selfridge-Conway 이산형 절차의 첫 번째 단계를 고려하십시오.

• 앨리스는 케이크를 그녀가 동등하다고 생각하는 세 부분으로 나누었다; 그 부분을 $A{\displaystyle ,}$ B$, C$라고 부르자$.$
• 밥은 자신이 가장 크다고 생각하는 부분($예{\displaystyle }$: A ${\displaystyle A$을 두 번째로 큰 부분과 같게 다듬는다. 자른 $부분$을 Y ${\displaystyle Y}$와 $A{\displaystyle }$ ${\displaystyle \setminus }$ ${\displaystyle Y}$ ${\displaystyle A\setminus$ Y$}$라고 부르자$.$
• $찰리$는${\displaystyle }$(${\displaystyle A}$ ${\displaystyle \setminus }$ ${\displaystyle Y}$)${\displaystyle }$, B${\displaystyle }$, ${\displaystyle C}$, C {\$displaystyle ($A\setminus $Y), B,$C} 중에서 한 조각을 선택하고$,$ 그리고 나서 밥은${\displaystyle }$(${\displaystyle Ay}$Y )$${\$displaystyle (A\setminus$ Y$)$을 선택해야 한다. 그리고 마지막으로 앨리스.

이 단계가 끝나면 $Y{\displaystyle }$ ${\displaystyle Y}$를 제외한 모든 케이크가 부러움$$ 없이 나눠진다.게다가, 앨리스는 이제 누가${\displaystyle }$(${\displaystyle Ay}$Y $){\displaystyle (A\setminus$ Y$)}}$을(를) 가져간 사람보다 IA를 가지고 있다$.$ 왜? 앨리스가 $B{\displaystyle }$ ${\displaystyle B}$ $또는$ C ${\displaysty C}$를 가져갔기 때문이며$,$ 둘 다 $그녀$의 의견으로는$$ A ${\displaystystystystystystystytytystytylean A}$과 같다.따라서 앨리스의 의견에 따르면$,{\displaystyle }$ 누가 (${\displaystyle Ay}$Y $){\displaystyle (A\setminus$ Y$)}$을 가져간 사람도 $Y{\displaystyle }$ ${\displaystyle Y}$를 가질 수 있는데$$,$$ 이것은 앨리스의 부러움을 사지 않을 것이다.

앨리스가 특정 선수(예: 밥)에 대해 IA를 맞도록 하려면 훨씬 더 복잡한 절차가 필요하다.그것은 케이크를 계속해서 더 작고 더 작은 조각으로 나누어 앨리스에게 항상 그녀가 밥보다 더 가치 있는 조각을 주어 IA가 유지되도록 한다.이것은 앨리스와 밥의 정확한 가치에 따라 무한한 시간이 걸릴 수 있다.

IA 절차를 사용하여 기본 BTP 절차는 주문된 모든 파트너 쌍에 대해 IA를 생성한다.예를 들어, 4개의 파트너가 있을 때, 12개의 주문된 파트너 쌍이 있다.그러한 각 쌍(X,Y)에 대해, 우리는 파트너 X가 파트너 Y에 대해 IA를 갖도록 보장하는 하위 절차를 실행한다.모든 파트너가 다른 파트너에 대해 IA를 갖게 되면, 우리는 나머지 부분을 임의의 파트너에게 줄 수 있고, 그 결과는 케이크 전체를 부러워하지 않는 분할이 된다.

참고 항목

• Brams-Taylor-Zwicker 절차 – 제한된 수의 절단을 사용하는 4개 파트너를 위한 이동 나이프 절차.
• 부러움이 없는 케이크 커팅 – 동일한 문제에 대한 더 오래되고 새로운 절차.
• 조정된 우승자 절차 – Brams와 Taylor가 두 대리점 간의 상품 분배의 유사하지만 뚜렷한 문제를 해결하도록 설계된 절차.

참조