- #1
adamg
- 48
- 0
does anyone know a proof for the solution to the frobenius problem for n=2? that is, that the smallest not possible number expressable as a linear combination of a and b is (a-1)(b-1)??
The Frobenius Problem, also known as the coin problem or the postage stamp problem, asks for the largest integer that cannot be expressed as a linear combination of a given set of positive integer coefficients. For N=2, this means finding the largest integer that cannot be written as the sum of two non-negative multiples of two given integers.
Finding a solution to the Frobenius Problem for N=2 has applications in various fields, including number theory, combinatorics, and computer science. It can also be used to solve practical problems, such as determining the minimum number of coins needed to make change for a given amount.
The solution to the Frobenius Problem for N=2 can be derived using various methods, including the linear Diophantine equation method, the geometric method, and the greedy algorithm. Each method involves a systematic approach to finding the solution by considering all possible cases and using mathematical principles.
The proof for the solution to the Frobenius Problem for N=2 relies on the concept of the greatest common divisor (GCD). By finding the GCD of the two given integers, the solution can be expressed as a linear combination of the two integers. This proof can be extended to the Frobenius Problem for larger values of N.
Yes, the solution to the Frobenius Problem for N=2 is limited by the values of the given integers. If the GCD of the two integers is 1, then there is no limit to the largest integer that cannot be expressed as a linear combination. However, if the GCD is greater than 1, then there may be certain limitations on the solution.