Search 75,466 tutors
FIND TUTORS
Ask a question
0 0

Solve Level D and E

Tutors, please sign in to answer this question.

1 Answer

This is known as Frobenius number, that is, the largest number, which cannot be obtained from a given collection of numbers. 
 
It is pretty obvious that if all coins are of even denomination, no odd sum can be obtain and Frobeniis number does not exist. Moreover, if set of three coins has greatest common divisor greater than 1, no number that is not the multiple of that divisor, can be obtained. Thus there are infinitely many impossible totals. But if gcd(a, b, c)=1 then there is largest impossible total. 
 
For the case of 6,7 and 8 cent stamps Frobenius number is 17. Proof is simple: you can obtain next 6 numbers, therefore any number after can be obtained by adding 6, 7, or 8 to one of those 6 numbers.
 
Let us check:
18=6+6+6
19=6+6+7
20=6+6+8
21=7+7+7
22=7+7+8
23=8+8+7
 
there is no general formula to find Frobenius number for three or more collections of stamps/coins. You may read more by this link:
 
The simplest reasoning using math notation is like this:
Let N be the number we are trying to represent. If we have coins of values a,b, and c then 
N=k1a+k2b+k3c
Here all k's are integers. If a,b,c have greatest common divisor p>1 then we MUST have:
 
N=p(k1n+k2m+k3l), where n,m,l are integers. Hence N MUST be divisible by p. So if you are given N, which is NOT divisible by p, such N can't be represented.Of course, there are infinitely many numbers not divisible  by a given number p> 1. Therefore, there are infinitely many impossible totals when the numbers a, b , and c have greatest common divisor > 1