Variations of the Frobenius coin problem

  • Thread starter richardfrobey
  • Start date
  • Tags
    Frobenius
In summary, the conversation discusses the existence of a formula or algorithm for solving problems involving n coin denominations totaling p cents and the Frobenius number. While an explicit formula is known for two coin denominations, there is no known explicit formula for three or more denominations. However, there is an algorithm that can compute the Frobenius number in polynomial time for any fixed number of denominations. The specifics of this algorithm are not known, but the question can be further explored on various online platforms.
  • #1
richardfrobey
1
0
I wasn't sure if this should go in the number theory section, but here goes:

Is there a formula for solving problems such as: If there are n coin denominations [itex]x_{1}[/itex],[itex]x_{2}[/itex]...[itex]x_{n}[/itex] that total p cents, how many combinations are possible? n and p are positive real numbers, of course.


On a side note, wikipedia says: "There is an explicit formula for the Frobenius number when there are only two different coin denominations. If the number of coin denominations is three or more, no explicit formula is known; but, for any fixed number of coin denominations, there is an algorithm computing the Frobenius number in polynomial time (in the logarithms of the coin denominations forming an input)."

Does anyone know what the algorithm that wikipedia mentions is? I know it cannot be written explicitly and mathematically (as per wikipedia), but can anyone write it in another format?


Feel free to repost this question on mathstackexchange, mathoverflow, yahoo! answers, etc. if it will help to get the answer.

Thanks in advance.
 
Mathematics news on Phys.org
  • #2
richardfrobey said:
If there are n coin denominations [itex]x_{1}[/itex],[itex]x_{2}[/itex]...[itex]x_{n}[/itex] that total p cents, how many combinations are possible?

Combinations of what? - you haven't stated a problem clearly.
 
  • #3
Stephen Tashi said:
Combinations of what? - you haven't stated a problem clearly.

I think this is asking about the number of combinations of coins that total less than or equal to p. I have seen similar problems, and even if this isn't what the TC meant (which I'm pretty sure it is), this should generate some interesting discussion.
 

1. What is the Frobenius coin problem and its variations?

The Frobenius coin problem, also known as the coin exchange problem, is a mathematical problem that involves finding the largest amount of money that cannot be made using a given set of coins. Variations of this problem involve changing the number of coins, their values, or the rules for exchanging them.

2. How is the Frobenius coin problem solved?

The Frobenius coin problem can be solved using a formula known as the "Frobenius number" or "Frobenius coin problem number." This number can be calculated using the values of the coins and a technique known as the "extended Euclidean algorithm."

3. What are some real-world applications of the Frobenius coin problem?

The Frobenius coin problem has applications in fields such as finance, computer science, and cryptography. In finance, it can be used to determine the minimum amount of change needed to make a given amount of money, while in computer science, it can be used to optimize algorithms for finding the optimal solution to the problem. In cryptography, it can be used to generate secure key exchange protocols.

4. What are some extensions of the Frobenius coin problem?

Some extensions of the Frobenius coin problem include the "generalized Frobenius coin problem," which allows for non-integer coin values, and the "multi-dimensional Frobenius coin problem," which involves finding the largest amount of money that cannot be made using a given set of coins in multiple currencies. There are also variations that involve finding the smallest amount that can be made or solving the problem for sets of more than two coins.

5. How does the Frobenius coin problem relate to other mathematical concepts?

The Frobenius coin problem is related to concepts such as number theory, combinatorics, and linear algebra. It can also be seen as a special case of the "knapsack problem," which involves finding the most valuable combination of items that can fit in a given container. Additionally, the techniques used to solve the Frobenius coin problem can be applied to other problems involving diophantine equations.

Similar threads

Combinatorics problem with coins
    • General Math
Replies
6
Views
2K
I Find an explicit formula for this n-sum problem
    • General Math
Replies
7
Views
1K
I Basel problem, primes and π²/6
    • General Math
Replies
5
Views
2K
Exploring the Variation in Movement Capacity of Individuals
    • Biology and Medical
Replies
4
Views
764
MHB Solving Probability Problem: Flip a Coin n Times (X) and n+1 Times (Y)
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Solution to Frobenius Problem for N=2: Proof?
    • General Math
Replies
3
Views
2K
I Are electrons universal problem solvers?
    • Quantum Physics
Replies
4
Views
733
I Solve Coin Sum Problem: Find Combinations for 200p
    • Linear and Abstract Algebra
Replies
13
Views
1K
Comp Sci Help with coin game C++ assignment?
    • Engineering and Comp Sci Homework Help
Replies
6
Views
2K
How to calculate the monthly interest rate?
    • Calculus and Beyond Homework Help
Replies
12
Views
1K

Hot Threads

Recent Insights

Back
Top