Difficult - Combination of two different coin values

Drolenz

New member
Hi,

I am unable to prove the problem described below. I have absolutely no clue as to how this proof should be derived.
The answer is provided in the book, and the question does not really ask that the answer should be proven, but I cannot fathom how the answer can be certain when it's not proven.

Problem:

Imagine that we only had two different types of coins. One coin type with a value of 4 and one coin type with a value of 7.
Examples of amounts that can be paid with these coins:
• 7 (one coin with a value of 7).
• 8 (two coins with a value of 4).
• 9 is not available.
• 10 is not available.
• 11 (one coin with a value of 4 and one with a value of 7).
What is the largest amount we can not pay by using these coins?

Assumptions
• The question only involves whole numbers (only whole numbered coins are available).
• We have access to an endless amount of whole numbered coins of each value.

Where I am at:
I am unable to understand if it is possible to prove the highest amount that can not be paid.
My equation so far is:

4x + 7y = z, where x, y and z are whole positive numbers.

I can test different amounts that can not be paid, but as I cannot test all possible combinations of x and y, I am unable to verify the answer with 100% certainty.

Appreciated any help here!

Jomo

Elite Member
Nice problem!

You can get every multiple of 4, 7, 8, 11, 12, 14, 15, 16, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, ????
From 18 on it *seems* that we can get any number. If this is true then the largest number that you can achieve is 17.

Now you need to show that you can get every number above 17 or find a number which you can get which is above 17.

Otis

Elite Member
… you need to show that you can get every number above 17
Jomo, do you realize that Drolenz already has the answer? They would like help proving that.

or find a number which you can get which is above 17.
I think you meant to say, "which you cannot get".

lev888

Senior Member
Hi,

I am unable to prove the problem described below. I have absolutely no clue as to how this proof should be derived.
The answer is provided in the book, and the question does not really ask that the answer should be proven, but I cannot fathom how the answer can be certain when it's not proven.

Problem:

Imagine that we only had two different types of coins. One coin type with a value of 4 and one coin type with a value of 7.
Examples of amounts that can be paid with these coins:
• 7 (one coin with a value of 7).
• 8 (two coins with a value of 4).
• 9 is not available.
• 10 is not available.
• 11 (one coin with a value of 4 and one with a value of 7).
What is the largest amount we can not pay by using these coins?

Assumptions
• The question only involves whole numbers (only whole numbered coins are available).
• We have access to an endless amount of whole numbered coins of each value.

Where I am at:
I am unable to understand if it is possible to prove the highest amount that can not be paid.
My equation so far is:

4x + 7y = z, where x, y and z are whole positive numbers.

I can test different amounts that can not be paid, but as I cannot test all possible combinations of x and y, I am unable to verify the answer with 100% certainty.

Appreciated any help here!
Look at the post #2. Let's start from 35. Using the 4 coin we can get to 35+4x - every 4th number. If only there was a way to get to 35+4x+1, 35+4x+2, and 35+4x+3...

Jomo

Elite Member
I got all numbers from 18 to 35 inclusive. If you double 18 you get 36. If you add 18 and 19 you get 37. If you double 19 you get 38. If you add 19 and 20 you get 39. Double 20 and get 40. Do you see the pattern?
Jomo, do you realize that Drolenz already has the answer? They would like help proving that.
Yes, I realize that Drolenz has the answer. It was not by accident that I stopped at 35 in my post. Stopping at 35 was a hint.

Dr.Peterson

Elite Member
Where I am at:
I am unable to understand if it is possible to prove the highest amount that can not be paid.
My equation so far is:

4x + 7y = z, where x, y and z are whole positive numbers.

I can test different amounts that can not be paid, but as I cannot test all possible combinations of x and y, I am unable to verify the answer with 100% certainty.

Appreciated any help here!
One approach would be to suppose that you can make some number z = 4x + 7y. Now, can you use that fact to make z+1?For example, if I told you that you can make 48 as 4(5)+7(4), can you make 49 by modifying my 5 and 4?

Now, under what conditions will that trick work?

If you can do this, then you can show that you can make any number greater than some minimal value of z.

By the way, you haven't told us what the book said for the answer. It appears that it just gives a number (whose value we know!) with no explanation? Since this is a great problem to learn from, I'd think they'd do more to help you learn from it!

Please respond, so we can see what to suggest next.

Drolenz

New member
Hi guys,

I thank all of you very much for your responses. It's very motivating to see your eagerness to help

Backdrop:
I was originally helping a friend who is taking night classes (he's in his late 30's), but was stomped by this question popping up in his high school curriculum book. I enquired his teacher for help, but the teacher said this was not at all necessary to understand the exam so he should just ignore it...

First, I did manage to deduce that 17 seemed plausible as I ventured through all the sums from 1-30, and it seemed reasonable that I could reach all sums post 17 (identifying 17 as impossible).

I do not know if it is even possible to prove this, but the answer is indeed 17.

