Форум умных людей

N друзей болтунов-говорунов вернулись из отпусков, у каждого полно новостей. За один телефонный звонок пара обменивается новостями полностью, и своими и известными на этот момент чужими. За сколько (минимально) звонков все друзья будут знать все новости других?

N(N-1) звонков.

То есть допустим, если N=3, то звонков надо 6. А не многовато будет?

Ну а одни и те же болтуны могут несколько раз друг другу звонить?

Могут. А смысл? Ведь требуется минимальное количество звонков определить, при которой вся информация разошлась по болтунам.

Ну так, с первого звонка, если один позвонит другому, то они расскажут друг другу только свою информацию, а надо чтобы все от всех ;)

Ну да. Вот и надо определить количество звонков при N говорунах.

Первый друг А звонит двум другим и все уже его знают. А, я не учёл, шо во время разговора тот ещё может и своё рассказать! Ну, тогда N(N-1)/2 звонков.

Я не особо долго расписывал решение, т.е. почти экспромтом ;) :

Показать скрытый текст

Нет.
Неверно.

А не просто N?

Нет.

 У меня так (N-1)+(N-2)

(N+logN) ?

за один звонок.. при N = 2 болтунам..

Илья, попробуй скажи что неверно )

Да, 2N-3.
Это верно.
Это тоже верно.

Почему? При n=4, за 4. При n=6, за 8, а при n=8, за 12.
А по этой формуле получается: n=4, 5. n=6, 9. n=8, 13.

Потому:
1->2, 1->3, 1->4
Осталось еще два звонка, чтобы первый передал инфу второму про 3-го и 4-го, то есть еще один звонок и звонок 3-му, чтобы передать инфу от 4-го 3-му. Всего пять. Четырьмя не обойтись.

А если за один звонок только один может рассказать свои новости другому, сколько потребуется звонков?

 2N-2

Это не самое оптимальное решение.
1 - 2
3 - 4
2 - 3
1 - 4 все.

-

Чего это "неа"? По-моему логично :)

for buka
Ну и в чем я неправ? За эти четыре разговора все узнают обо всех
1 - 2 // 1 знает о 1,2; 2 знает о 1,2
3 - 4 // 3 знает о 3,4; 4 знает о 3,4
2 - 3// 2 знает о 1,2,3,4; 3 знает о 1,2,3,4
1 - 4// 1 знает о 1,2,3,4; 4 знает о 1,2,3,4
Что и требовалось доказать

я убрал

Для 4-х доказано. А вот для трех нет.
FireSpace вырисовывается формула такая из вашего сообщения 2N-4, но при условии, что N>=4.
То есть для N=3, 2*N-3. А для остальных случаев ( не будем считать N=2), годится формула 2*N-4. Вот и все.

Получается так.

Можно и доказательство попробовать нарисовать. :)

Для N > 4 каждый следующий добавляет 2 звонка как минимум...

совершенно верно,
n=2 - 1
3-3
4-4
5-6
закономерность найти невозможно...