PDF-версии: 
K бабушек одновременно узнали K сплетен, причём каждая из них узнала только одну сплетню. Бабушки принялись обмениваться сплетнями по телефону. Каждый разговор занимает 1 час, в течение которого можно передать сколько угодно сплетен. Какое минимальное количество часов разговора нужно, чтобы все бабушки узнали все сплетни, если:
а) K = 64,
б) K = 55,
в) K = 100.
Решение. а) Сплетня, известная одной из бабушек, после 1-го часа станет известна не более, чем двум (включая первую), после второго часа — не более, чем четырем, ..., после 5-го часа — не более, чем 32м бабушкам. Итак, потребуется не менее 6 часов. Покажем, что 6 часов достаточно. Переговоры можно вести по следующей схеме. Занумеруем бабушек шестизначными двоичными числами. В k-й час беседуют старушки, номера которых отличаются только в k-м разряде (например в 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 часов.
| Критерии оценивания выполнения задания | Баллы |
|---|---|
| Верно получены все перечисленные (см. критерий на 1 балл) результаты. | 4 |
| Верно получены три из перечисленных (см. критерий на 1 балл) результатов. | 3 |
| Верно получены два из перечисленных (см. критерий на 1 балл) результатов. | 2 |
| Верно получен один из следующих результатов: — пример в п. а; — обоснованное решение п. б; — обоснование в п. в того, что S может принимать все целые значения (отличные от −1 и 1); — обоснование в п. в того, что равенства S = −1 и S = 1 невозможны. | 1 |
| Решение не соответствует ни одному из критериев, перечисленных выше. | 0 |
| Максимальный балл | 4 |