ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 32062
Темы:    [ Процессы и операции ]
[ Разбиения на пары и группы; биекции ]
Сложность: 2
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

В компании из k человек (k > 3) у каждого появилась новость, известная ему одному. За один телефонный разговор двое сообщают друг другу все известные им новости. Докажите, что за 2k – 4 разговора все они могут узнать все новости.


Решение

Передача информации может быть осуществлена следующим образом. Рассмотрим некоторых четверых людей в компании — назовем их A, B, C, D. Пусть сначала все члены компании, кроме B, C и D звонят A и сообщают ему свои новости. Это потребует k – 4 звонка. Затем между собой говорят A и B, а также C и D. После этого A говорит с C, а B с D, в результате чего все четверо будут знать все новости. За оставшиеся 2n – 4 звонка A сообщает их всем остальным.

Замечания

Источник решения: книга "В.О.Бугаенко. Турниры им. Ломоносова. Конкурсы по математике. МЦНМО-ЧеРо. 1998".

Источники и прецеденты использования

олимпиада
Название Турнир им.Ломоносова
год/номер
Номер 09
Дата 1986
задача
Номер 04

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .