[Math] the largest value not attained by coins worth $\$0.25$ and $\$0.29$? (Frobenius Coin Problem)

elementary-number-theorypuzzlerecreational-mathematics

I came across a math-related brain teaser recently that offered no solution, I present the gist of it and my reasoning so far.

Suppose I had an unlimited amount of two coin types that were worth $\$0.25$ and $\$0.29$ each. The question is: What is the maximum possible denomination that cannot be formed?

Now my reasoning:

Let z, a total producible denomination, be written as .25x + .29y = z.

Where x is the number of .25 coins, and y is the number of .29 coins and since we are counting the number of coins this limits x and y to the set of all positive integers.

By solving for y: y = (4z-x)/1.16 I was able to come up with a "procedure" to determine if a particular denomination can be produced from a combination of the two coins.

It is as follows for a denomination d under consideration:

  1. Set a to 4d

  2. Divide a by 1.16, if fully divisible then the result is the number of .29 coins, and we are done if not go to step 3

  3. Subtract 1 from a, the number of .25 coins is 1 more than before — if a becomes < 0 then the amount is not producible from these coin combinations otherwise repeat step 2

Does this reasoning seem sound? What I'm trying to do here is extrapolate out this process to prove that the maximum possible non-producible denomination is infinite. (Such as a base case of 1.99 cannot work based on procedure above, and if you continued to add .25 coins to this amount to infinity there would never be a maximum possible non-producible denomination).

I'd appreciate any mathematical insight to approaching this kind of problem.

Brian's answer was helpful, now I know the name of the problem. I see that $t = ma+nb$ can be the linear integral combination (from that PDF link) and t is representable only for solutions that have $m$ and $n$ with nonnegative integers, and that if you accept the inequality $0\le m \le (b-1)$ then the solution is $t = (b-1)a+(-1)b = (ab-a)-b = aa-a-b$.

Though, I have no idea where that inequality $0\le m \le (b-1)$ comes from, it seems to just be hand waved at.

So instead, I made a chart where (for my example problem) there's 29 rows and the chart is composed of all the counting numbers (one after the other). This makes each column 29 apart. Then it's elimination of all representable by finding the first number in each row divisible by 25 (in green). It can then be seen each number to infinity for that row thereafter can be created by adding more 29's (so all green numbers and those crossed off are representable). So in this chart, the red numbers are not representable, and the highest is 671 (which correlates to $ab-a-b = 25*29-25-29 = 671$). Also, from this chart I can conceptually see that all numbers can be created after a certain number of unrepresentable, which was something I was originally having hard time seeing. (They are represented by the … for infinity).

Anyways, back to the above: where does that inequality $0\le m \le (b-1)$ come from for the $ab-a-b$ solution?

enter image description here

Best Answer

It’s a well-known result of Sylvester that if $a$ and $b$ are relatively prime positive integers, the largest integer that cannot be written in the form $ma+nb$ for some non-negative integers $m$ and $n$ is $ab-a-b$. (He also showed that exactly half of the $(a-1)(b-1)$ integers $0,1,\dots,ab-a-b$ cannot be so written.) For your problem take $a=25$ and $b=29$ and work in cents.

This PDF gives a lot more information on the Frobenius coin problem, including a pretty accessible development of the first part of Sylvester’s result. (The later parts of the PDF are considerably more advanced.)

Related Question