El procedimiento de cuchillos móviles de Stromquist es un procedimiento para cortar pasteles sin envidia entre tres jugadores. Lleva el nombre de Walter Stromquist, quien lo presentó en 1980. [1]
Este procedimiento fue el primer procedimiento de cuchillo móvil sin envidia ideado para tres jugadores. Requiere cuatro cuchillos pero solo dos cortes, por lo que cada jugador recibe una sola pieza conectada. No hay una generalización natural a más de tres jugadores que divida el pastel sin cortes adicionales. La partición resultante no es necesariamente eficiente . [2] : 120–121
Procedimiento
Un árbitro mueve una espada de izquierda a derecha sobre el pastel, dividiéndolo hipotéticamente en una pequeña pieza izquierda y una gran pieza derecha. Cada jugador mueve un cuchillo sobre la pieza correcta, manteniéndola siempre paralela a la espada. Los jugadores deben mover sus cuchillos de forma continua, sin realizar ningún "salto". [3] Cuando cualquier jugador grita "cortar", la torta es cortada por la espada y por cualquiera de los cuchillos de los jugadores que sea el central de los tres (es decir, el segundo en orden de la espada). Luego, el pastel se divide de la siguiente manera:
- La pieza a la izquierda de la espada, que denotamos Izquierda , se entrega al jugador que primero gritó "cortar". A este jugador lo llamamos el "que grita" ya los otros dos jugadores los "más silenciosos".
- La pieza entre la espada y el cuchillo central, que denotamos Medio , se le da al jugador restante cuyo cuchillo está más cerca de la espada.
- La pieza restante, Derecha , se entrega al tercer jugador.
Estrategia
Cada jugador puede actuar de una forma que garantice que, según su propia medida, ningún otro jugador reciba más que ellos:
- Siempre sostenga su cuchillo de manera que divida la parte a la derecha de la espada en dos piezas que sean iguales a sus ojos (por lo tanto, su cuchillo inicialmente divide todo el pastel en dos partes iguales y luego se mueve hacia la derecha mientras la espada se mueve hacia la derecha).
- Grita 'cortar' cuando Izquierda se vuelve igual a la pieza que estás a punto de recibir si te quedas callado (es decir, si tu cuchillo está más a la izquierda, grita 'cortar' si Izquierda = Medio; si tu cuchillo está más a la derecha, grita si Izquierda = Derecha; si su cuchillo está en el centro, grite 'cortar' si Izquierda = Medio = Derecha).
Análisis
Ahora demostramos que cualquier jugador que utilice la estrategia anterior recibe una participación sin envidia.
Primero, considere los dos más silenciosos. Cada uno recibe una pieza que contiene su propio cuchillo, para que no se envidien. Además, debido a que permanecieron en silencio, la pieza que reciben es más grande en sus ojos que Izquierda, por lo que tampoco envidian al que grita.
El que grita recibe Izquierda, que es igual a la pieza que podrían recibir al permanecer en silencio y más grande que la tercera pieza, por lo que el grito no envidia a ninguno de los más silenciosos.
Siguiendo esta estrategia cada persona obtiene la pieza más grande o una de las más grandes por su propia valoración y por lo tanto la división está libre de envidias.
El mismo análisis muestra que la división está libre de envidia incluso en el caso algo degenerado en el que hay dos gritos, y la pieza más a la izquierda se le da a cualquiera de ellos.
Dividiendo un pastel 'malo'
El procedimiento de cuchillos móviles se puede adaptar para la división de tareas : dividir un pastel con un valor negativo. [4] : ejercicio 5.11
Ver también
- El procedimiento de corte de pastel justo proporciona una solución más simple al mismo problema, utilizando solo 3 cuchillos giratorios, cuando el pastel es un círculo unidimensional ("pastel"),
- El procedimiento de cuchilla giratoria de Robertson – Webb proporciona una solución aún más simple, utilizando solo una cuchilla giratoria, cuando la torta es bidimensional.
- Procedimiento de cuchilla móvil
Referencias
- ^ Stromquist, Walter (1980). "Cómo cortar un pastel de forma justa". The American Mathematical Monthly . 87 (8): 640–644. doi : 10.2307 / 2320951 . JSTOR 2320951 .
- ^ Brams, Steven J .; Taylor, Alan D. (1996). División justa: del corte de la torta a la resolución de disputas . Prensa de la Universidad de Cambridge. ISBN 0-521-55644-9.
- ^ La importancia de esta continuidad se explica aquí: "Procedimiento de los 3 cuchillos de Stromquist" . Desbordamiento matemático . Consultado el 14 de septiembre de 2014 .
- ^ 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 .