1
$\begingroup$

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)

Improve this question
$\endgroup$
3
  • $\begingroup$ This appears to be the same question as Find the number of nonnegative integer solutions to linear systems $\endgroup$
    – Stef
    Commented Dec 14, 2022 at 14:28
  • $\begingroup$ 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. $\endgroup$
    – Stef
    Commented Dec 14, 2022 at 14:46
  • $\begingroup$ How can 1A+0B+3C correspond to the 10 combinations you mention ??? $\endgroup$
    – user16034
    Commented May 14, 2023 at 19:52

1 Answer 1

Reset to default
0
$\begingroup$

  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.)

  3. Implement an algorithm to count the number of solutions to this integer linear program, or equivalently, count the number of integer lattice points in this convex polytope. See, e.g., Finding all solutions to an integer linear programming (ILP) problem, https://math.stackexchange.com/questions/3001715/find-the-number-of-non-negative-integer-solutions-to-linear-systems, Counting the number of satisfied models - given mathematical constraints.

  4. Submit to your programming contest and win the contest. Make sure to credit all sources that you used in doing so.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.