|
|
 |
Условие
Из колоды вынули семь карт, показали всем, перетасовали и раздали Грише и Лёше по три карты, а оставшуюся карту
а) спрятали;
б) отдали Коле.
Гриша и Лёша могут по очереди сообщать вслух любую информацию о своих картах. Могут ли они сообщить друг другу свои карты так, чтобы при этом Коля не смог вычислить местонахождение ни одной из тех карт, которых он не видит? (Гриша
и Лёша не договаривались о каком-либо особом способе общения; все переговоры
происходят открытым текстом.)
Решение
а) Пусть Гриша скажет: "У меня либо {называет свои карты}, либо {называет три карты, которых у него нет}". После этого Лёша должен сказать: "У меня либо {называет свои карты}, либо {называет три карты Гриши, если второй из наборов, названных Гришей, не совпадает с его набором, и любые другие три карты, которых у него нет, иначе}". После этого каждый из них, очевидно, знает весь расклад. Коле же ничего не ясно. Действительно, названо три набора карт: 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 состоит из семи точек и семи прямых (одна из них на рисунке изображена как окружность). На каждой прямой по три точки, каждые две прямые пересекаются ровно по одной точке.
