Mixing
Need help finding maximum unpayable amount between two coins of values 5 and 7, and understanding why.
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I am currently taking in introduction course to Discrete mathematics, and came across this problem:
Imagine we have only 5- and 7-coins. One can prove that any large enough integer amount can be paid using only such coins. Yet clearly we cannot pay any of numbers 1, 2, 3, 4, 6, 8, 9 with our coins. What is the maximum amount that cannot be paid?
I am a bit stuck, I was told that the solution was simple enough and didn't require programming ( the course also is a crash course in Python) but I don't see any method that was presented in the lectures for arriving at the answer.
How would I do it, and more importantly what should I take away for future similar problems?
discrete-mathematics
edited Jul 21 at 11:22
Parcly Taxel
33.6k136588
asked Jul 21 at 10:58
Brandonbury
61
add a comment |Â
up vote
1
down vote
favorite
I am currently taking in introduction course to Discrete mathematics, and came across this problem:
Imagine we have only 5- and 7-coins. One can prove that any large enough integer amount can be paid using only such coins. Yet clearly we cannot pay any of numbers 1, 2, 3, 4, 6, 8, 9 with our coins. What is the maximum amount that cannot be paid?
I am a bit stuck, I was told that the solution was simple enough and didn't require programming ( the course also is a crash course in Python) but I don't see any method that was presented in the lectures for arriving at the answer.
How would I do it, and more importantly what should I take away for future similar problems?
discrete-mathematics
edited Jul 21 at 11:22
Parcly Taxel
33.6k136588
asked Jul 21 at 10:58
Brandonbury
61
Note that the title does not match the question. The question is about the maximum amount that cannot be paid. There is no "maximum payable amount."
– David K
Jul 21 at 11:09
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I am currently taking in introduction course to Discrete mathematics, and came across this problem:
Imagine we have only 5- and 7-coins. One can prove that any large enough integer amount can be paid using only such coins. Yet clearly we cannot pay any of numbers 1, 2, 3, 4, 6, 8, 9 with our coins. What is the maximum amount that cannot be paid?
I am a bit stuck, I was told that the solution was simple enough and didn't require programming ( the course also is a crash course in Python) but I don't see any method that was presented in the lectures for arriving at the answer.
How would I do it, and more importantly what should I take away for future similar problems?
discrete-mathematics
edited Jul 21 at 11:22
Parcly Taxel
33.6k136588
asked Jul 21 at 10:58
Brandonbury
61
I am currently taking in introduction course to Discrete mathematics, and came across this problem:
Imagine we have only 5- and 7-coins. One can prove that any large enough integer amount can be paid using only such coins. Yet clearly we cannot pay any of numbers 1, 2, 3, 4, 6, 8, 9 with our coins. What is the maximum amount that cannot be paid?
I am a bit stuck, I was told that the solution was simple enough and didn't require programming ( the course also is a crash course in Python) but I don't see any method that was presented in the lectures for arriving at the answer.
How would I do it, and more importantly what should I take away for future similar problems?
discrete-mathematics
edited Jul 21 at 11:22
Parcly Taxel
33.6k136588
asked Jul 21 at 10:58
Brandonbury
61
edited Jul 21 at 11:22
Parcly Taxel
33.6k136588
edited Jul 21 at 11:22
Parcly Taxel
33.6k136588
edited Jul 21 at 11:22
Parcly Taxel
33.6k136588
33.6k136588
asked Jul 21 at 10:58
Brandonbury
61
asked Jul 21 at 10:58
Brandonbury
61
asked Jul 21 at 10:58
Brandonbury
61
61
Note that the title does not match the question. The question is about the maximum amount that cannot be paid. There is no "maximum payable amount."
– David K
Jul 21 at 11:09
add a comment |Â
Note that the title does not match the question. The question is about the maximum amount that cannot be paid. There is no "maximum payable amount."
– David K
Jul 21 at 11:09
Note that the title does not match the question. The question is about the maximum amount that cannot be paid. There is no "maximum payable amount."
– David K
Jul 21 at 11:09
Note that the title does not match the question. The question is about the maximum amount that cannot be paid. There is no "maximum payable amount."
– David K
Jul 21 at 11:09
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
3
down vote
The maximum unpayable amount is 23. That higher numbers are payable comes from the following representations:
$$24=5+5+7+7$$
$$25=5+5+5+5+5$$
$$26=7+7+7+5$$
$$27=5+5+5+5+7$$
$$28=7+7+7+7$$
with the rest formed by adding 5s to these. That 23 cannot be formed can be seen by repeatedly subtracting 7 from it – 16, 9, 2, $-5$ – and noting that no nonnegative multiple of 5 appears.
This is sometimes known as Sylvester's coin problem. The largest unpayable amount from coins of value $a$ and $b$, when they are coprime, is $ab-a-b$. The takeaway from this, I think, would be that it is always good to try small examples as part of the problem solving process, so as to get a feel of what the problem's conditions and boundaries are.
answered Jul 21 at 11:21
Parcly Taxel
33.6k136588
add a comment |Â
up vote
0
down vote
Parcly Taxel has already given a good answer for your specific question, but, since your title also said "understanding why", let me explain a way to think about this. The following idea works in general to prove Sylvester's $ab-a-b$ result, but I'll describe it in your specific situation.
Think of the positive integers in blocks of 5 consecutive numbers. In the first block $1,2,3,4,5$, the only payable amount is the last element, 5. As a result, in all subsequent blocks, the last element will be payable, just by using more 5-coins. In the second block, $6,7,8,9,10$, you get, in addition to the last element 10 that we already know is payable, one more payable element, 7. As a result, in all subsequent blocks, the second element will be payable, just by using more 5-coins. In the third block, $11,12,13,14,15$, in addition to the second and last elements that we already know are payable, we get one more payable element, 14. So in all later blocks, the second, fourth, and last elements will be payable. The fourth block gets us no new payable elements (because there's no multiple of 7 in that block), but the fifth block gets us the new payable element 21. So in all subsequent blocks, all elements but the third will be payable. In the 6th block, we get the new payable number 28, the third number in that block. So from the sixth block on, everything is payable. The last block with an unpayable element is therefore the fifth block, and its only unpayable element is the third element, 23.
You might check what happens in the analogous calculation with blocks of 7 instead of blocks of 5. You'll find that sometimes a block gets two new payable elements, which didn't happen with blocks of 5, but the process still leads you to the correct answer 23.
answered Jul 21 at 14:43
Andreas Blass
47.6k348104
add a comment |Â
up vote
0
down vote
This is an instance of the Frobenius coin problem. Given two positive integers $x$, $y$ with $rm gcd(x,y)=1$ the largest amount that cannot be paid with $x$- and $y$-coins is given by
$$N=x y-x-y .$$
The proof is not too difficult: With $x$-coins alone you can do all sums having remainder $0$ mod $x$. One $y$-coin gives you access to a new remainder mod $x$, two $y$-coins access to a second remainder mod $x$, and so on. It follows that you need $x-1$ of the $y$-coins in order to have access to all remainders mod $x$. These $x-1$ coins make up the amount $N':=(x-1)y$. The last inaccessible amount is then obtained by subtracting $x$ from $N'$, whence we are lead to the $N$ given above.
answered Jul 21 at 15:13
Christian Blatter
163k7107306
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
The maximum unpayable amount is 23. That higher numbers are payable comes from the following representations:
$$24=5+5+7+7$$
$$25=5+5+5+5+5$$
$$26=7+7+7+5$$
$$27=5+5+5+5+7$$
$$28=7+7+7+7$$
with the rest formed by adding 5s to these. That 23 cannot be formed can be seen by repeatedly subtracting 7 from it – 16, 9, 2, $-5$ – and noting that no nonnegative multiple of 5 appears.
This is sometimes known as Sylvester's coin problem. The largest unpayable amount from coins of value $a$ and $b$, when they are coprime, is $ab-a-b$. The takeaway from this, I think, would be that it is always good to try small examples as part of the problem solving process, so as to get a feel of what the problem's conditions and boundaries are.
answered Jul 21 at 11:21
Parcly Taxel
33.6k136588
add a comment |Â
up vote
3
down vote
The maximum unpayable amount is 23. That higher numbers are payable comes from the following representations:
$$24=5+5+7+7$$
$$25=5+5+5+5+5$$
$$26=7+7+7+5$$
$$27=5+5+5+5+7$$
$$28=7+7+7+7$$
with the rest formed by adding 5s to these. That 23 cannot be formed can be seen by repeatedly subtracting 7 from it – 16, 9, 2, $-5$ – and noting that no nonnegative multiple of 5 appears.
This is sometimes known as Sylvester's coin problem. The largest unpayable amount from coins of value $a$ and $b$, when they are coprime, is $ab-a-b$. The takeaway from this, I think, would be that it is always good to try small examples as part of the problem solving process, so as to get a feel of what the problem's conditions and boundaries are.
answered Jul 21 at 11:21
Parcly Taxel
33.6k136588
add a comment |Â
up vote
3
down vote
up vote
3
down vote
The maximum unpayable amount is 23. That higher numbers are payable comes from the following representations:
$$24=5+5+7+7$$
$$25=5+5+5+5+5$$
$$26=7+7+7+5$$
$$27=5+5+5+5+7$$
$$28=7+7+7+7$$
with the rest formed by adding 5s to these. That 23 cannot be formed can be seen by repeatedly subtracting 7 from it – 16, 9, 2, $-5$ – and noting that no nonnegative multiple of 5 appears.
This is sometimes known as Sylvester's coin problem. The largest unpayable amount from coins of value $a$ and $b$, when they are coprime, is $ab-a-b$. The takeaway from this, I think, would be that it is always good to try small examples as part of the problem solving process, so as to get a feel of what the problem's conditions and boundaries are.
answered Jul 21 at 11:21
Parcly Taxel
33.6k136588
The maximum unpayable amount is 23. That higher numbers are payable comes from the following representations:
$$24=5+5+7+7$$
$$25=5+5+5+5+5$$
$$26=7+7+7+5$$
$$27=5+5+5+5+7$$
$$28=7+7+7+7$$
with the rest formed by adding 5s to these. That 23 cannot be formed can be seen by repeatedly subtracting 7 from it – 16, 9, 2, $-5$ – and noting that no nonnegative multiple of 5 appears.
This is sometimes known as Sylvester's coin problem. The largest unpayable amount from coins of value $a$ and $b$, when they are coprime, is $ab-a-b$. The takeaway from this, I think, would be that it is always good to try small examples as part of the problem solving process, so as to get a feel of what the problem's conditions and boundaries are.
answered Jul 21 at 11:21
Parcly Taxel
33.6k136588
answered Jul 21 at 11:21
Parcly Taxel
33.6k136588
answered Jul 21 at 11:21
Parcly Taxel
33.6k136588
answered Jul 21 at 11:21
Parcly Taxel
33.6k136588
33.6k136588
add a comment |Â
add a comment |Â
up vote
0
down vote
Parcly Taxel has already given a good answer for your specific question, but, since your title also said "understanding why", let me explain a way to think about this. The following idea works in general to prove Sylvester's $ab-a-b$ result, but I'll describe it in your specific situation.
Think of the positive integers in blocks of 5 consecutive numbers. In the first block $1,2,3,4,5$, the only payable amount is the last element, 5. As a result, in all subsequent blocks, the last element will be payable, just by using more 5-coins. In the second block, $6,7,8,9,10$, you get, in addition to the last element 10 that we already know is payable, one more payable element, 7. As a result, in all subsequent blocks, the second element will be payable, just by using more 5-coins. In the third block, $11,12,13,14,15$, in addition to the second and last elements that we already know are payable, we get one more payable element, 14. So in all later blocks, the second, fourth, and last elements will be payable. The fourth block gets us no new payable elements (because there's no multiple of 7 in that block), but the fifth block gets us the new payable element 21. So in all subsequent blocks, all elements but the third will be payable. In the 6th block, we get the new payable number 28, the third number in that block. So from the sixth block on, everything is payable. The last block with an unpayable element is therefore the fifth block, and its only unpayable element is the third element, 23.
You might check what happens in the analogous calculation with blocks of 7 instead of blocks of 5. You'll find that sometimes a block gets two new payable elements, which didn't happen with blocks of 5, but the process still leads you to the correct answer 23.
answered Jul 21 at 14:43
Andreas Blass
47.6k348104
add a comment |Â
up vote
0
down vote
Parcly Taxel has already given a good answer for your specific question, but, since your title also said "understanding why", let me explain a way to think about this. The following idea works in general to prove Sylvester's $ab-a-b$ result, but I'll describe it in your specific situation.
Think of the positive integers in blocks of 5 consecutive numbers. In the first block $1,2,3,4,5$, the only payable amount is the last element, 5. As a result, in all subsequent blocks, the last element will be payable, just by using more 5-coins. In the second block, $6,7,8,9,10$, you get, in addition to the last element 10 that we already know is payable, one more payable element, 7. As a result, in all subsequent blocks, the second element will be payable, just by using more 5-coins. In the third block, $11,12,13,14,15$, in addition to the second and last elements that we already know are payable, we get one more payable element, 14. So in all later blocks, the second, fourth, and last elements will be payable. The fourth block gets us no new payable elements (because there's no multiple of 7 in that block), but the fifth block gets us the new payable element 21. So in all subsequent blocks, all elements but the third will be payable. In the 6th block, we get the new payable number 28, the third number in that block. So from the sixth block on, everything is payable. The last block with an unpayable element is therefore the fifth block, and its only unpayable element is the third element, 23.
You might check what happens in the analogous calculation with blocks of 7 instead of blocks of 5. You'll find that sometimes a block gets two new payable elements, which didn't happen with blocks of 5, but the process still leads you to the correct answer 23.
answered Jul 21 at 14:43
Andreas Blass
47.6k348104
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Parcly Taxel has already given a good answer for your specific question, but, since your title also said "understanding why", let me explain a way to think about this. The following idea works in general to prove Sylvester's $ab-a-b$ result, but I'll describe it in your specific situation.
Think of the positive integers in blocks of 5 consecutive numbers. In the first block $1,2,3,4,5$, the only payable amount is the last element, 5. As a result, in all subsequent blocks, the last element will be payable, just by using more 5-coins. In the second block, $6,7,8,9,10$, you get, in addition to the last element 10 that we already know is payable, one more payable element, 7. As a result, in all subsequent blocks, the second element will be payable, just by using more 5-coins. In the third block, $11,12,13,14,15$, in addition to the second and last elements that we already know are payable, we get one more payable element, 14. So in all later blocks, the second, fourth, and last elements will be payable. The fourth block gets us no new payable elements (because there's no multiple of 7 in that block), but the fifth block gets us the new payable element 21. So in all subsequent blocks, all elements but the third will be payable. In the 6th block, we get the new payable number 28, the third number in that block. So from the sixth block on, everything is payable. The last block with an unpayable element is therefore the fifth block, and its only unpayable element is the third element, 23.
You might check what happens in the analogous calculation with blocks of 7 instead of blocks of 5. You'll find that sometimes a block gets two new payable elements, which didn't happen with blocks of 5, but the process still leads you to the correct answer 23.
answered Jul 21 at 14:43
Andreas Blass
47.6k348104
Parcly Taxel has already given a good answer for your specific question, but, since your title also said "understanding why", let me explain a way to think about this. The following idea works in general to prove Sylvester's $ab-a-b$ result, but I'll describe it in your specific situation.
Think of the positive integers in blocks of 5 consecutive numbers. In the first block $1,2,3,4,5$, the only payable amount is the last element, 5. As a result, in all subsequent blocks, the last element will be payable, just by using more 5-coins. In the second block, $6,7,8,9,10$, you get, in addition to the last element 10 that we already know is payable, one more payable element, 7. As a result, in all subsequent blocks, the second element will be payable, just by using more 5-coins. In the third block, $11,12,13,14,15$, in addition to the second and last elements that we already know are payable, we get one more payable element, 14. So in all later blocks, the second, fourth, and last elements will be payable. The fourth block gets us no new payable elements (because there's no multiple of 7 in that block), but the fifth block gets us the new payable element 21. So in all subsequent blocks, all elements but the third will be payable. In the 6th block, we get the new payable number 28, the third number in that block. So from the sixth block on, everything is payable. The last block with an unpayable element is therefore the fifth block, and its only unpayable element is the third element, 23.
You might check what happens in the analogous calculation with blocks of 7 instead of blocks of 5. You'll find that sometimes a block gets two new payable elements, which didn't happen with blocks of 5, but the process still leads you to the correct answer 23.
answered Jul 21 at 14:43
Andreas Blass
47.6k348104
answered Jul 21 at 14:43
Andreas Blass
47.6k348104
answered Jul 21 at 14:43
Andreas Blass
47.6k348104
answered Jul 21 at 14:43
Andreas Blass
47.6k348104
47.6k348104
add a comment |Â
add a comment |Â
up vote
0
down vote
This is an instance of the Frobenius coin problem. Given two positive integers $x$, $y$ with $rm gcd(x,y)=1$ the largest amount that cannot be paid with $x$- and $y$-coins is given by
$$N=x y-x-y .$$
The proof is not too difficult: With $x$-coins alone you can do all sums having remainder $0$ mod $x$. One $y$-coin gives you access to a new remainder mod $x$, two $y$-coins access to a second remainder mod $x$, and so on. It follows that you need $x-1$ of the $y$-coins in order to have access to all remainders mod $x$. These $x-1$ coins make up the amount $N':=(x-1)y$. The last inaccessible amount is then obtained by subtracting $x$ from $N'$, whence we are lead to the $N$ given above.
answered Jul 21 at 15:13
Christian Blatter
163k7107306
add a comment |Â
up vote
0
down vote
This is an instance of the Frobenius coin problem. Given two positive integers $x$, $y$ with $rm gcd(x,y)=1$ the largest amount that cannot be paid with $x$- and $y$-coins is given by
$$N=x y-x-y .$$
The proof is not too difficult: With $x$-coins alone you can do all sums having remainder $0$ mod $x$. One $y$-coin gives you access to a new remainder mod $x$, two $y$-coins access to a second remainder mod $x$, and so on. It follows that you need $x-1$ of the $y$-coins in order to have access to all remainders mod $x$. These $x-1$ coins make up the amount $N':=(x-1)y$. The last inaccessible amount is then obtained by subtracting $x$ from $N'$, whence we are lead to the $N$ given above.
answered Jul 21 at 15:13
Christian Blatter
163k7107306
add a comment |Â
up vote
0
down vote
up vote
0
down vote
This is an instance of the Frobenius coin problem. Given two positive integers $x$, $y$ with $rm gcd(x,y)=1$ the largest amount that cannot be paid with $x$- and $y$-coins is given by
$$N=x y-x-y .$$
The proof is not too difficult: With $x$-coins alone you can do all sums having remainder $0$ mod $x$. One $y$-coin gives you access to a new remainder mod $x$, two $y$-coins access to a second remainder mod $x$, and so on. It follows that you need $x-1$ of the $y$-coins in order to have access to all remainders mod $x$. These $x-1$ coins make up the amount $N':=(x-1)y$. The last inaccessible amount is then obtained by subtracting $x$ from $N'$, whence we are lead to the $N$ given above.
answered Jul 21 at 15:13
Christian Blatter
163k7107306
This is an instance of the Frobenius coin problem. Given two positive integers $x$, $y$ with $rm gcd(x,y)=1$ the largest amount that cannot be paid with $x$- and $y$-coins is given by
$$N=x y-x-y .$$
The proof is not too difficult: With $x$-coins alone you can do all sums having remainder $0$ mod $x$. One $y$-coin gives you access to a new remainder mod $x$, two $y$-coins access to a second remainder mod $x$, and so on. It follows that you need $x-1$ of the $y$-coins in order to have access to all remainders mod $x$. These $x-1$ coins make up the amount $N':=(x-1)y$. The last inaccessible amount is then obtained by subtracting $x$ from $N'$, whence we are lead to the $N$ given above.
answered Jul 21 at 15:13
Christian Blatter
163k7107306
answered Jul 21 at 15:13
Christian Blatter
163k7107306
answered Jul 21 at 15:13
Christian Blatter
163k7107306
answered Jul 21 at 15:13
Christian Blatter
163k7107306
163k7107306
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2858406%2fneed-help-finding-maximum-unpayable-amount-between-two-coins-of-values-5-and-7%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Note that the title does not match the question. The question is about the maximum amount that cannot be paid. There is no "maximum payable amount."
– David K
Jul 21 at 11:09