МАЛЫЙ МЕХМАТ МГУ

Кружок 8 класса

Занятие 13 (8 февраля 2014 года). Алгоритмы

1.

В тюрьме Кощея пять камер, пронумерованных числами от 1 до 5. В каждой камере сидит по одному узнику. Василиса уговорила Кощея провести эксперимент: на стене каждой камеры она один раз напишет какой-нибудь номер и в полночь каждый узник перейдёт в камеру с указанным номером (если номер на стене совпадает с номером камеры, то узник никуда не переходит). В следующую полночь узники опять должны перейти из камеры в камеру согласно указаниям на стене, и так они действуют в течение пяти ночей. Если расположение узников в камерах в течение всех шести дней (включая первый) ни разу не повторится, то Василисе дадут звание Премудрой, а узников отпустят. Помогите Василисе написать номера в камерах.

2.

Фокусник выкладывает 36 карт в 6 столбцов по 6 карт и просит Зрителя мысленно выбрать карту и запомнить столбец, ее содержаший. После этого Фокусник определенным образом собирает карты, снова выкладывает в виде квадрата 6×6 и просит Зрителя назвать номера столбцов, содержащих выбранную карту в первый и второй раз. После ответа Зрителя Фокусник безошибочно отгадывает карту. Как действовать Фокуснику, чтобы фокус гарантированно удался?

3.

Есть доска 3×3. В некоторой клетке стоит заяц. Охотник выбирает любые две клетки, на которые заяц не сможет пойти. За один ход заяц перебегает на любую разрешенную соседнюю по стороне клетку. Если заяц не сможет сделать ход, он проиграет. Может ли Охотник выиграть, если он увидит зайца только в тот момент, когда тому некуда пойти?

4.

В темнице сидит 100 узников, каждый в одиночной камере (общение между камерами невозможно). Король предложил узникам сыграть в игру. Для этого в специальной комнате повесили лампочку с выключателем (только два положения вкл/выкл). Лампочка изначально выключена. В эту комнату по одному заводят узников и предлагают им сделать одно из двух действий: поменять положение выключателя или ничего не сделать. Если в какой-то момент один из узников вдруг скажет фразу «В этой комнате побывали все 100 узников» и это окажется правдой, то всех отпускают, если нет — то казнят. Смогут ли узники выйти на волю, если им за день до игры предоставлена возможность всем вместе пообщаться и выработать стратегию? (Считается что узников водят в произвольном порядке, сколь угодно долго и каждый узник побывает в камере сколь угодно много раз).

5.

На плоскости расположены 100 точек-овец и одна точка-волк. За один ход волк передвигается на расстояние не больше 1, после этого одна из овец передвигается на расстояние не больше 1, после этого снова ходит волк и т. д. При любом ли начальном расположении точек волк сможет поймать одну из овец?

6.

Переаттестация Совета Мудрецов из 1000 мудрецов происходит так: король выстраивает их в колонну по одному и надевает на голову каждому колпак белого или черного цвета. Каждый мудрец видит цвета колпаков всех впереди стоящих мудрецов, но не видит цвет своего колпака и цвета колпаков мудрецов, стоящих сзади него. Затем мудрецы по одному называют какой-нибудь цвет (каждому разрешается говорить ровно один раз; то, что говорит один мудрец, слышат все). После этого король казнит всех мудрецов, назвавших цвет, отличный от цвета своего колпака. Накануне переаттестации все члены Совета договорились между собой и придумали, как минимизировать число казненных. Скольким из них гарантированно удастся избежать казни?

7.

По кругу стоит 101 мудрец. Каждый из них либо считает, что Земля вращается вокруг Юпитера, либо считает, что Юпитер вращается вокруг Земли. Один раз в минуту все мудрецы одновременно оглашают свои мнения. Сразу после этого каждый мудрец, оба соседа которого думают иначе, чем он, меняет своё мнение, а остальные — не меняют. Докажите, что через некоторое время мнения перестанут меняться.