Muốn chia tiền nhóm với ít lần chuyển khoản nhất, đừng thanh toán từng khoản một. Hãy tính số dư ròng của mỗi người (đã trả bao nhiêu trừ phần phải chịu), rồi cho người âm nhiều nhất trả người dương nhiều nhất, lặp lại đến khi mọi số dư về 0. Cách này luôn xong trong tối đa n − 1 lần chuyển cho nhóm n người, và thường ít hơn thế khi trong nhóm có những khoản tự triệt tiêu nhau.
Vì sao chia từng khoản lại sinh ra cả chục lần chuyển khoản
Một chuyến đi ba ngày của năm người bạn thường có rất nhiều khoản chi lắt nhắt: người này trả phòng, người kia trả bữa tối, người nọ đổ xăng, có người mua nước dọc đường. Nếu với mỗi khoản, ai cũng chuyển phần của mình cho người đã trả, số lần chuyển khoản tăng vọt. Chỉ bốn khoản chi lớn, mỗi khoản bốn người phải trả lại cho người ứng tiền, là đã 16 lần chuyển. Thêm vài khoản nhỏ nữa thì con số lên tới vài chục.
Điều thú vị là phần lớn số lần chuyển ấy thừa. Tiền đi vòng: Dũng chuyển cho An 300.000 đồng tiền phòng, rồi An lại chuyển cho Dũng 150.000 đồng tiền ăn sáng Dũng trả hộ. Hai lệnh chuyển gộp được thành một lệnh 150.000 đồng. Mở rộng ý đó cho cả nhóm, ta đi tới một nguyên tắc đơn giản: chỉ có số dư cuối cùng của mỗi người là quan trọng, còn ai trả hộ ai khoản nào không quan trọng.
Bước 1: tính số dư ròng của từng người
Số dư ròng = tổng tiền người đó đã bỏ ra cho nhóm − phần chi phí người đó phải chịu. Dương nghĩa là nhóm đang nợ người đó, âm nghĩa là người đó đang nợ nhóm. Tổng số dư của cả nhóm luôn bằng 0, vì mọi đồng ai đó trả hộ đều là phần mà người khác phải chịu. Đây cũng là cách kiểm tra sổ sách nhanh nhất: cộng cột số dư mà không ra 0 là đã ghi sai ở đâu đó.
Ví dụ: năm người đi Đà Lạt, chia đều mọi khoản. An trả homestay 3.000.000 đồng, Bình trả các bữa ăn 1.500.000 đồng, Chi trả tiền thuê xe 1.000.000 đồng, Hoa trả vé tham quan 500.000 đồng, Dũng chưa trả gì. Tổng chi 6.000.000 đồng, mỗi người chịu 1.200.000 đồng.
| Người | Đã trả | Phải chịu | Số dư ròng |
|---|---|---|---|
| An | 3.000.000 | 1.200.000 | +1.800.000 |
| Bình | 1.500.000 | 1.200.000 | +300.000 |
| Chi | 1.000.000 | 1.200.000 | −200.000 |
| Hoa | 500.000 | 1.200.000 | −700.000 |
| Dũng | 0 | 1.200.000 | −1.200.000 |
| Cộng | 6.000.000 | 6.000.000 | 0 |
Nếu không chia đều (có người không ăn bữa nào đó, có người không đi tham quan), cột "phải chịu" sẽ khác nhau, nhưng cách tính số dư vẫn y như vậy. Mọi phức tạp của việc ai dùng gì đều dồn vào cột "phải chịu"; còn bước thanh toán phía sau chỉ cần cột cuối.
Bước 2: người nợ nhiều nhất trả người được nhiều nhất
Cách làm tay phổ biến nhất gọi là cách tham lam: mỗi lượt, ghép người có số dư âm lớn nhất với người có số dư dương lớn nhất, cho chuyển số tiền nhỏ hơn trong hai giá trị tuyệt đối. Sau mỗi lượt, ít nhất một người về đúng 0 và ra khỏi danh sách.
- Dũng (−1.200.000) trả An (+1.800.000) đúng 1.200.000. Dũng về 0, An còn +600.000.
- Hoa (−700.000) trả An (+600.000) 600.000. An về 0, Hoa còn −100.000.
- Bình còn +300.000. Chi (−200.000) trả Bình 200.000. Chi về 0, Bình còn +100.000.
- Hoa (−100.000) trả Bình 100.000. Tất cả về 0.
Bốn lần chuyển cho năm người, thay vì mười mấy lần nếu thanh toán từng khoản. Vì mỗi lượt loại ít nhất một người, và lượt cuối loại cùng lúc hai người, số lần chuyển không bao giờ vượt quá n − 1. Nhóm 8 người đi chơi cả tuần, ghi vài chục khoản, cũng chỉ cần tối đa 7 lệnh chuyển.
Cách "một đầu mối" cũng cho n − 1 lần
Một cách khác cũng ra n − 1: chọn một người làm đầu mối, ai âm thì chuyển cho đầu mối, đầu mối chuyển lại cho ai dương. Số lệnh bằng nhau, nhưng lượng tiền đi qua tay đầu mối lớn hơn, và người đầu mối phải chờ nhận đủ rồi mới chuyển đi được. Nhóm thân, có sẵn một người giữ quỹ, thì cách này dễ theo dõi. Nhóm lỏng lẻo hơn thì cách tham lam đỡ phiền vì ai trả xong là xong.
Có thể ít hơn n − 1 không: khi có nhóm con tự cân
Con số n − 1 chỉ là mức trần. Muốn ít hơn, phải tìm được những nhóm con mà tổng số dư bằng 0. Mỗi nhóm con như vậy tự thanh toán nội bộ được, và tiết kiệm đúng một lần chuyển.
Ví dụ sáu người có số dư: +500.000, +400.000, +100.000, −500.000, −300.000, −200.000. Cách tham lam: người −500.000 trả người +500.000 (một lệnh, cặp này tự cân); người −300.000 trả người +400.000 300.000; người −200.000 trả người +400.000 100.000 và trả người +100.000 100.000. Tổng bốn lệnh, ít hơn n − 1 = 5. Không thể xuống ba lệnh, vì ở đây chỉ tách được đúng hai nhóm tự cân: cặp {+500.000; −500.000} và bộ {+400.000; +100.000; −300.000; −200.000}.
Công thức tổng quát: số lần chuyển tối thiểu = n − k, trong đó k là số nhóm con tự cân lớn nhất có thể tách được. Với ví dụ Đà Lạt ở trên, không có nhóm con nào (ngoài cả nhóm) có tổng bằng 0, nên k = 1 và bốn lần đã là ít nhất.
Vì sao máy tính cũng thấy khó
Tìm k lớn nhất nghĩa là thử chia tập số dư thành càng nhiều nhóm tổng bằng 0 càng tốt. Đây là họ hàng của bài toán tổng tập con (subset sum) quen thuộc trong tin học, và đã được chứng minh thuộc lớp NP-khó: chưa ai biết thuật toán nào chạy nhanh cho mọi trường hợp khi số người lớn. Với nhóm bạn dưới chục người thì không sao, máy thử hết các cách tách chỉ trong tích tắc. Còn khi làm tay, mẹo thực tế là nhìn xem có cặp nào bằng nhau về giá trị tuyệt đối (một người +350.000, một người −350.000) thì ghép họ trước, rồi mới chạy cách tham lam cho phần còn lại.
Làm tròn để chuyển khoản cho gọn
Số dư thật thường lẻ, kiểu 437.333 đồng. Có hai cách gọn:
- Làm tròn số dư trước khi ghép: tròn mọi số dư về nghìn đồng, rồi chỉnh một người (thường là người đầu mối hoặc người có số dư lớn nhất) để tổng vẫn bằng 0. Sai lệch mỗi người không quá 500 đồng.
- Làm tròn từng lệnh chuyển: ghép như bình thường, đến lệnh cuối cùng thì để nguyên số lẻ. Cách này đúng tuyệt đối nhưng lệnh cuối nhìn hơi khó chịu.
Với nhóm bạn, sai vài trăm đồng không ai bận tâm. Quan trọng là quy ước từ đầu, để không ai cảm thấy mình bị làm tròn thiệt một cách âm thầm.
Chuyến dài, nhiều tháng: cứ cộng dồn số dư
Nhóm hay đi ăn với nhau, đi chơi cuối tuần, góp tiền sinh nhật, không cần thanh toán sau mỗi lần. Chỉ cần một bảng ghi số dư lũy kế: mỗi khoản chi mới cộng vào cột của người trả, trừ vào cột của những người hưởng. Khi số dư của ai đó vượt một ngưỡng (chẳng hạn quá 1.000.000 đồng), hoặc cuối mỗi tháng, mới chạy một lượt thanh toán.
Lợi ích là các khoản chi tự triệt tiêu nhau theo thời gian. Tuần này An trả, tuần sau Bình trả, cộng dồn lại số dư có khi gần 0, chẳng cần chuyển đồng nào. Rủi ro là người hay ứng tiền bị "ngâm" lâu; nên đặt ngưỡng rõ ràng để không ai phải ôm khoản lớn quá lâu.
| Cách thanh toán | Số lệnh chuyển (5 người, 4 khoản lớn) | Hợp khi |
|---|---|---|
| Trả lại từng khoản | Có thể tới 16 | Chỉ có một, hai khoản chi |
| Một đầu mối giữ quỹ | 4 | Nhóm có người tin cậy giữ tiền |
| Tham lam theo số dư ròng | Tối đa 4, thường ít hơn | Nhóm đông, nhiều khoản chi |
| Cộng dồn nhiều tháng | Gom vào một đợt | Nhóm gặp nhau thường xuyên |
Những điều cần thống nhất để khỏi mất lòng
Cách tham lam có một hệ quả mà nhiều người không để ý: người nợ có thể phải chuyển tiền cho một người mà họ chưa từng "nợ trực tiếp". Trong ví dụ trên, Hoa trả cho Bình 100.000 đồng dù Hoa không ăn bữa nào Bình trả riêng cho mình. Về tiền thì hoàn toàn đúng, nhưng ai không quen sẽ thắc mắc. Nên nói trước với cả nhóm: "Mình tính theo số dư cuối, ai chuyển cho ai là để ít lệnh nhất."
- Ghi khoản chi ngay khi phát sinh, kèm ảnh hoá đơn nếu có. Ghi lại từ trí nhớ sau ba ngày là nguồn gốc của hầu hết tranh cãi.
- Ghi rõ ai hưởng mỗi khoản, đặc biệt các khoản không phải ai cũng dùng (đồ uống có cồn, vé một điểm tham quan chỉ vài người vào).
- Công khai bảng số dư trước khi chạy thanh toán; cho mọi người vài giờ để soát.
- Ai đã chuyển xong thì đánh dấu, để người nhận kiểm tra với biến động số dư tài khoản.
Góc nhìn hôm nay: ứng dụng làm hộ, nhưng nên hiểu cách nó tính
Nhiều ứng dụng chia tiền phổ biến có tính năng "đơn giản hoá nợ" chạy đúng ý tưởng trên: gộp mọi khoản thành số dư ròng rồi đề xuất ít lệnh chuyển. Biết nguyên lý giúp bạn tự kiểm tra kết quả bằng một bảng tính: cột đã trả, cột phải chịu, cột số dư, và dòng cộng phải bằng 0. Nếu dùng bảng tính, hàm SUM cho cột số dư là phép thử đầu tiên; sắp xếp cột số dư từ âm nhiều nhất đến dương nhiều nhất là đã có sẵn thứ tự ghép cặp cho cách tham lam. Ai muốn đọc sâu hơn về mặt lý thuyết có thể tìm các tài liệu về "debt simplification" hay "minimum cash flow" trong sách thuật toán, nơi bài này thường làm ví dụ cho đồ thị có trọng số.
Câu hỏi thường gặp
Chia tiền nhóm thế nào để ít lần chuyển khoản nhất?
Tính số dư ròng mỗi người bằng tiền đã trả trừ phần phải chịu. Sau đó cho người âm nhiều nhất trả người dương nhiều nhất, lặp lại đến khi mọi số dư về 0. Nhóm n người cần tối đa n − 1 lần chuyển.
Số dư ròng là gì?
Số dư ròng là chênh lệch giữa số tiền một người đã bỏ ra cho nhóm và phần chi phí người đó phải chịu. Dương là nhóm nợ người đó, âm là người đó nợ nhóm. Tổng số dư của cả nhóm luôn bằng 0, nên đây cũng là cách kiểm tra sổ sách.
Vì sao có lúc chỉ cần ít hơn n − 1 lần chuyển?
Khi trong nhóm có những nhóm con có tổng số dư bằng 0, mỗi nhóm con tự thanh toán nội bộ và tiết kiệm được một lần chuyển. Số lần chuyển tối thiểu bằng số người trừ số nhóm con tự cân tách được.
Thuật toán đơn giản hoá nợ có làm ai bị thiệt không?
Không, mỗi người vẫn trả hoặc nhận đúng số dư của mình. Điều khác duy nhất là người nhận tiền có thể không phải người mình đã nợ trực tiếp, nên cần thống nhất trước với cả nhóm.
Có nên thanh toán sau mỗi lần đi ăn không?
Với nhóm gặp nhau thường xuyên, cộng dồn số dư rồi thanh toán theo tháng hoặc khi ai đó vượt một ngưỡng đặt trước sẽ gọn hơn nhiều. Các khoản thường tự triệt tiêu một phần theo thời gian.