|
|
 |
Условие
N друзей одновременно узнали N новостей, причём каждый узнал одну
новость. Они стали звонить друг другу и обмениваться новостями.
Каждый разговор длится 1 час. За один разговор можно передать сколько угодно новостей.
Какое минимальное количество часов необходимо, чтобы все узнали все новости?
Рассмотрите три случая:
а) N = 64,
б) N = 55,
в) N = 100.
Решение
а) Новость, известная одному из друзей, после 1-го часа станет известна не более чем двум (включая первого), после второго часа – не более чем четырём, ..., после 5-го часа – не более чем 32. Итак, потребуется не менее 6 часов.
Покажем, что 6 часов достаточно. Переговоры можно вести по следующей схеме. Занумеруем участников шестизначными двоичными числами. В k-й час беседуют люди, номера которых отличаются только в k-м разряде (например в 3-й час abc0de беседует с abc1de). При этом каждый час количество новостей, известных каждому, удваивается. (Например, после 2-го часа каждый знает четыре новости, известные четырём участникам с номерами, отличающимися от его номера в двух первых разрядах.)
Замечание. Этот способ переговоров годится только для степеней двойки. Ниже изложен метод, который годится для любых чётных чисел.
в) То, что 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 часов.
Замечания
1. Z50 – группа вычетов по модулю 50.
2. Аналогично задача решается для произвольного N (см. решения Задачника "Кванта").
3. Баллы: 5 + 7 + 12.
