Procedimientos de traslado con cuchillo en Austin

El procedimiento de la cuchilla móvil de Austin es un procedimiento para la división equitativa de un pastel . A cada uno de los n socios se le asigna una porción del pastel que este socio valora como exactamente igual a su valor real. $1/n$ del pastel. Esto contrasta con los procedimientos de división proporcional , que dan a cada socio al menos $1/n$ del pastel, pero puede dar más a algunos de los socios.

Cuando $n=2$ La división generada por el procedimiento de Austin es una división exacta y, además, está libre de envidia . Es posible dividir el pastel en cualquier número k de porciones que ambos socios valoren exactamente como 1/ k . Por lo tanto, es posible dividir el pastel entre los socios en cualquier fracción (por ejemplo, darle 1/3 a Alice y 2/3 a George).

Cuando $n>2$ , la división no es ni exacta ni libre de envidia, ya que cada socio solo valora su propia parte como $1/n$ pero puede que valoren otras piezas de manera diferente.

La principal herramienta matemática utilizada por el procedimiento de Austin es el teorema del valor intermedio (TVI). ^{[ 1 ]}^{[ 2 ]}^{[ 3 ]}^{: 66}

Dos socios y medias tartas

Los procedimientos básicos implican $n=2$ Parejas que desean dividir un pastel de manera que cada una reciba exactamente la mitad.

Procedimiento con dos cuchillos

Para efectos de la descripción, llamemos a los dos jugadores Alice y George, y supongamos que el pastel es rectangular.

Alice coloca un cuchillo a la izquierda del pastel y un segundo, paralelo a él, a la derecha, donde calcula que parte el pastel en dos.
Alicia mueve ambos cuchillos hacia la derecha de tal manera que la parte que queda entre ellos siempre contiene, a sus ojos, la mitad del valor del pastel (aunque la distancia física entre los cuchillos puede variar).
George grita "¡Alto!" cuando cree que la mitad del pastel está entre los cuchillos. Podemos estar seguros de que George se detendría en algún momento, ya que si Alice llega al final, su cuchillo izquierdo debe estar en la misma posición que el derecho. El Teorema del Valor Interno establece que George debe estar convencido de que el pastel está partido por la mitad en algún punto.
Se lanza una moneda al aire para elegir entre dos opciones: o George recibe la pieza que está entre los cuchillos y Alice recibe las dos piezas de los flancos, o viceversa. Si los participantes dicen la verdad, coinciden en que la pieza entre los cuchillos vale exactamente 1/2, por lo que la división es exacta.

Procedimiento con un solo cuchillo

Se puede utilizar un solo cuchillo para lograr el mismo efecto.

Alice gira el cuchillo sobre el pastel 180°, dejando la mitad a cada lado.
George dice "¡Alto!" cuando está de acuerdo.

Por supuesto, Alice debe terminar el turno con el cuchillo en la misma línea donde comenzó. De nuevo, según el Teorema del Valor Intermedio, debe haber un punto en el que George sienta que las dos mitades son iguales.

Dos socios y fracciones generales

Como señaló Austin, los dos socios pueden encontrar un solo trozo de pastel que ambos valoran como exactamente $1/k$ , para cualquier número entero $k\geq 2$ . ^{[ 2 ]} Llamar al procedimiento anterior $\mathrm {Cortar} _ {2}(1/k)$ :

Alicia hace $k-1$ marcas paralelas en el pastel de tal manera que $k$ piezas así determinadas tienen un valor exacto $1/k$ .
Si hay una pieza que George también valora como $1/k$ , entonces hemos terminado.
De lo contrario, debe haber una pieza que George valora como menos que $1/k$ y una pieza adyacente que George valora como más que $1/k$ .
Deja que Alice coloque dos cuchillos sobre las dos marcas de una de estas piezas y los mueva en paralelo, manteniendo el valor entre ellos exactamente igual a 1. $1/k$ hasta que coincidan con las marcas de la otra pieza. Según el IVT, debe haber un punto en el que George esté de acuerdo en que el valor entre los cuchillos es exactamente $1/k$ .

Mediante la aplicación recursiva $\mathrm {Cortar} _ {2}$ , los dos socios pueden dividir todo el pastel en $k$ piezas, cada una de las cuales vale exactamente $1/k$ para ambos: ^{[ 2 ]}

