A country has three denominations of coins, worth 7, 10, and 53 units of value. What is the maximum number of units of currency which one cannot have if they are only carrying these three kinds of coins?
I agree with Guest #6, we are looking for 7x + 10y + 53z = d where d is the sum required and x, y and z are all positive.
That means that most of the smaller sums are not possible, (we are not allowed to pay 8 units for example, by tendering 24 7 unit coins and receiving 16 10 ' s in change).
The answer can be arrived at by what might be regarded as trial and error.
Forget the 53 for the moment and just look at the 7 and 10 unit coins, and prior to that the various multiples of 7,
7, 14, 21, 28, 35, 42 ,49, 56, 63, and notice that that the units digits cover each of the numbers from 1 to 9.
Some examples.
Suppose the sum required were 89, to make this up, look at the final digit 9 and that will lead to 89 = 49 + 40 = 7*7 + 4*10.
Similarly 74 = 14 + 60 = 2*7 + 6*10,
68 = 28 + 40 = 4*7 + 4*10, etc.
If the sum is large we may or maynot choose to make use of the 53 unit coins.
For example if the sum required was say 732, we could still use just 7's and 10's, 732 = 42 + 690 = 6*7 + 69*10, (there's nothing in the question to say that we can't do that), or we could say that 732 = 636 + 96 = 12*53 + 8*7 + 4*10.
Going back to smaller numbers, we couldn't make up a sum of 39, for example, because, from the 7's multiples we would have to use the 49 and that is too big, it's greater than the required 39.
Looking at it this way the largest number that can't be made up, (with one exception), is 46, as it requires the use of 56.
All numbers above this, with one exception, can be catered for.
47 = 7 + 40, 48 = 28 + 20, 49 = 49, 50 = 50, 51 = 21 + 30, 52 = 42 + 10, 53 = ????.
53 doesn't work, the 3 means that we have to use 63 which is too big, and that's why 53 is included in the question as a third denomination coin.
There is some background analysis using the Euclidean algorithm, it leads to
\(\displaystyle \frac{2S}{7}\leq k \leq\frac{3S}{10}\quad ,\)
where S is the sum required and k is a parameter.
For a given value of S, it's necessary to be able to find an integer value for k in order that the sum can be made up with 7's and 10's.
If, for example S = 46 we have 92/7 (=13.14..)<= k <= 138/10 (=13.8), so no integer k exists, so 46 can't be catered for,
while, for example,
if S = 47, 94/7 (=13.43..) <= k <= 141/10 (=14.1), so k = 14 and a solution can be found.
Tiggsy
If I understand your question, you want to know if there is a maximum amount that you CANNOT make by adding or subtracting these 3 coins. If that is what is meant, then I think there is NO MAXIMUM that you cannot make. My reasoning is that you can make ALL the numbers from 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10 and up just from the 7 and 10 by adding and subtracting them. Example: If you want to make 1,000,000 from these 3 coins, you could easily do it this way: [18,866 x 53] + [6 x 7] + [6 x 10] = 1,000,000.
Let us know if that is what is meant by the question.
This is how i understood his question (correct me if i'm wrong):
Find largest natural number that we can't express as 7*a+10*b+53*c where a, b, c are non-negative integers.
Well, if we are allowed to add AND subtract the 3 coins, then I cannot think of not being able to make up ANY number by finding the proper values of a, b, c. Now, for exmple, you would think that it would be difficult or not possible to make up a number 1 greater than the LCM of 7, 10, 53. But, that is not the case because: LCM [7, 10, 53] =3,710 + 1 =3,711. I can easily make up 3,711 as follows:
[69 x 53] + [ 7 x 2] + [ 10 x 4] =3,711........and so on and in many different combinations of the 3 coins.
No. This is a variant of the Chicken McNugget theorem. It’s 7x+10y+53z=d. We want to find the biggest value of d where it cannot be expressed as the left hand side. Also, x, y, z, are all positive. I personally dunno how to do this type thoe. Somebody else maybe post solution? C Phill? Melody?
I agree with Guest #6, we are looking for 7x + 10y + 53z = d where d is the sum required and x, y and z are all positive.
That means that most of the smaller sums are not possible, (we are not allowed to pay 8 units for example, by tendering 24 7 unit coins and receiving 16 10 ' s in change).
The answer can be arrived at by what might be regarded as trial and error.
Forget the 53 for the moment and just look at the 7 and 10 unit coins, and prior to that the various multiples of 7,
7, 14, 21, 28, 35, 42 ,49, 56, 63, and notice that that the units digits cover each of the numbers from 1 to 9.
Some examples.
Suppose the sum required were 89, to make this up, look at the final digit 9 and that will lead to 89 = 49 + 40 = 7*7 + 4*10.
Similarly 74 = 14 + 60 = 2*7 + 6*10,
68 = 28 + 40 = 4*7 + 4*10, etc.
If the sum is large we may or maynot choose to make use of the 53 unit coins.
For example if the sum required was say 732, we could still use just 7's and 10's, 732 = 42 + 690 = 6*7 + 69*10, (there's nothing in the question to say that we can't do that), or we could say that 732 = 636 + 96 = 12*53 + 8*7 + 4*10.
Going back to smaller numbers, we couldn't make up a sum of 39, for example, because, from the 7's multiples we would have to use the 49 and that is too big, it's greater than the required 39.
Looking at it this way the largest number that can't be made up, (with one exception), is 46, as it requires the use of 56.
All numbers above this, with one exception, can be catered for.
47 = 7 + 40, 48 = 28 + 20, 49 = 49, 50 = 50, 51 = 21 + 30, 52 = 42 + 10, 53 = ????.
53 doesn't work, the 3 means that we have to use 63 which is too big, and that's why 53 is included in the question as a third denomination coin.
There is some background analysis using the Euclidean algorithm, it leads to
\(\displaystyle \frac{2S}{7}\leq k \leq\frac{3S}{10}\quad ,\)
where S is the sum required and k is a parameter.
For a given value of S, it's necessary to be able to find an integer value for k in order that the sum can be made up with 7's and 10's.
If, for example S = 46 we have 92/7 (=13.14..)<= k <= 138/10 (=13.8), so no integer k exists, so 46 can't be catered for,
while, for example,
if S = 47, 94/7 (=13.43..) <= k <= 141/10 (=14.1), so k = 14 and a solution can be found.
Tiggsy
As Guest#6 says, there is actually a Theorem called the "Chicken McNugget Theorem" and is discussed in some significant detail here:
https://artofproblemsolving.com/wiki/index.php?title=Chicken_McNugget_Theorem
+2440 There is a “Chicken McNugget’s Theorem,” but there should not be one.
The real reason is the “cute” name “Chicken McNugget’s Theorem.” If it’s “cute” then more will remember it and use it. Cuteness in general, and anthropomorphic cuteness in particular, is the byword for educating children and adults too. We might not understand it unless a blòódy dancing McNugget explains it to us.
According to the Wikipedia article the “Chicken McNugget’s Theorem” is a “special case” of the Frobenius coin problem. The supposed reason it is special is that boxes of chicken nuggets were sold in units of 6, 9, and 20.”
Now, let’s put on our “thinking caps,” and consider these cute numbers: 6, 9, and 20.
The “thinking caps” work well: There is nothing special about these numbers—it’s just one set of an infinite number of sets that have a Frobenius number.
GA
