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

Проект МЦНМО
при участии
школы 57
Задача 105089
Темы:    [ Математическая логика (прочее) ]
[ Криптография ]
[ Деление с остатком ]
Сложность: 5-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Из колоды вынули семь карт, показали всем, перетасовали и раздали Грише и Лёше по три карты, а оставшуюся карту
  а) спрятали;
  б) отдали Коле.
Гриша и Лёша могут по очереди сообщать вслух любую информацию о своих картах. Могут ли они сообщить друг другу свои карты так, чтобы при этом Коля не смог вычислить местонахождение ни одной из тех карт, которых он не видит? (Гриша и Лёша не договаривались о каком-либо особом способе общения; все переговоры происходят открытым текстом.)


Решение

  а) Пусть Гриша скажет: "У меня либо {называет свои карты}, либо {называет три карты, которых у него нет}". После этого Лёша должен сказать: "У меня либо {называет свои карты}, либо {называет три карты Гриши, если второй из наборов, названных Гришей, не совпадает с его набором, и любые другие три карты, которых у него нет, иначе}". После этого каждый из них, очевидно, знает весь расклад. Коле же ничего не ясно. Действительно, названо три набора карт: A, B и C. Наборы B и C пересекаются по двум картам, Гриша сказал: "У меня либо A, либо B", Лёша сказал: "У меня либо A, либо C". Это означает, что либо у Гриши набор A, а у Лёши – C, либо у Гриши – B, а у Лёши – A. Конечно, эти расклады различны, и даже закрытую карту определить нельзя.

  б) Заметим, что предыдущий способ не работает: зная закрытую карту, Коля может всё определить.

  Первый способ. Занумеруем карты числами от 0 до 6. Пусть Гриша и Лёша по очереди назовут остатки от деления суммы номеров своих карт на 7. Тогда они узнают расклад: каждый из них должен лишь прибавить к своей сумме сумму другого и найти остаток, противоположный этой общей сумме по модулю 7. Это и будет номер закрытой карты. После этого восстановление расклада не составляет труда.
  Проверим, что Коля ничего не узнал. Рассмотрим карту с номером s. Покажем, что она могла попасть к Грише, если он назвал сумму a. Для этого надо дополнить эту карту двумя другими с суммой номеров  a – s.  Легко видеть, что существует три различные пары номеров, дающие в сумме  a – s.  Из них две, возможно, испорчены тем, что туда входит карта с номером s или закрытая карта, но как минимум одна пара остаётся. Ей мы и дополним набор Гриши. Такие же рассуждения показывают, что любая карта могла оказаться и у Лёши.

  Второй способ. Гриша строит конечную проективную плоскость порядка 2 (см. рис.) так, чтобы одной из её прямых была его тройка карт (остальные шесть прямых пересекаются с этой тройкой ровно по одной карте). То есть сообщает "у меня одна из семи следующих троек карт ...".

  Получив эту информацию, Леша сразу понимает, какая именно прямая у Гриши: так как на любой из шести прочих прямых карта Коли является не более чем одной из точек, а карта Гриши – ровно одной из точек, то на каждой из этих шести прямых есть карта Леши, и эту тройку он может исключить из рассмотрения. После этого он говорит вслух, какая именно карта у Коли.
  Коля может исключить те три прямые, которые содержат его карту, но остальные четыре прямые с его точки зрения равноправны, а каждая из шести остальных точек на какой-то из этих прямых не лежит. Поэтому никакой дополнительной информации о расположении карт он не получает.


Ответ

Могут.

Замечания

Конечная проективная плоскость порядка 2 состоит из семи точек и семи прямых (одна из них на рисунке изображена как окружность). На каждой прямой по три точки, каждые две прямые пересекаются ровно по одной точке.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 63
Год 2000
вариант
Класс 10
задача
Номер 6

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

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