Тайное общество

[karzhas]

В тайном обществе 2011 членов, и у каждого есть счет в банке (на счету целое число рублей, которое может быть отрицательным). Время от времени один из членов общества переводит со своего счета на счет каждого из своих друзей, состоящих в обществе, по 1 рублю. Известно, что с помощью цепочки таких переводов они могут перераспределить имеющиеся на счетах средства произвольным образом. Докажите что в этом обществе ровно 2010 пар друзей

[TOTAL]

$A$ и $B$ - друзья
$S(A)$ - друзья любого колена для $A,$ но не для $B$
$S(B)$ - друзья любого колена для $B,$ но не для $A$
$S(A,B)$ - общие друзья любого колена для $A$ и $B$

Достаточно показать, что $S(A,B)$ пусто.
Для этого достаточно показать, что если $S(A,B)$ не пусто, то не существует набора переводов, единственным результатом которых является передача 1 рубля от $A$ до $B$

$N(A)$ - столько переводов сделал $A$
$N(B)$ - столько переводов сделал $B$

Очевидно, каждый из $S(A)$ сделал $N(A)$ переводов, каждый из $S(B)$ сделал $N(B)$ переводов.
Если $N(A)=N(B),$ то все сделали $N(A)$ переводов, т.е. рубль не передан.
Если $N(A) \ne N(B),$ то каждый из $S(A,B)$ сделал переводов строго между $N(A)$ и $N(B),$ поэтому разница счетов $A$ и $B$ изменилась больше, чем на 2.

[Dave]

TOTAL в сообщении #518376 писал(а):

Если $N(A) \ne N(B),$ то каждый из $S(A,B)$ сделал переводов строго между $N(A)$ и $N(B),$ поэтому разница счетов $A$ и $B$ изменилась больше, чем на 2.

Почему? Можно поподробнее этот момент?

[TOTAL]

Dave в сообщении #518788 писал(а):

TOTAL в сообщении #518376 писал(а):

Если $N(A) \ne N(B),$ то каждый из $S(A,B)$ сделал переводов строго между $N(A)$ и $N(B),$ поэтому разница счетов $A$ и $B$ изменилась больше, чем на 2.

Почему? Можно поподробнее этот момент?

Пусть $N(A) > N(B)$ и рекордсмен по переводам из $S(A,B)$ сделал $M > N(A)$ переводов. Все знакомые этого рекордсмена должны сделать тоже по $M$ переводов, знакомые их знакомых тоже по $M$ переводов и т.д. В конце концов придем к выводу, что $A$ и $B$ сделали по $M$ переводов. К противоречию также придем, если предположим, что $M = N(A)$ (по цепочке знакомств доберемся до $B$).

[Dave]

TOTAL в сообщении #518798 писал(а):

Пусть $N(A) > N(B)$ и рекордсмен по переводам из $S(A,B)$ сделал $M > N(A)$ переводов. Все знакомые этого рекордсмена должны сделать тоже по $M$ переводов, знакомые их знакомых тоже по $M$ переводов и т.д. В конце концов придем к выводу, что $A$ и $B$ сделали по $M$ переводов. К противоречию также придем, если предположим, что $M = N(A)$ (по цепочке знакомств доберемся до $B$).

Эти рассуждения справедливы только если от любого человека из $S(A,B)$ есть цепочка к любому другому из $S(A,B)$, не проходящая ни через $A$, ни через $B$, а это не всегда так. Да и даже если это так, то вывод ровно о $M$ переводах для $A$ и $B$ тоже не столь однозначен. К тому же $M$ - максимум для $S(A,B)$, поэтому теоретически возможен третий вариант, $M<N(A)$.

[Dave]

На всякий случай, вот моё решение.

Изобразим общество в виде графа, где каждому члену общества соответствует вершина, а паре друзей - ребро. Также будем говорить, что деньги переводятся между соответствующими вершинами графа. Мы выполним условие задачи, если докажем, что этот граф является деревом, т.е. связным графом без циклов.

Если бы граф был несвязным, т.е. из какой-либо вершины нельзя было бы пройти в другую по рёбрам этого графа, то очевидно, что и перераспределить деньги между этими двумя вершинами было бы невозможно.

Теперь предположим, что в графе присутствует цикл $C$. Возьмём любые две соседние вершины $a$ и $b$ внутри этого цикла. По условию, существует набор переводов, позволяющий перевести ровно 1 рубль от $a$ к $b$ и имеющий нулевой баланс операций на других вершинах. Сопоставим каждой вершине $x$ число $f(x)$, соответствующее количеству раз, когда из этой вершины осуществляется перевод по 1 рублю во все прилегающие вершины. Заметим, что если все эти числа равны $1$, то суммарный баланс операций нулевой для каждой вершины. Это означает, что если $m$ - минимум этих чисел по всем вершинам, то, вычитая $m$ из всех чисел, мы получим набор переводов, дающих тот же эффект. Значит, не ограничивая общности, можно считать, что минимум равен $0$.

Временно выбросим из графа ребро $\{a,b\}$. При этом, поскольку в любом пути между вершинами графа, содержащем это ребро, его (ребро) всегда можно заменить оставшимся куском цикла $C$, то граф не перестанет быть связным. Пусть теперь $d$ - вершина, на которой достигается вышеуказанный минимум чисел $f(x)$, равный $0$, ближайшая к $a$ в смысле пути по рёбрам модифицированного графа и $D$ - этот кратчайший путь. $a \ne d$, иначе это означало бы, что из $a$ нет переводов и суммарный баланс в $a$ неотрицательный, в то время, как он должен быть равен $-1$. Пусть теперь $p$ - вершина из $D$, непосредственно предшествующая $d$ по пути из $a$ ($p$ может совпадать с $a$). Поскольку ближе, чем $d$ к $a$, вершин с $f(x)=0$ нет, то $f(p)>0$. Теперь, в силу того, что $f(d)=0$ и в $d$ есть минимум один перевод из $p$, заключаем, что суммарный баланс в $d$ положительный, а значит $d=b$. Отсюда заключаем, что $p \ne a$, т.к. ребро $\{a,b\}$ было выброшено. Возвращая это ребро на место и учитывая, что $f(a)>0$, $f(p)>0$, а $f(b)=f(d)=0$, видим, что суммарный баланс в $b$ будет не менее $2$, что противоречит тому, что он должен быть равен $1$. $\blacksquare$

[TOTAL]

Dave в сообщении #519071 писал(а):

TOTAL в сообщении #518798 писал(а):

Пусть $N(A) > N(B)$ и рекордсмен по переводам из $S(A,B)$ сделал $M > N(A)$ переводов. Все знакомые этого рекордсмена должны сделать тоже по $M$ переводов, знакомые их знакомых тоже по $M$ переводов и т.д. В конце концов придем к выводу, что $A$ и $B$ сделали по $M$ переводов. К противоречию также придем, если предположим, что $M = N(A)$ (по цепочке знакомств доберемся до $B$).

Эти рассуждения справедливы только если от любого человека из $S(A,B)$ есть цепочка к любому другому из $S(A,B)$, не проходящая ни через $A$, ни через $B$, а это не всегда так.

Эти рассуждения справедливы всегда, т.к. в них не требуется доступ от любого к любому, а требуется только доступ от любого до $A$ и $B$

Поправка к первоначальной формулировке: $S(A)$ - это все те, к кому $B$ имеет доступ только через $A$