Помогите, плз.

[Sergey Berlov]

Приветствую тебя, Max!

> Max Alekseyev к Soumarokov Stas.

SS>> Сто друзей узнали сто новостей, причем каждый узнал одну свою
SS>> новость. Друзья начали перезваниваться и рассказывать друг другу
SS>> новости. Один разговор идет один час, и за один разговор можно
SS>> передать любое количество новостей. За какое минимальное время
SS>> все узнают все новости?

SS>> Число 100 выбрано произвольно. Hужен алгоритм для N друзей и
SS>> новостей. При N=2^x все в порядке - ответ х, в других случаях
SS>> ничего понять не могу.

MA> Пусть f(N) - минимальное число часов, необходимое для того, чтобы все
MA> N человек узнали все N новостей.

MA> *Утверждение* 1. f(N) >= ceil(log2(N))
MA> /Доказательство/. Всего должно быть передано/получено N(N-1) новостей.
MA> За один час номер t совершается максимум N/2 звонков, причем каждый
MA> звонок передает максимум 2^t новостей. Пусть x=f(N). Тогда N/2
MA> (2+2^2+...+2^x) >= N(N-1) 2^x - 1 >= N-1
2^x >> = N
x >> = ceil(log2(N))

MA> *Утверждение* 2. f(2^x) = x.
MA> /Доказательство/ очевидно.

MA> *Утверждение* 3. f(N) <= ceil(log2(N)) + 1
MA> /Доказательство/. Пусть 2^x < N <= 2^{x+1}. Разобьем множество людей N
MA> на два N = M + K, где M=2^x, K=N-2^x. Понятно, что K<=M. Алгоритм
MA> звонков: 1 час: люди из K звонят каким-то (любым) людям из M с 2 по
MA> (x+1) часы: люди из M делятся между собой всеми новостями (см.
MA> утверждение 2) x+2 час: люди из K звонят каким-то (любым) людям из M В
MA> результате указанной последовательности звонков все узнали все
MA> новости, и на это понадобилось x+2=ceil(log2(N))+1 часов.

MA> *Гипотеза* 3. Если N нечетно, то f(N) = ceil(log2(N)) + 1.
Доказательство: в первый час был человек, который не участвовал в разговорах.
Тогда его новость в первый час знал 1 человек, во второй --- не более 2,
в третий --- не более 4 и т. д. Значит, все люди ее узнают не ранее, чем
через $[\log_2]+2$ звонков.
MA> *Гипотеза* 4. Если N четно, то f(N) = ceil(log2(N)).
Доказательство: пусть в группе $2k$ людей. Разобьем ее на 2 равные части
и перенумеруем людей в частях $A_1, A_2, \dots ,A_k$ и $B_1, \dots ,B_k$.
Пусть во время $m$-того разговора человек с номером $A_i$ говорит с человеком
с номером $B_{i+2^{m-1}}$, где индекс берется по модулю $k$. Тогда до разговора
с номером $[\log_2(2k)]$ включительно каждую новость будет каждый час узнавать
ровно вдвое больше людей. Осталось заметить, что во время последнего разговора
каждую новость узнают все.

Счастливо!

Serg

XC: #RU.MATH, #PERSONAL.FROM