Каждый из 20 человек знает ровно одну новость, причём все новости различны.
Они передают по телефону эти новости друг другу, причём когда Х звонит Y, он рассказывает Y все новости, которые он к этому времени знает, но Y при этом звонке ничего не рассказывает Х. Какое наименьшее количество звонков необходимо, чтобы все
услышали все эти 20 новостей?
Ответы
1) 20*20 = 400
2) 400 - 20 = 380
Ответ:
Всего 38 звонков
Объяснение:
Всего 20 человек, у каждого 1 личная новость.
Очевидно, что 1й звонок распространит 1 новость. Следовательно, у кого-то их станет 2 (рассказанная и своя).
Поедлагаю такой алгоритм:
Для того, чтобы все 20 новостей стали известны кому-то одному, нужно
20 - 1 = 19 звонков.
(19 звонков - потому что надо передать всего 19 новостей; одна "своя" новость в счет звонков не войдет).
Однако после 19 звонков все новости полностью известны только одному человеку. А значит, 19ти - неизвестны.
Этт значит, что необходимо совершить ещё 19 звонков (т.к. 1 звонок "обогащает" новостями только 1го человека).
Итого, всего звонков необходимо:
19 + 19 = 38
Где первые 19 звонков - "накопительная" фаза, а последующие 19 - "распространяющая" фаза.