Current status:
I tried to wrap my head around the different comments you all made, and I do understand the logic behind the comments. So thank you all for that

I might be stuck in a wrong thought here, as I tried to reach some sort of conclusions based on your comment by including 18 as a foundation in the equation and working on some additions to that number. But I still can't get any further when I'm basing my thoughts on variations of this equation:

4x + 7y = 18 + z, where z will be any additional number post 18. Though this doesn't get me anywhere, unfortunately.
I thought about the comment z+1, and considered possible ways to prove all increments of 1 work on the equation 4x + 7y = 18 + z, where z could be any number from 18 and upwards. Still nothing.

I believe I am not skilled enough to answer this problem (though I've taken much more advanced math classes than this). Maybe that's why this was so interesting. I presumed I could rush through all the questions on that level easily but was obviously dragged back to reality

Question:
Any ideas on how I should initiate the proof for this?

Further on:

If we get to crack this problem, I'll check with the author of the book for the proof as well. I can't imagine normal high school students taking this course should be able to prove this problem, so would be nice to see if he has a proof available. The teacher of the class does not.

lev888

Senior Member
Hi guys,

I thank all of you very much for your responses. It's very motivating to see your eagerness to help

Backdrop:
I was originally helping a friend who is taking night classes (he's in his late 30's), but was stomped by this question popping up in his high school curriculum book. I enquired his teacher for help, but the teacher said this was not at all necessary to understand the exam so he should just ignore it...

First, I did manage to deduce that 17 seemed plausible as I ventured through all the sums from 1-30, and it seemed reasonable that I could reach all sums post 17 (identifying 17 as impossible).

I do not know if it is even possible to prove this, but the answer is indeed 17.

Current status:
I tried to wrap my head around the different comments you all made, and I do understand the logic behind the comments. So thank you all for that

I might be stuck in a wrong thought here, as I tried to reach some sort of conclusions based on your comment by including 18 as a foundation in the equation and working on some additions to that number. But I still can't get any further when I'm basing my thoughts on variations of this equation:

4x + 7y = 18 + z, where z will be any additional number post 18. Though this doesn't get me anywhere, unfortunately.
I thought about the comment z+1, and considered possible ways to prove all increments of 1 work on the equation 4x + 7y = 18 + z, where z could be any number from 18 and upwards. Still nothing.

I believe I am not skilled enough to answer this problem (though I've taken much more advanced math classes than this). Maybe that's why this was so interesting. I presumed I could rush through all the questions on that level easily but was obviously dragged back to reality

Question:
Any ideas on how I should initiate the proof for this?

Further on:
If we get to crack this problem, I'll check with the author of the book for the proof as well. I can't imagine normal high school students taking this course should be able to prove this problem, so would be nice to see if he has a proof available. The teacher of the class does not.
I don't think you need advanced math to prove this.

You know you can get all numbers up to 35:
..., 30, 31, 32, 33, 34, 35
So, what about 36 and up?

Let's use x to designate all those numbers:
..., 30, 31, 32, 33, 34, 35, x x x x x x x x x x x x x x x ...

As I mentioned before, with the 4 coin we can 'target' every 4th number after 35: 35 + 4n.
Let's use "O" for those numbers:
..., 30, 31, 32, 33, 34, 35, x x x O x x x O x x x O x x x ...

How do we get to the remaining xs using the 4 coin?

Romsek

Senior Member
The idea is that $$\displaystyle v = 4m + 7n$$

We know that the GCF of (4,7)=1 thus any number can be written as $$\displaystyle v=4m+7n$$

The issue is that we can't have negative coins, i.e. $$\displaystyle m,n \geq 0$$

So we are looking for the largest valued combination such that either m or n is -1

Now we also note that given some (m,n), the same value is obtained from (m-7k,n+4k), k=0,1,2, etc. Again provided nothing goes negative.

This bounds what we can set for the non-negative m or n.

If n=-1, we can get 6(4) - 7 = 17
Trying to let m=7 is just equivalent to m=0, n=3

If m=-1, we can get -4+7(3) = 17
Trying to let n=4 is equivalent to (6,0)

So it seems apparent that 17 is the largest value we can't obtain without using negative numbers of coins.

JeffM

Elite Member
Of course as a banker, there really is no integer amount that you cannot spend with such coins. (If I want to pay for something priced at a non-integer value, we must rever to the old-fashioned notion of boot, as in “to boot”). If I want to pay for something priced at 1, I pay with two 4-value coins and receive what I want plus one 7-value coin. If I want to pay for something priced at 2, I pay two 7-value coins and receive what I want plus three 4-value coins.

Any positive integer can be expressed as 4k - 3, 4k - 2, 4k - 1, or 4k.

4k - 3 = 4k + 4 - 7 = 4(k + 1) - 7
4k - 2 = 4k + 12 - 14 = 4(k + 3) - 2 * 7
4k - 1 = 4k + 20 - 21 = 4(k + 5) - 3 * 7
4k, no problem

Some unknown person invented change.

And thus, dearly beloved, did moneychangers come to haunt us.

Jomo

Elite Member
I still like what I did.
I showed that we can obtain all values from 18 to 35.

Since you can get 18, you can get 18+18 = 36
Since you have 18 and 19 you can get 18+19=37
Since you can get 19, you can get 19+19 = 38.
Since you can get 19 and 20, you can get get 19+20 = 39
Since you can get 20, you can get 20+20 = 40.

You can get any even integer 2n>17 by noting that n+n=2n.
You can get any odd integer > 2n+1>17 by noting that (n) + (n+1) = 2n+1
There is more to show but that is the sketch of the proof.

Dr.Peterson

Elite Member
I was originally helping a friend who is taking night classes (he's in his late 30's), but was stomped by this question popping up in his high school curriculum book. I enquired his teacher for help, but the teacher said this was not at all necessary to understand the exam so he should just ignore it...
What topic is this problem attached to? That might suggest what method they expect your friend to use.

But you've been given hints (see #8) that make it so obvious you may be embarrassed when you see it. It doesn't take any particular skill.
If we get to crack this problem, I'll check with the author of the book for the proof as well. I can't imagine normal high school students taking this course should be able to prove this problem, so would be nice to see if he has a proof available. The teacher of the class does not.
This is actually a well-known problem that can be proved in several ways. Since everyone is showing solutions, here is mine (avoiding all advanced ideas):

Suppose we know that z = 4x + 7y. Then since 1 = 4(2) + 7(-1), we can obtain x+1 as 4x + 7y + 4(2) + 7(-1) = 4(x+2) + 7(y-1). That is, we can increase x by 2 and decrease y by 1.

Of course, we can only do that if we can decrease y by 1, so this works only when y > 0. Of course, then to get z+2, we'll need the original y to be at least 2, and similarly for z+3. But we can get z+4 by just increasing x by 1. So once we have a number where y is 3, we can get every subsequent number.

The smallest such number is 4(0) + 7(3) = 21. So every number starting at 21 is obtainable.

On the other hand, though we can't make 17, which is 4(-1) + 7(3), by the same reasoning we can make 18 = 4(1) + 7(2), and then 19 and 20. So we can make anything greater than 17.

Romsek's proof (#9) is just this on steroids.

Drolenz

New member
Thank you all for your excellent contributions and support!

I've managed to understand Jomo's answer, but I am not certain what is missing after my conclusions below.
JeffM, Romsek's and Dr.Petersons answers I have to review some more, as I don't understand 100% how I should construct the proof based on these inputs. Specifically, the introduction of the negative value in the equations makes me somewhat baffled.

"What topic is this problem attached to? That might suggest what method they expect your friend to use ."
It's algebra in upper secondary school / high school. But it's related to the improvement of grades as an adult because some of these courses are required for entry to university/college.

My friend's teacher literally told him to not dwell too much into this, rather just ignore it completely as it is not relevant for the requirements he is up against in his upcoming exam. No clarification or support was provided.

This didn't sit well with me, as my curiosity when providing him help got the better of me. So any answer/proof that I understand is OK

Also, thanks for the link to https://en.wikipedia.org/wiki/Coin_problem.
I will read more upon this! Wasn't aware that this was a well-known problem.

My understanding of the proof so far:

Initial equation:
4x + 7y = z

Assumptions:
x, y >= 0 and in the domain of real, rational numbers.

Steps:
We can manually calculate all sums from 1 to and including 35.
These numbers can't be attained in that range of numbers.
• 1, 2, 3, 5, 6, 9, 10, 13, 17
All existing sums above 35 can be calculated with a combination of the numbers from 18 to and including 35.

If 18 <= n <= 35,

Any even integer z = k*n > 17, where k is an even number can be reached.
Any even integer z = k*n+1 > 17, where k is an even number can be reached.

Jomo

Elite Member
You should look at post #8 by lev888 as I think he nailed this problem.
He showed which numbers can be obtained from numbers of the form 35+4n. Now think about which numbers will be included in 34+4n, and 33 + 4n and finally 32+4n.

Jomo

Elite Member
I don't think you need advanced math to prove this.

You know you can get all numbers up to 35:
..., 30, 31, 32, 33, 34, 35
So, what about 36 and up?

Let's use x to designate all those numbers:
..., 30, 31, 32, 33, 34, 35, x x x x x x x x x x x x x x x ...

As I mentioned before, with the 4 coin we can 'target' every 4th number after 35: 35 + 4n.
Let's use "O" for those numbers:
..., 30, 31, 32, 33, 34, 35, x x x O x x x O x x x O x x x ...

How do we get to the remaining xs using the 4 coin?
Lev, I'll be honest and say that I thought my method was the best of all that was posted. However, after reading your post again I can see that you nailed this problem and it was done with elegance. Good job!!

lev888

Senior Member
Lev, I'll be honest and say that I thought my method was the best of all that was posted. However, after reading your post again I can see that you nailed this problem and it was done with elegance. Good job!!
Thanks!