4

I came across the below problem

In the olden days, there were only $4$ paise, $7$ paisa, and $11$ paisa coins. What is the maximum amount you can't exactly pay using just the three sets of coins?

I recognized that this is somewhat related to the Frobenius number for three sets of numbers but as per my knowledge there is no well-defined explicit formula to calculate the Frobenius number for three sets of numbers as we have for two numbers. Then how can we proceed ahead to solve this problem? Is there any other way to approach this kind of scenario? Please help !!!

Thanks in advance !!!

Ganit
  • 1,689

2 Answers2

3

I don't know anything about Frobenius numbers, but there is a way to do this problem by checking not too many cases. Since we have a $4$ paisa coin, then as soon as we have four consecutive numbers we can give exact change for, then we can give exact change for all subsequent numbers. I started checking cases at $12$ paisa but for sake of brevity I'll just tell you the first sequence of four I found: $18=11+7$, $19 = 11+4+4$, $20 = 4\cdot 5$, and $21 = 7\cdot 3$.

On the other hand, $17$ is not payable in exact change: $2\cdot 11=22>17$ so we can use either none or one $11$ paisa coin. If we use one $11$ paisa coin, then we must pay $6$ paisa, which is impossible with $7$ and $4$ paisa coins as $7$ is too big and $6$ is not a multiple of $4$. Similar analysis shows $17$ is not payable using just $7$ and $4$ paisa coins so the proof is complete.

Edit: I wrote this before Theo commented the simplifying observation that $11=7+4$, so this proof can probably be shortened.

Glare
  • 3,639
2

The answer is at most $17$ from the least value of pairs of coins, in this case $(4-1)(7-1)-1=17$. As $17-11=6$ is not achievable with only $4$ and $7$, the answer is $17$.

JMP
  • 21,771