Школьная задачка по математике

Dosperato

Вот, братишке в школе задали задачку, всю голову поломал, не могу никак решить:
Есть N бабушек, каждой из которых известна одна уникальная новость (не известная пока никакой другой). Они хотят поделиться ими друг с другом так, чтобы все знали всё. Для этого они звонят друг другу по телефону. При каждом звонке две бабушки обмениваются всеми новостями, которые им известны. Вопрос: для каждого N указать минимальное число звонков, необходимое для этого.

12457806

(N=2) - 1
(N=3) - 3
(N=4) - 5
(N=5) - 7
Короче, кажись (N-1)+(N-2)= 2N-3; N>1
Логика такая - первая "всезнающая бабка" (точнее, пара бабок образуется на N-1 звонке.
Но осталось еще N-2 бабок, для оповещения каждой из которых надо сделать как минимум один звонок.

Dosperato

Ну для 4х можно и побыстрее. Да и для 5ти тоже...

vvasilevskiy

Ну для 4х можно и побыстрее
Примеры в студию

12457806

Ну приведи решение для четырех бабок, по каждому звонку)

toxin

звонка для 4 бабок: 1-2, 3-4, 1-3, 2-4.

12457806

Ага, точно)
Придумывай тогда общее решение

griz_a

Не верю, что ее задали братишке в школе, потому что в олимпиадном задачнике "Математический аквариум" она значится как "очень сложная, где одним намеком не обойтись".
Что-то часто анонимусы стали обманывать честной народ.

Sergey79

4 звонка для 4 бабок: 1-2, 3-4, 1-3, 2-4.
Для N=2^n бабок:
Формируется сетка бабок как в кубковой системе розыгрышей. В первом туре бабки играют попарно. Во втором туре "победители" первого тура играют между собой, а проигравшие первого тура играют между собой. В третьем туре победители-победители играют между собой, победители-проигравшие играют между собой, проигравшие-победители играют между собой, проигравшие-проигравшие играют между собой.
Например для 8:
1) 1,2,3,4 vs 5,6,7,8: 1-5, 2-6, 3-7, 4-8
2) 1(5 2(6) vs 3(7) 4(8): 1-3(5-7 2-4(6-8)
3) 1(3,5,7) vs 2(4,6,8): 1-2 (3-4, 5-6, 7-8)
Итого n*2^(n-1) звонков. Быстрее - нельзя вроде.

griz_a

За 2N-3 можно запросто, а ты предлагаешь N log N/ 2
Ясно же что лажа

Sergey79

да, что-то я забыл асимптотики=)

Sergey79

Хорошо, у меня получилось уже 2N-4 для 2^n бабок

mtk79

Более того, в задачке предполагается минимизировать потери (время и нагрузку на сеть предполагая наличие некоторого коллективного разума у бабушек. Совершенно очевидно же, что сами бубульки будут максимизировать число звонков, и я не удивлюсь даже, если спустя час после того, как бабулька A_i поведает бабульке A_j свою сокровенную новость B_i, бабулька A_j позвонит бабульке A_i и, (если дозвонится, в чем я в случае N>3 абсолютно не уверен) поведает ее же сокровенную новомть

Sergey79

С точки зрения физического смысла, бабка является оператором, преобразующим новость (на входе) в некую новую новость (на выходе). То есть если в системе совершено более одного звонка, то каждый звонок будет генератором новых новостей, и количество звонков будет расходящимся.

lena1978

если первая бабка будет целый день названивать второй бабке, а вторая бабка никому не отзвонит, то нихера нового не будет.

blackout

Тут была неправда.

Sergey79

если первая бабка будет целый день названивать второй бабке, а вторая бабка никому не отзвонит, то нихера нового не будет.
fail, ведь вторая бабка будет сообщать при каждом следующем звонке преобразованные новости первой

lena1978

а, ты новое условие уже ввел

griz_a

По-моему, я для 8 строил меньше 12, но, честно говоря, строить сейчас лень. Потом ты интерполируешь другой кусочно-линейной функцией и там меня уже не хватит %)

Lokomotiv59

n-4 заведомо хватит для любого количества бабок n>3, не обязательно для степени двойки, так как имеет место рекуррентная формула: s(n+1) <= s(n) + 2

babygirl

По-моему, я для 8 строил меньше 12
Крайне маловероятно.

Lokomotiv59

Кстати удалось доказать, что s(n+1) >= s(n) + 1

griz_a

я уж не помню, решал ее год назад или даже два. по-моему, там периодически удается сэкономить 1 и во мне сильно мнение, что там не 2n асимптотика, а меньше.
но до серьезных результатов я не дошел.

griz_a

Да, видно где-то я налажал тогда :(
А жаль, мог бы, наверное, и докрутить, зная ответ :(
Оставить комментарий
Имя или ник:
Комментарий: