Question

Каждый из 20 человек знает ровно одну новость, причём все новости различны. Они передают по телефону эти новости друг другу, причём когда Х звонит Y, он рассказывает Y все новости, которые он к этому времени знает, но Y при этом звонке ничего не рассказывает Х. Какое наименьшее количество звонков необходимо, чтобы все услышали все эти 20 новостей?

Answer 1

Ответ:

Всего 38 звонков

Объяснение:

Всего 20 человек, у каждого 1 личная новость.

Очевидно, что 1й звонок распространит 1 новость. Следовательно, у кого-то их станет 2 (рассказанная и своя).

Поедлагаю такой алгоритм:

Для того, чтобы все 20 новостей стали известны кому-то одному, нужно

20 - 1 = 19 звонков.

(19 звонков - потому что надо передать всего 19 новостей; одна "своя" новость в счет звонков не войдет).

Однако после 19 звонков все новости полностью известны только одному человеку. А значит, 19ти - неизвестны.

Этт значит, что необходимо совершить ещё 19 звонков (т.к. 1 звонок "обогащает" новостями только 1го человека).

Итого, всего звонков необходимо:

19 + 19 = 38

Где первые 19 звонков - "накопительная" фаза, а последующие 19 - "распространяющая" фаза.

Answer 2

1) 20*20 = 400

2) 400 - 20 = 380

Answer 3

Для того чтобы все 20 человек услышали все 20 новостей, достаточно 19 звонков.

Пояснение:

1. Первый человек (назовем его A) может позвонить любому из оставшихся 19 человек и рассказать ему свою новость. На этом этапе у одного человека есть одна новость, а у остальных - ничего.

2. Далее второй человек (назовем его B) звонит любому из оставшихся 18 человек (включая A) и рассказывает ему свою новость, а также новость, которую он услышал от A. Теперь у B две новости, а у остальных - по одной.

3. Продолжаем этот процесс, пока все не услышат все новости.

Итак, сначала A делает 1 звонок, затем B делает 1 звонок, C - 1 звонок и так далее. Общее количество звонков будет равно 1 + 1 + 1 + ... + 1 (19 раз) = 19 звонков.