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-23 03:56:49 · 2 answers · asked by iluxa 5 in Science & Mathematics ➔ Mathematics
Perhaps clarification is in order. The problem is not to find such X and Y that make S be simple and small. The problem, rather, is to find S for big and ugly X and Y. For instance, if the two coins were 17 and 146, what't be S?
2007-03-23 04:03:57 · update #1
x = 2
y = 3
1 - cannot
2 - can
3 - can
4 - can
5 - can
The answer is 2
2007-03-23 04:02:20 · answer #1 · answered by John S 6 · 0⤊ 1⤋
As I said last time, I think that the answer is (x - 1)(y - 1) but I haven't had time to formulate a proof.
2007-03-23 11:07:37 · answer #2 · answered by mathsmanretired 7 · 0⤊ 0⤋