Questions   
Sort: 
May 4, 2018
 #9
avatar
+2

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

May 4, 2018

1 Online Users