There are $N$ banks with each having some some (possibly negative) integral balance with them. We say, a bank is in debt if its balance is less than rupee $0$. In each step, a bank may
- borrow $1$ rupee from every other banks, thus increasing its own balance by rupee $(N-1)$ and decreasing other banks' balances by rupee $1$ each
- lend $1$ rupee from every other banks, thus decreasing its own balance by rupee $(N-1)$ and increasing other banks' balances by rupee $1$ each
If at the beginning, the total amount of money with all the banks is rupee $0$, then is it possible to free every bank from debt in only a finite number of steps? If not, then what is the minimum total balance required to do so?
I could see that rupee $0$ wont work as if we let $N=3$ and if the balances in the three banks are rupee $1$, rupee $0$, and rupee $-1$ respectively, then no matter what move we make, either the bank with negative balance goes to more negative, or the balance configuration remains same. Although this looks quite obvious, I have not been able to devise a formal proof of this.
For the general case, I couldn't figure out anything. Here is a Numberphile video by Holly Krieger, where she discusses a case for a general graph with only the second condition allowed in each step. In our case, we have a complete graph, and so, with only the second step allowed, we can expect the answer to be
$$\text{Total balance}\geq \binom N 2-N+1$$
but as professor Krieger mentions, the general formula of $\text{Total balance}\geq \mathtt{genus}$ requires quite advanced methods from Graph Theory. But, I am expecting an elementary solution for the present problem.
Although I recieved quite an elegant answer, I would like to add something to my question. In the original source of this question, it was framed in a little different manner. The question already had a suggestion of three different ways one can take to achieve a solution (any of which may or may not be true) and they were-
- Write a system of linear equations describing the initial balances and the exchanges, and then solve it to get to an answer.
- Find a proof of the $N=3$ case and extend it to free other banks from debt.
- Find an invariant and use it solve the process.
While the answer I got seems to use the last suggestion, I was throughout under the impression that the second way is also a valid one.
So, is there an inductive way to reach to the solution? I feel like there should be a way to argue inductively. I would like to see some of your attempts to do so.
Note: If anybody knows the code for the symbol of Indian Rupee in MathJax, please edit the question, or share the command. I know the code used in Overleaf, but that doesn't seem to work here.
Best Answer
Let $x_1,\dots,x_N$ denote the wealth of each bank at some point in the process. For each $i\neq j$, the quantity $x_i-x_j\pmod N$ is invariant. Therefore, you can only hope to succeed when the balances of all banks are congruent modulo $N$. In your example with $N=3$ and $(x_1,x_2,x_3)=(-1,0,1)$, we have $x_2-x_1=x_3-x_2=x_1-x_3\equiv 1\neq 0\pmod 3$, proving you cannot win. The same goes when $(x_1,x_2,x_3)=(0,0,1)$, since $x_2-x_3\not\equiv 0\pmod 3$.
Conversely, if all balances are congruent $\pmod N$, then you can succeed by repeatedly having the wealthiest bank lend to everyone else. To prove this, suppose that $t$ banks are tied for wealthiest. In a single step, each of these $t$ banks will lend to everyone else. You can then show that the quantity $$ \sum_{i<j} |x_i-x_j| $$ is strictly decreased by this step, in several cases.
If $x_i$ and $x_j$ are both tied for wealthiest, then $|x_i-x_j|=0$ both before and after this step.
If $x_i$ and $x_j$ are not tied for wealthiest, then both $x_i$ and $x_j$ receive $t$ rupees from the $t$ wealthiest banks, so $|x_i-x_j|$ is unchanged.
If $x_i$ was the wealthiest and $x_j$ was not, then the fact that $x_i-x_j\equiv 0\pmod N$ implies that their balancess differ by at least $N$, which means that that having $x_i$ lend to everyone decreases $|x_i-x_j|$ by $N$.