ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66743
Тема:    [ Кооперативные алгоритмы ]
Сложность: 4
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Автор: Кноп К.А.

Фокусник с помощником показывают фокус. В ряд стоят 13 закрытых пустых шкатулок. Фокусник уходит, а зритель на виду у помощника прячет по монетке в любые две шкатулки по своему выбору. Затем возвращается фокусник. Помощник открывает одну шкатулку, в которой нет монетки. Далее фокусник указывает на 4 шкатулки, и их одновременно открывают. Цель фокусника – открыть обе шкатулки с монетками. Предложите способ, как договориться фокуснику с помощником, чтобы этот фокус всегда удавался.

См. также задачу 66739

Решение

Мысленно расположим шкатулки по кругу, изобразив их точками, делящими окружность на 13 равных дуг длины 1, и будем выражать расстояния между шкатулками в дугах. Между любыми двумя шкатулками с одной из сторон круга находится не более 6 дуг длины 1. Тогда нам достаточно придумать ≪шаблон≫ – четырёхугольник с вершинами в шкатулках, – между вершинами которого реализуются все расстояния от 1 до 6. Пример такого шаблона изображён на рисунке (четырёхугольник с вершинами 1, 2, 5, 7), одна из его вершин помечена красным.

Этот шаблон всегда можно повернуть так, чтобы он ≪накрыл≫ обе шкатулки с монетами. Помощник так и делает, а открывает шкатулку перед красной вершиной шаблона. Фокусник поворачивает шаблон так, чтобы красная вершина шла сразу за шкатулкой, открытой помощником, и находит монеты.

Это же решение можно изложить другими словами. Занумеруем шкатулки остатками по модулю 13. Если помощник открывает шкатулку с номером k, то фокусник открывает шкатулки с номерами k+1, k+2, k+5 и k+7. Поскольку любая пара шкатулок имеет вид {n, n+1}, {n, n+2}, {n, n+3}, {n, n+4}, {n, n+5} или {n, n+6}, то помощник всегда найдёт четвёрку шкатулок нужного вида, содержащую пару шкатулок с монетами.

Для знатоков. Мы описали конечную проективную плоскость над полем $Z_{3}$, где шкатулки выступают в роли точек, а шаблоны — в роли прямых. На этой плоскости как раз 13 точек и 13 прямых, причём на каждой прямой лежит по 4 точки.

Источники и прецеденты использования

олимпиада
Название Турнир городов
номер/год
Дата 2018/19
Номер 40
вариант
Вариант весенний тур, базовый вариант, 10-11 класс
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .