Suppose you have a bunch of coins of 2 denominations, say X and Y, such that X and Y are co-prime. What is the smallest sum S, starting from which you can pay any sum without change?
Include the proof of the formula you find.
For example: suppose x=3, y=5.
1 - cannot pay
2 - cannot
3 - can
4 - cannot
5 - can
6 - can: 3 + 3
7 - cannot
8 - can: 3 + 5
9 - can: 3 + 3 + 3
10 - can: 5 + 5
11 - can: 8 (which we've shown already) + 3
so, the answer here would be 8.
2007-03-22 05:19:08 · 2 answers · asked by iluxa 5 in Science & Mathematics ➔ Mathematics
x = 2 , y = 3 . the only sum you cant pay w/o change would be 1, so your answer would be 2.
2007-03-22 05:25:23 · answer #1 · answered by dylan k 3 · 0⤊ 2⤋
Empirically it would seem that the answer is (x - 1)(y - 1).
I'll come back later if I can formulate a proof.
2007-03-22 12:52:53 · answer #2 · answered by mathsmanretired 7 · 1⤊ 0⤋