Hispanopedia WikiEl procedimiento de cuchillos móviles de Stromquist es un método para cortar un pastel sin envidia entre tres jugadores. Recibe su nombre de Walter Stromquist, quien lo presentó en 1980. [ 1 ]
Este procedimiento fue el primer método de cuchillo móvil sin envidia diseñado para tres jugadores. Requiere cuatro cuchillos, pero solo dos cortes, por lo que cada jugador recibe una sola pieza conectada. No existe 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 de Stromquist
Versión más sencilla
En una versión más sencilla del problema, una división se considera "justa" si todos los participantes están satisfechos de haber recibido al menos 1/n (donde n = 3) del pastel. Para esta versión, existe una solución simple y práctica, atribuida por Steinhaus [ 3 ] a Banach y Knaster.
Procedimiento para la versión más sencilla
Un árbitro mueve una espada de izquierda a derecha sobre el pastel, dividiéndolo hipotéticamente en una pequeña pieza izquierda y una pieza grande derecha. Cada jugador mueve un cuchillo sobre la pieza derecha, manteniéndolo siempre paralelo a la espada. Los jugadores deben mover sus cuchillos de forma continua, sin hacer ningún "salto". [ 4 ] Cuando un jugador grita "cortar", el pastel es cortado por la espada y por el cuchillo de los jugadores que resulte ser el central de los tres (es decir, el segundo en orden desde la espada). Luego, el pastel se divide de la siguiente manera:
- La pieza situada a la izquierda de la espada, a la que denominamos Izquierda , se le entrega al jugador que primero gritó "¡Corta!". A este jugador lo llamamos "el que grita" y a los otros dos, "los que callan".
- La pieza que se encuentra entre la espada y el cuchillo central, a la que denominamos "Medio" , se entrega al jugador restante cuyo cuchillo esté más cerca de la espada.
- La pieza restante, la derecha , se entrega al tercer jugador.
Estrategia
Cada jugador puede actuar de manera que garantice que, según su propio criterio, reciba al menos un tercio del pastel.
- Siempre sostenga el cuchillo de manera que divida la parte a la derecha de la espada en dos trozos 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 a medida que la espada se mueve hacia la derecha).
- Grita "cortar" cuando Izquierda sea igual a la pieza que estás a punto de recibir si permaneces en silencio (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 tu cuchillo está en el centro, grita "cortar" si Izquierda=Medio=Derecha).
Análisis
Ahora demostramos que cualquier jugador que utilice la estrategia anterior recibe al menos un tercio del pastel.
Primero, consideremos a la persona que grita. Ella grita cuando, según su criterio, izquierda = centro = derecha. Por lo tanto, la porción que recibe es exactamente un tercio del pastel, según su perspectiva.
Ahora consideremos a los dos más tranquilos. Como permanecieron tranquilos, no envidian al que grita, es decir, el trozo de pastel restante (después de regalar el trozo de la izquierda) es más grande que dos tercios del pastel.
Ahora bien, como dividen el pastel restante en 2 partes iguales, cada una de las partes equivale a un tercio o más del pastel, según sus respectivas valoraciones.
La porción que reciben contiene necesariamente sus cuchillos, es decir, es igual o más grande que la porción que habrían cortado, que de todos modos era igual o más grande que un tercio del pastel.
Por lo tanto, cada agente recibe al menos un tercio del pastel según sus respectivas valoraciones.
Los empates pueden resolverse arbitrariamente y el mismo análisis seguirá siendo válido.
Dividir 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. [ 5 ] : ejercicio 5.11
Véase también
- El procedimiento de corte de pastel de Fair proporciona una solución más sencilla al mismo problema, utilizando solo 3 cuchillos giratorios, cuando el pastel es un círculo unidimensional ("pastel"),
- El procedimiento de cuchillo giratorio de Robertson-Webb proporciona una solución aún más sencilla, utilizando solo un cuchillo giratorio, cuando el pastel es bidimensional.
- Procedimiento de movimiento del cuchillo
- Martin Gardner describe el caso n = 3 (versión más simple) en su libro [ 6 ].
Referencias
- ↑ Stromquist, Walter (1980). "Cómo cortar un pastel de manera 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 reparto de pasteles a la resolución de disputas . Cambridge University Press. ISBN 0-521-55644-9.
- ^ Steinhaus, H. (julio de 1949). "Sobre la división pragmática" . Econométrica . 17 : 315– 319. doi : 10.2307/1907319 . ISSN 0012-9682 . JSTOR 1907319 .
- ↑ La importancia de esta continuidad se explica aquí: "Procedimiento de los 3 cuchillos de Stromquist" . Math Overflow . Consultado el 14 de septiembre de 2014 .
- ↑ 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 .
- ^ Austin, AK (junio de 1979). "¡Ajá! Insight, de Martin Gardner. Pp. viii, 179. £4. 1978. SBN 0 89454 001 7 (Freeman)" . La Gaceta Matemática . 63 (424): 130– 131. doi : 10.2307/3616029 . ISSN 0025-5572 . JSTOR 3616029 .
- protocolos de reparto equitativo
- Corte de pastel