Часть информации

[wpoms.]

Каждому из `n` членов клуба сообщили только некоторую, разную для разных членов клуба, часть информации. Они могут делиться этой информацией, но, по соображениям безопасности, только следующим образом: любые два члена клуба могут связаться друг с другом по телефону, но во время телефонного разговора только один из них может говорить и он может сообщить собеседнику всю имеющуюся у него информацию. Определите минимальное количество телефонных звонков, которые нужно сделать для распространения всей информации всем членам клуба.

@темы: Дискретная математика, Комбинаторика

Comments

[Adjirranirr]

Уточнение — что значит «разную часть информации»? Тут возможно 2 интерпретации.

Первая — информация двух членов клуба может пересекаться. Если формально, пусть суммарное множество информации есть `U = {x_1,\ x_2,\ ...,\ x_n}`, и если первый участник обладает информацией в размере `U \\ {x_1}`, второй — `U \\ {x_2}`, `i`-й — `U \\ {x_i}`, и так далее, то звонков необходимо (и достаточно) `n`. Каждый должен принять звонок хотя бы раз, а при любом звонке получатель в итоге обладает всей информацией.
В общем случае, для произвольного множества `U` с допущением возможности пересечения информации, определить количество звонков невозможно — можно только утверждать, что `n <= k <= 2n - 2`.

Вторая — информация строго уникальна (никакие `2` члена клуба не обладают общей информацией). Тогда, чтобы передать всю информацию, потребуется `2n - 2` звонка. В самом деле, при `n = 2` звонков, очевидно, необходимо и достаточно `2`; и если `n` членов распространяют информацию между собой за `2n - 2` звонка, клубу с `n + 1` членами потребуется на `2` звонка больше, так как «лишний» должен хотя бы один раз позвонить и хотя бы один раз принять звонок. По теореме об индукции, звонков потребуется `2n - 2` для любого `n`.