21. Решение
а) Сплетня, известная одной из бабушек, после 1-го часа станет
известна не более, чем двум (включая первого), после второго
часа — не более, чем четырем, ..., после 5-го часа — не более,
чем 32. Итак, потребуется не менее 6 часов. Покажем, что 6 часов
достаточно. Переговоры можно вести по следующей схеме.
Занумеруем бабушек шестизначными двоичными числами. В k-й час
беседуют старушки, номера которых отличаются только в k-м
разряде (например в 3-й час abc0de беседует с abc1de). При этом
каждый час количество сплетен, известных каждой, удваивается.
(Например, после 2-го часа каждая знает 4 сплетни, известные 4
бабушкам с номерами, отличающимися от её номера в двух первых
разрядах.)
Замечание. Этот способ переговоров годится только для степеней
двойки. Ниже изложен метод, который годится для любых четных
чисел.
в) То, что 6 часов мало, видно из а). Покажем, что 7 часов
достаточно. Занумеруем бабушек элементами из Z50 × {–1, 1}. В
1-й час бабушка с номером (x, y) беседует с (x, –y), во 2-й — с
(x + 1, –y), в 3-й — с (x + 3, –y), в 4-й — с (x + 7, –y), в 5-й
— с (x + 15, –y), в 6-й — с (x + 31, –y), в 7-й — с (x + 63,
–y). При этом количество сплетен у каждой из бабушек каждый час
(кроме последнего) удваивается. (Занумеруем сплетни так же, как
бабушек, знающих их в начале. После 1-го часа бабушка с номером
(0, 0) знает все сплетни с x = 0, после 2-го — все сплетни с x =
0, 1, после 3-го — все сплетни с x = 0, 1, 2, 3; и т. д.)
б) В первый час одна из бабушек ни с кем не беседует. Как видно
из а), остальным, чтобы узнать её сплетню, потребуется еще не
меньше 6 часов.
Разделим бабушек на две группы: 32 и 23 человека. В 1-й час все
члены второй группы беседуют с членами первой. За следующие 5
часов члены первой группы обмениваются сплетнями (по схеме из а)
или из в); в результате каждый знает все сплетни). В последний
час они сообщают всю информацию членам второй группы.
Ответ: а) 6 часов, б) 7 часов, в) 7 часов.
|