Quebra-cabeça dos quatro copos

O quebra-cabeça dos quatro copos, também conhecido como o problema do garçom cego é 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.

O quebra-cabeça

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.

Solução

Um algoritmo que garante que a campainha vai tocar no máximo em cinco voltas é o seguinte:

1. No primeiro turno escolher um par na diagonal oposta dos copos e virar estes copos de volta para cima.
2. No segundo turno escolher dois copos adjacente. Pelo menos um deverá estar voltado para cima. Se o outro estiver voltado para baixo, vire-o para cima. Se a campainha não tocou então temos 3 copos virados para cima e um voltado para baixo.
3. No terceiro turno escolher um par de copos diagonalmente opostos. Se um estiver voltado para baixo, vire-o para cima e a campainha irá tocar. Se ambos estiverem para cima vire um para baixo. Agora temos dois copos virados para baixo, e eles devem ser adjacentes.
4. No quarto turno escolher dois copos adjacentes e inverter os dois. Se ambos tiverem a mesma orientação, em seguida, a campainha tocará. Caso contrário, há agora dois copos voltados para baixo e eles devem estar na diagonal oposta.
5. No quinto turno escolher um par de copos diagonalmente opostos e vire os dois. A campainha irá tocar.

Generalizações

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 .

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 .