# Coin exchange, find different triples of values

Suppose i have 3 coins: A, B, C. Each one of them have different value: a, b, c. And if want to exchange coins A for coins B, i need to be able to give exactly a units of currency A and get exactly b units of currency B in return. The problem is to find how many different triples of coins i can have? For example, if i got 1 coins of A, 0 coins of B, 3 coins of C, and its currencies is a=1 b=1 c=1, i can have 10 different triples of values:

• 0 0 3
• 0 3 0
• 3 0 0
• 1 0 2
• 1 2 0
• 2 1 0
• 0 1 2
• 0 2 1
• 2 0 1
• 1 1 1

Is there any mathematical formula that allows me to do this calculation without looping through all possible triples? (1 ≤ A, B, C ≤ 10^9), (0 ≤ a, b, c ≤ 10^9)

• This appears to be the same question as Find the number of nonnegative integer solutions to linear systems
– Stef
Dec 14, 2022 at 14:28
• Also, if you want to find a particular solution to equation ax+by+cz=S, you can use the extended Euclidean algorithm twice. Calling S your initial sum of money, and calling g = gcd(a, b), use the algorithm a first time to find (u, v) that solves au+bv=g and a second time to find (w,z) that solves gw+cz=S. Combine those two into a final solution (x=uw, y=vw, z): (au+bv)w + cz = S becomes a(uw)+b(vw)+cz=S.
– Stef
Dec 14, 2022 at 14:46
• How can 1A+0B+3C correspond to the 10 combinations you mention ???
– user16034
May 14 at 19:52

1. Introduce integer variables $$x,y,z$$. Let $$x$$ count the number of times that you've exchanged a units of currency A for b units of currency B, $$y$$ count the number of times that you've exchanged a units of currency A for c units of currency C, and $$z$$ count the number of times that you've exchanged b units of currency B for c units of currency C.
2. Write down linear inequalities on $$x,y,z$$ that determine which values lead to an admissible triple. (This is your programming contest / exercise problem, so you get to do this part.)