Usar $\mathrm {Cortar} _ {2}(1/k)$ cortar un trozo que vale exactamente $1/k$ para ambos socios.
Ahora el pastel restante vale exactamente $(k-1)/k$ para ambos socios; usar $\mathrm {Cortar} _ {2}(1/(k-1))$ cortar otro trozo que valga exactamente $1/k$ para ambos socios.
Continúe así hasta que haya $k$ piezas.

Dos socios pueden lograr una división exacta con cualquier proporción racional de derechos mediante un procedimiento ligeramente más complicado. ^{[ 3 ]}^{: 71}

Muchos socios

Al combinar $\mathrm {Cortar} _ {2}$ Con el protocolo Fink , es posible dividir un pastel en $n$ socios, de manera que cada socio reciba una pieza que valga exactamente $1/n$ para él: ^{[ 1 ]}^{[ 4 ]}

Los socios n.° 1 y n.° 2 utilizan $\mathrm {Cortar} _ {2}(1/2)$ para darles a cada uno de ellos una pieza que valiera exactamente 1/2 para ellos.
El socio n.° 3 utiliza $\mathrm {Cortar} _ {2}(1/3)$ con el socio n.° 1 para obtener exactamente 1/3 de su parte y luego $\mathrm {Cortar} _ {2}(1/3)$ con la socia n.° 2 para obtener exactamente 1/3 de su parte. La primera pieza vale exactamente 1/6 para la socia n.° 1, por lo que la socia n.° 1 se queda con exactamente 1/3; lo mismo ocurre con la socia n.° 2. En cuanto a la socia n.° 3, aunque cada pieza puede ser mayor o menor que 1/6, la suma de las dos piezas debe ser exactamente 1/3 del pastel entero.

Tenga en cuenta que para $n>2$ , la división generada no es exacta, ya que una pieza vale $1/n$ solo a su propietario y no necesariamente a los demás socios. A partir de 2015, no se conoce ningún procedimiento exacto de división para $n>2$ socios; solo se conocen procedimientos de división casi exactos .

Véase también

El procedimiento de Austin es utilizado por el procedimiento de Brams-Taylor-Zwicker .
Otros procedimientos y resultados sobre división equitativa y división exacta .

Referencias

1 2 Austin, AK (1982). "Compartiendo un pastel". The Mathematical Gazette . 66 (437): 212– 215. doi : 10.2307/3616548 . JSTOR 3616548 . S2CID 158398839 .
1 2 3 Brams, Steven J.; Taylor, Alan D. (1996). División justa [ De la división de bienes a la resolución de disputas ] . págs. 22–27 . ISBN 978-0-521-55644-6.
1 2 Robertson, Jack; Webb, William (1998). Algoritmos para el reparto de pasteles: Sea justo si puede . Natick, Massachusetts: AK Peters. ISBN 978-1-56881-076-8. LCCN 97041258 . OL 2730675W .
↑ Brams, Steven J.; Taylor, Alan D. División justa [ De la división de bienes a la resolución de disputas ] . págs. 43–44 . ISBN 978-0-521-55644-6.

Enlaces externos

Fischer, Daniel. "División consensuada de un pastel entre dos personas en proporciones arbitrarias" . Math.SE. Consultado el 23 de junio de 2015 .

[austin-1] 1 2 Austin, AK (1982). "Compartiendo un pastel". The Mathematical Gazette . 66 (437): 212– 215. doi : 10.2307/3616548 . JSTOR 3616548 . S2CID 158398839 .

[bramstaylor-2] 1 2 3 Brams, Steven J.; Taylor, Alan D. (1996). División justa [ De la división de bienes a la resolución de disputas ] . págs. 22–27 . ISBN 978-0-521-55644-6.

[rw98-3] 1 2 Robertson, Jack; Webb, William (1998). Algoritmos para el reparto de pasteles: Sea justo si puede . Natick, Massachusetts: AK Peters. ISBN 978-1-56881-076-8. LCCN 97041258 . OL 2730675W .

[bramstaylor43-4] Brams, Steven J.; Taylor, Alan D. División justa [ De la división de bienes a la resolución de disputas ] . págs. 43–44 . ISBN 978-0-521-55644-6.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]