СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Математика профильного уровня
≡ математика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задания Д16 C7 № 508147

K бабушек одновременно узнали K сплетен, причём каждая из них узнала только одну сплетню. Бабушки принялись обмениваться сплетнями по телефону. Каждый разговор занимает 1 час, в течение которого можно передать сколько угодно сплетен. Какое минимальное количество часов разговора нужно, чтобы все бабушки узнали все сплетни, если:

а) K = 64,

б) K = 55,

в) K = 100.

Решение.

а) Сплетня, известная одной из бабушек, после 1-го часа станет известна не более, чем двум (включая первую), после второго часа — не более, чем четырем, ..., после 5-го часа — не более, чем 32м бабушкам. Итак, потребуется не менее 6 часов. Покажем, что 6 часов достаточно. Переговоры можно вести по следующей схеме. Занумеруем бабушек шестизначными двоичными числами. В -й час беседуют старушки, номера которых отличаются только в -м разряде (например в 3-й час беседует с ). При этом каждый час количество сплетен, известных каждой, удваивается. (Например, после 2-го часа каждая знает 4 сплетни, известные 4 бабушкам с номерами, отличающимися от её номера в двух первых разрядах.)

 

б) В первый час одна из бабушек ни с кем не беседует. Как видно из а), остальным, чтобы узнать её сплетню, потребуется еще не меньше 6 часов. То есть, как минимум, необходимо 7 часов разговора. Разделим бабушек на две группы: 32 и 23 человека. В 1-й час все члены второй группы беседуют с членами первой. За следующие 5 часов члены первой группы обмениваются сплетнями (по схеме из а); в результате каждая бабушка знает все сплетни). В последний час они сообщают всю информацию членам второй группы.

 

в) То, что 6 часов мало, видно из а). Покажем, что 7 часов достаточно. Занумеруем бабушек парами чисел , где y принимает значения 1 и -1, а х - от 0 до 49 (при этом, если x оказывается больше 49, то берем остаток от его деления на 50). В 1-й час бабушка с номером беседует с , во 2-й — с , в 3-й — с , в 4-й — с , в 5-й — с , в 6-й — с , в 7-й — с При этом количество сплетен у каждой из бабушек каждый час (кроме последнего) удваивается. (Занумеруем сплетни так же, как бабушек, знающих их в начале. После 1-го часа бабушка с номером (0, 0) знает все сплетни с , после 2-го — все сплетни с , после 3-го — все сплетни с ; и т. д.)

 

Ответ: а) 6 часов; б) 7 часов; в) 7 часов.

Источник: А. Ларин: Тре­ни­ро­воч­ный ва­ри­ант № 94.
Раздел кодификатора ФИПИ/Решу ЕГЭ: Числа и их свойства