И. В. Раскина Логика для всех: от пиратов до мудрецов Издание третье, стереотипное
жүктеу/скачать 1.3 Mb. Pdf көрінісі
|
| Ответ. 1 или 3.
Д44. 1) Занумеруем карты от 0 до 6. Можно считать, что у Гриши карты 1, 2 и 3. Пусть он скажет: «У меня либо набор 1, 2, 3, либо набор 4, 5, 6». Поскольку у Ле- ши на руках как минимум две карты из набора 4, 5, 6, он понимает, что у Гриши набор 1, 2, 3, и знает, какая кар- та спрятана. Теперь Леша должен сообщить Грише свои карты. Возможны два случая. 1. У Леши набор 4, 5, 6 (а спрятана карта 0). Леша говорит: «У меня либо набор 4, 5, 6, либо 1, 2, 0». 2. У Леши другой набор, скажем, 4, 5, 0 (а спрятана карта 6). Леша говорит: «У меня либо набор 4, 5, 0, либо 1, 2, 3». 162 В обоих случаях названный Лешей «не свой» набор пе- ресекается с Гришиным как минимум по двум картам, по- этому Гриша тоже узнает, какой на самом деле набор у Леши. Докажем, что Коле ничего не ясно. Действительно, и в том, и в другом случае названо три набора карт: A, B и C. Наборы B и C пересекаются по двум картам, Гриша сказал: «У меня либо A, либо B», Леша сказал: «У меня либо A, либо C». Это означает, что либо у Гриши набор A, а у Леши — C, либо у Гриши — B, а у Леши — A. Поэтому три карты из набора A и две карты из пересечения набо- ров B и C могут оказаться как у Гриши, так и у Леши (в нашем примере это карты 1, 2, 3, 4 и 5). А из остальных двух карт наборов B и C (в нашем примере 6 и 0) одна закрытая, другая — у одного из игроков. Поэтому место- положение никакой из карт Коля вычислить не может. 2) Заметим, что предыдущий способ не работает: зная закрытую карту, Коля может всё определить. Пусть Гриша занумерует карты числами от 0 до 6 (и объявит об этом вслух). Затем пусть Гриша и Леша по очереди назовут остатки от деления суммы номеров своих карт на 7. Тогда они узнают расклад: ведь остаток сум- мы Гриши плюс остаток суммы Леши плюс номер спря- танной карты должны давать 0 + 1 + 2 + 3 + 4 + 5 + 6 = 0 (mod 7). Так, например, если у Леши карты 1, 3, 4, а Гри- ша назвал остаток 4, то спрятана карта −4 − (1 + 3 + 4) = 2 (mod 7), значит, у Гриши карты 0, 5, 6. Проверим, что Коля ничего не узнал. Его информация исчерпывается Гришиной суммой g и Колиной картой k (а Лешину сумму теперь Коля и сам может вычислить). Рассмотрим любую другую карту, пусть ее номер x. Пока- жем, что она входит в какой-нибудь набор из трех карт с суммой g, не содержащий k. Для этого дополним x парой карт с суммой номеров g − x. Таких пар ровно три при лю- бом значении g − x (доказательство см. ниже). Из них две, возможно, не подходят из-за того, что туда входит карта с номером s или k, но как минимум одна пара остается. С ее 163 помощью мы и создадим набор для Гриши (а набор для Леши получится автоматически). Например, если x = 3, то в нашем случае при g = 4 надо найти пару с суммой 4 − 3 = 1. Таких пар три: 1 = 0 + 1 = 2 + 6 = 3 + 5 (mod 7). Из них подходит только {0, 1}, то есть у Гриши мог быть набор 0, 1, 3. Итак, любая карта могла оказаться у Гриши. Такие же рассуждения показывают, что любая карта могла оказать- ся и у Леши. Поэтому местоположение никакой из карт Коля вычислить не может. Осталось доказать, что неупорядоченных пар с нужной суммой s всегда три. Есть семь упорядоченных пар (0, s), (1, s − 1), ff, (6, s − 6). Из них ровно в одной оба остат- ка одинаковы, поскольку уравнение 2x = s имеет, ввиду взаимной простоты чисел 2 и 7, ровно одно решение. Из неупорядоченной пары с разными остатками получается ровно две упорядоченных, поэтому неупорядоченных пар вдвое меньше, чем упорядоченных, то есть ровно 3. жүктеу/скачать 1.3 Mb. Достарыңызбен бөлісу:
|