I have come across an interesting elementary school math question which I would like to generalize. The problem is roughly as follows:
There are $4$ apples and $5$ bananas. $3$ apples can used to form $1$ banana, and $3$ bananas can be used to form $1$ apple. How many apples and bananas are left after all possible conversions?
By doing the conversions manually, you will end up with $1$ banana and $0$ apples. For example, you can first convert $3$ of the $4$ apples into $1$ banana, leaving $1$ apple left, then convert the $5+1=6$ bananas into $2$ apples. Finally, you can convert the $1+2=3$ apples into $1$ banana and no apples left, which is the answer.
You can also first convert $3$ of the $5$ bananas into $1$ apple, leaving $2$ bananas, then convert $3$ of the $4+1=5$ apples into $1$ banana, leaving $2$ apples. Then convert the $2+1=3$ bananas into $1$ apple, and finally convert the $2+1=3$ apples into $1$ banana and no apples left, which also gives the same answer.
Now I was wondering how one can solve a generalized version of this problem: Given that there are $A$ apples and $B$ bananas, how many apples and bananas are left after all possible conversions? Assume that $k$ of one kind of fruit will convert to $1$ of the other.
I think that a solution to this problem will involve some usage of modular arithmetic, but I don't have any insights on how to approach a problem like this. The problem is that the fruits can keep converting back and forth to each other, and I'm not sure how to do deal with that. Obviously you would want to convert the most of one kind of fruit as you can to the other type, then repeat the process over and over again until there is $<k$ of each fruit, but I'm unsure of how to put that into mathematical terms which I can work with.
I was also wondering about another generalization which involves more than $2$ fruits, in that $k$ of one type of fruit can convert to $1$ of any other kind of fruit. If you could give any insight about this generalization as well, that would be greatly appreciated, but you don't have to if you don't want to. I was just mainly wondering about the first one.
TLDR; This boils down to taking modulo $k^2-1$ of a base $k$ number with digits $A,B$.
Let $f_k(A,B)$ be the result after applying all possible conversions to $(A,B)$.
Conversions are just repeated subtractions of $k$, and repeated subtraction is division.
For $A,B\ge 0$, this makes your process equivalent to the following:
Let $A/k = k\cdot q_a+r_a$ and $B/k = k\cdot q_b+r_b$.
New quantities will be $(A,B)\to (r_a+q_b, r_b+q_a)$.
Repeat previous steps until both quantities are less than $k$.
Taking your example, $(4, 5)\to (2, 3)\to (3, 0)\to (0, 1)$, hence $f_3(4,5)=(0,1)$.
There are $k^2$ possible final results of this process and all except $(0,0)$ repeat periodically.
That is, the period will be $k^2-1$.
The result $(0, 0)$ can occur only when $A=B=0$.
Else, it turns out that $f_k(A, B) = (x, y)$, where:
$$ \begin{array}{} M = k^2-1, \\ \alpha_0 = (A\cdot k + B) \bmod M, \\ \alpha = \begin{cases} \alpha_0, & \alpha_0\ne 0 \\ M, & \alpha_0 = 0 \end{cases},\\ x = \left\lfloor\frac{\alpha}{k}\right\rfloor \bmod k,\\ y = \alpha \bmod k.\\ \end{array} $$
So we have a closed form formula for this process.
Notice that $A\cdot k + B$ is a decimal representation of a base $k$ number with digits $A,B$.
Also notice that $x$ and $y$ are equations for base $k$ digits of a decimal number $\alpha$.
That is, this process is equivalent to taking modulo $M$ of a base $k$ number $A, B$.
The slight edge case is that we need the remainder $M$ instead of $0$ when taking mod.