Как рассчитаться в группе минимальным числом переводов

Чтобы рассчитаться в группе минимальным числом переводов, перестаньте думать об отдельных долгах. Посчитайте одно число на человека — его баланс — и сводите тех, кто должен, с теми, кому должны, начиная с самых больших сумм. Это и есть весь способ упростить долги между друзьями: клубок из полутора десятков мелких долгов превращается в несколько переводов.

Сначала — баланс каждого

Баланс человека — сколько он заплатил минус его доля во всех расходах. Плюс — группа должна ему; минус — он должен группе. Сумма балансов всей группы всегда ровно ноль: каждый рубль, который кому-то должны, кто-то должен. Если у вас не ноль — какой-то расход разделён неправильно.

Главный сдвиг: когда балансы посчитаны, уже неважно, кто за что платил. Оля не должна отдельно Маше за дом и Косте за машину. Оля должна группе 19 560 ₽, и любой маршрут, по которому эти 19 560 ₽ дойдут до тех, кому должны, одинаково правильный.

Почему «каждый каждому» — это лишние переводы

Интуитивный способ — возвращать за каждый расход: по каждому чеку все переводят плательщику свою долю. Возьмём пятерых — Дима, Маша, Оля, Костя и Саша — после недели в Сочи, все расходы поровну на пятерых:

Четыре расхода, по каждому четверо должны плательщику: 16 долгов. Если платить их по одному — 16 переводов, причём некоторые идут в обе стороны. Костя должен Маше 24 000 ₽ за дом, а Маша Косте — 10 400 ₽ за машину: 10 400 ₽ уходят от Маши к Косте и тут же возвращаются обратно.

Если сначала свести каждую пару, станет лучше: Костя просто переводит Маше разницу 13 600 ₽. Пар у пятерых десять, значит, переводов не больше десяти. Лучше, но до минимума далеко.

Жадный способ: самый большой должник платит самому большому кредитору

Начинаем с балансов:

Плюсы: 74 095 + 6 095 = 80 190 ₽. Минусы: 14 725 + 19 560 + 45 905 = 80 190 ₽. Сходится до рубля.

Теперь повторяем один шаг, пока все не окажутся на нуле: тот, кто должен больше всех, платит тому, кому должны больше всех, сколько может — меньшую из двух сумм.

1. Больше всех должен Саша (45 905 ₽), больше всех должны Маше (74 095 ₽). Саша переводит Маше 45 905 ₽. Саша закрыт, Маше ещё должны 28 190 ₽.
2. Теперь больше всех должна Оля (19 560 ₽), а Маше по-прежнему должны больше всех (28 190 ₽). Оля переводит Маше 19 560 ₽. Оля закрыта, Маше должны 8 630 ₽.
3. Дима должен 14 725 ₽; Маше должны 8 630 ₽ — всё ещё больше, чем Косте (6 095 ₽). Дима переводит Маше 8 630 ₽. Маша закрыта, Дима должен ещё 6 095 ₽.
4. Дима переводит Косте 6 095 ₽. Закрыты оба.

Проверка: Маша получает 45 905 + 19 560 + 8 630 = 74 095 ₽ — ровно её баланс. Дима отправляет 8 630 + 6 095 = 14 725 ₽ — ровно его. Шестнадцать долгов, четыре перевода, ни рубля не потерялось.

Заметьте: Дима не платил за дом напрямую, а переводит Косте, которому ни за что конкретное не был должен. Это нормально — он платит ровно свою долю поездки, просто деньги попадают туда, где нужны.

Почему переводов никогда не больше n − 1

Каждый шаг полностью закрывает хотя бы одного человека: та из двух сумм, что меньше, обнуляется. Закрытый человек в расчёте больше не участвует.

У пятерых четыре шага закроют четверых. А раз сумма балансов всегда ноль, когда четверо на нуле, пятый тоже на нуле — последний перевод всегда закрывает сразу двоих. Поэтому переводов нужно максимум на один меньше, чем людей: четыре на пятерых, девять на десятерых. Те, у кого баланс уже ноль, вообще не считаются.

Иногда можно и лучше. Если двое в группе должны друг другу ровно столько же, сколько им нужно закрыть, они могут рассчитаться между собой и сэкономить перевод. Жадный способ такие совпадения специально не ищет, а найти точный минимум в общем случае — действительно трудная задача. В реальных компаниях разница редко больше одного перевода, а у простого способа есть свойство поважнее: его может проверить любой с карандашом.

Как посчитать вручную

Если считаете без приложения:

1. Выпишите, сколько каждый заплатил и какова его доля. В целых рублях или копейках, без «примерно».
2. Вычтите — получите балансы. Проверьте, что в сумме ноль.
3. Отсортируйте: сверху тот, кому должны больше всех, снизу тот, кто должен больше всех.
4. Сведите верх и низ, запишите перевод, обновите обоих и отсортируйте заново.

Минут десять на обороте чека. Если тратили в нескольких валютах, сначала всё переведите в одну — см. как делить расходы в разных валютах. В kisir балансы считаются по ходу, и каждый видит свою часть плана: кому и сколько перевести.

Отмечайте переводы

План закончен только тогда, когда деньги реально ушли и группа это видит.

• Отмечайте каждый перевод как платёж, а не как расход. Платёж гасит долг; расход его создаёт.
• Отмечайте в момент отправки, при желании с подписью — «Сочи». Балансы отправителя и получателя изменятся, а остальной план останется верным.
• Частичный перевод — нормально. Если Саша сейчас переводит 20 000 ₽, а остальное в пятницу, отметьте 20 000. Его баланс станет −25 905 ₽, больше ничего не меняется.

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

Если почти за всё платил один человек, план ещё проще — все переводят ему. Этот случай разобран отдельно: один заплатил за всех — как поделить.