stringtranslate.com

Procedimiento de cuchilla giratoria de Robertson-Webb

El procedimiento de cuchilla giratoria de Robertson-Webb es un procedimiento para cortar sin envidia un pastel bidimensional entre tres socios. [1] : 77–78  Hace solo dos cortes, por lo que cada socio recibe una única pieza conectada.

Su principal ventaja sobre el procedimiento anterior de cuchillas móviles de Stromquist y el posterior procedimiento de cuchillas móviles de Barbanel-Brams es que requiere una sola cuchilla móvil. Esta ventaja aprovecha la naturaleza bidimensional del pastel.

Procedimiento

Inicialmente, cada compañero hace un corte vertical de modo que el pastel de su izquierda valga exactamente 1/3 para él. Se selecciona el corte más a la izquierda. Supongamos que este corte pertenece a Alice. Entonces Alice recibe la pieza más a la izquierda y su valor es exactamente 1/3. El resto debe dividirse entre los socios restantes (Bob y Carl).

Tenga en cuenta que la parte de Alice vale como máximo 1/3 y el resto vale al menos 2/3 para Bob y Carl. Entonces, si Bob y Carl reciben cada uno al menos la mitad del resto, no tienen envidia. El desafío es asegurarse de que Alice no envidiará a ninguno de ellos.

La solución se basa en la siguiente observación: Para cada ángulo , Alice puede poner un cuchillo en el ángulo y cortar el resto en dos mitades iguales a sus ojos . Esto significa que Alice puede girar un cuchillo sobre el resto de manera que las partes de los dos lados del cuchillo sean siempre iguales ante sus ojos.

Cuando el cuchillo está en el ángulo 0, Bob (débilmente) prefiere la pieza que está encima del cuchillo o la pieza que está debajo del cuchillo; cuando el cuchillo está en un ángulo de 180, las piezas se invierten. Por lo tanto, según el teorema del valor intermedio , debe haber un ángulo en el que Bob piense que las piezas de ambos lados del cuchillo son iguales. En este ángulo, Bob grita "¡alto!". Se corta el pastel, Carl elige un trozo y Bob recibe el otro trozo.

Análisis

Alicia no tiene envidia porque para ella las tres piezas valen exactamente 1/3.

Bob y Carl no envidian a Alice porque su pieza vale como máximo 1/3 y la suya al menos (1/2)*(2/3) = 1/3.

Bob no envidia a Carl porque sus piezas son iguales a sus ojos; Carl no envidia a Bob porque eligió la mejor pieza ante sus ojos.

Dividiendo un pastel 'malo'

El procedimiento de cuchilla giratoria se puede adaptar para la división de tareas domésticas : dividir un pastel con un valor negativo: [1] : ejercicio 5.10  en el paso inicial, se debe seleccionar el corte más a la derecha , en lugar del corte más a la izquierda.

Ver también

Referencias

  1. ^ ab Robertson, Jack; Webb, William (1998). "Algoritmos para cortar pasteles: sea justo si puede" . Natick, Massachusetts: AK Peters. ISBN 978-1-56881-076-8. LCCN  97041258. OL  2730675W.