На вращающемся квадратном столе стоят четыре стакана, по стакану на каждом из углов стола. Некоторые из стаканов перевёрнуты вверх дном.
У вас завязаны глаза. Вы не знаете, какие стаканы стоят вверх дном, а какие - вниз дном. Необходимо перевернуть все стаканы либо вниз дном, либо все вверх дном, но:
- можно взять в руки любые два стакана;
- взяв стаканы, вы можете перевернуть один или два стакана, или, не переворачивая ни один, поставить стаканы на место;
- после того, как вы поставили стаканы на место, стол поворачивается на произвольное число оборотов, так что вы уже не знаете где какой стакан;
- в момент, когда все стаканы оказались перевёрнуты в одну сторону, вам сообщат об этом.
Придумайте алгоритм, который гарантированно позволит вам перевернуть все стаканы вниз дном или все стаканы вверх дном. Решение должно работать за конечное число ходов.
Ответ:
Будем брать либо соседние стаканы (те, которые находятся ближе к вам), либо диагональные (слева ближе к вам, справа дальше от вас).
- Берём два соседних стакана, переворачиваем их вверх дном, ставим на место.
- Берём два диагональных стакана, поворачиваем вверх дном.
- Берём два диагональных стакана. Если хотя бы один стакан повёрнут вниз дном, переворачиваем один стакан вверх дном. Иначе, переворачиваем любой стакан вниз дном.
- Берём два соседних стакана, переворачиваем их оба.
- Берём два стакана по диагонали, переворачиваем оба.
Причём, на любом шаге может оказаться, что задача решена.
Ответ...