Loading AI tools
Quebra-cabeça lógico Da Wikipédia, a enciclopédia livre
O quebra-cabeça dos quatro copos, também conhecido como o problema do garçom cego[1] é um quebra-cabeça lógico primeiramente divulgado por Martin Gardner na sua coluna "Jogos Matemáticos" ("Mathematical Games") na edição de fevereiro de 1979 da revista Scientific American.[2]
Quatro cálices ou copos são colocados nos cantos de uma mesa com bandeja giratória quadrada do tipo Lazy Susan. Alguns dos copos estão virados para baixo e outros virados para cima. Uma pessoa de olhos vendados está sentada ao lado da mesa e é necessário re-organizar os copos de modo que eles fiquem todos para cima ou para baixo, um ou outro arranjo sendo aceitável, que será assinalado ao cego pelo toque de uma campainha. Os copos podem ser re-arranjados em turnos sujeitos às regras a seguir. Quaisquer dois copos podem ser inspecionados uma vez e depois de sentir a sua orientação, a pessoa pode inverter a orientação de um deles, nenhum deles ou ambos. Depois de cada turno a mesa Lazy Susan é rotacionada por um ângulo aleatório. O desafio do quebra-cabeça é conceber um algoritmo que permita que a pessoa de olhos vendados possa garantir que todos os copos têm a mesma orientação (para cima ou para baixo) em um número finito de rotações. O algoritmo deve ser não estocástico, isto é, não deve depender da sorte.[3]
Um algoritmo que garante que a campainha vai tocar no máximo em cinco voltas é o seguinte:[2]
O quebra-cabeça pode ser generalizado para n copos em vez de quatro. Para dois copos é trivialmente resolvido em um turno, invertendo um dos copos. Para três copos existe um algoritmo de dois turnos. Para cinco ou mais copos não existe um algoritmo que garanta que a campainha vai tocar em um número finito de turnos[2] .
Uma outra generalização permite ainda que k copos (em vez de dois) de um grupo de n copos sejam examinados em cada turno. Um algoritmo pode ser encontrado para que a campainha toque em um número finito de turnos ao longo de k ≥ (1 − 1/p)n onde p é o maior fator primo de n[2] .
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.