Problema de los cuatro vasos

El problema de los cuatro vasos [1] es un acertijo lógico de Martin Gardner . Publicado en la columna "Math Games" de la edición de febrero de 1979 de Scientific American .

Redacción

Cuatro vasos están ubicados en las esquinas de una mesa giratoria cuadrada. Algunos vasos están colocados (es decir, correctamente) y otros están boca abajo (es decir, al revés). Una persona con los ojos vendados debe reacomodar los anteojos para que estén todos en la misma posición, en cuyo caso sonará la campana. Los vasos se pueden reorganizar uno por uno de acuerdo con las siguientes reglas. Se pueden comprobar dos vasos cualesquiera en un solo movimiento y, al detectar su orientación, una persona puede cambiar la orientación de cualquiera de ellos, de ninguno de los vasos o de ambos. Después de cada rotación, la mesa gira en un ángulo aleatorio. El desafío es desarrollar un algoritmo que permita a una persona con los ojos vendados verificar que todos los anteojos tienen la misma orientación (hacia arriba o hacia abajo) en un número finito de rotaciones. El algoritmo debe ser no estocástico, es decir, no debe depender de la suerte. [2]

Solución

El algoritmo que garantiza que la campana sonará después de no más de cinco revoluciones es el siguiente: [3]

  1. En el primer turno, seleccione el par de anteojos opuestos en diagonal y gire ambos anteojos boca abajo.
  2. En el segundo turno, seleccione dos vasos adyacentes. Al menos uno de ellos se levanta como resultado del paso anterior. Si el otro está caído, dale la vuelta también. Si la campana no suena, ahora hay tres vasos arriba y uno abajo.
  3. En el tercer turno, seleccione el par de anteojos opuestos en diagonal. Si uno de ellos está caído, dale la vuelta y sonará la campana. Si ambos están arriba, voltea uno. Ahora se colocan dos vasos y se paran uno al lado del otro.
  4. En el cuarto turno, seleccione dos vasos adyacentes y voltee ambos. Si ambos estuvieran en la misma orientación, sonaría la campana. De lo contrario, ahora los dos vasos están boca abajo y deben estar diagonalmente separados uno del otro.
  5. En el quinto giro, selecciona el par de gafas opuesto en diagonal y voltea ambos. La campana sonará.

Generalizaciones

El rompecabezas se puede generalizar a n vasos en lugar de cuatro. Para dos copas, esto se resuelve trivialmente en un solo movimiento volteando cualquiera de las copas. Para tres vasos, hay un algoritmo en dos vueltas. Para cinco o más vasos, no existe un algoritmo que garantice que la campana sonará en un número finito de revoluciones. [cuatro]

Una generalización adicional le permite verificar k tazas (en lugar de dos) de n tazas en cada turno. Es posible encontrar un algoritmo que resuelva el problema en un número finito de vueltas si k ≥ (1 − 1/ p ) n , donde p es el mayor factor primo de n . [cuatro]

Notas

  1. ↑ Ehrenborg, Richard (1995). “El problema del cantinero ciego” (PDF) . Revista de Teoría Combinatoria, Serie A. 70 (2): 249 y ndash, 266. DOI : 10.1016/0097-3165(95)90092-6 . Archivado (PDF) desde el original el 13 de agosto de 2021 . Consultado el 14 de noviembre de 2021 . Parámetro obsoleto utilizado |deadlink=( ayuda )
  2. ↑ Braingle » Rompecabezas 'Cuatro vasos' . Consultado el 14 de noviembre de 2021. Archivado desde el original el 14 de noviembre de 2021.
  3. ↑ Havil, Julián. Capítulo 4: El giro de una mesa // ¡Perplejo! . - Prensa de la Universidad de Princeton, 2007. - ISBN 978-0-691-12056-0 . Havil, Julián (2007). "Capítulo 4: El giro de una mesa".
  4. ↑ 1 2 Havil, Julián. Capítulo 4: El giro de una mesa // ¡Perplejo! . - Prensa de la Universidad de Princeton, 2007. - ISBN 978-0-691-12056-0 . Havil, Julián (2007). "Capítulo 4: El giro de una mesa". desconcertado! . Prensa de la Universidad de Princeton. ISBN 978-0-691-12056-0.