Three coins for the fair king [duplicate]
$begingroup$
This question already has an answer here:
Eight coins for the fair king
6 answers
Based on the question Eight coins for the fair king:
I saw a comment saying "There isn't a good solution known even with three coins in all cases".
So the challenge here is to try to solve the same problem placed above, except with only 3 coins.
The rules are:
You must create 3 coins of different value, no more.
Any sum of money must be paid with only 3 coins. This sum should be paid without giving change.
You must set N such that no price is allowed to be greater than N.
I've tried to solve it myself and the best combination I could get to was
Coins of
1,2and5, which can get me to a maximum of N = 12.
The highest number that follows the rules wins, and if there's proof that it's definitely the highest answer possible, it gets the tick.
Note: You may only use up to 3 coins to pay every amount, rather than 8.
mathematics combinatorics optimization open-ended
asked Dec 27 '18 at 14:23
S. M.S. M.
953419
$endgroup$
marked as duplicate by Glorfindel, Chowzen, athin, JonMark Perry, n_palum Dec 28 '18 at 13:52
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Eight coins for the fair king
6 answers
Based on the question Eight coins for the fair king:
I saw a comment saying "There isn't a good solution known even with three coins in all cases".
So the challenge here is to try to solve the same problem placed above, except with only 3 coins.
The rules are:
You must create 3 coins of different value, no more.
Any sum of money must be paid with only 3 coins. This sum should be paid without giving change.
You must set N such that no price is allowed to be greater than N.
I've tried to solve it myself and the best combination I could get to was
Coins of
1,2and5, which can get me to a maximum of N = 12.
The highest number that follows the rules wins, and if there's proof that it's definitely the highest answer possible, it gets the tick.
Note: You may only use up to 3 coins to pay every amount, rather than 8.
mathematics combinatorics optimization open-ended
asked Dec 27 '18 at 14:23
S. M.S. M.
953419
$endgroup$
marked as duplicate by Glorfindel, Chowzen, athin, JonMark Perry, n_palum Dec 28 '18 at 13:52
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
4
$begingroup$
Can you repeat the context of the original problem here? Relying on a link to maintain that context isn't the best idea.
$endgroup$
– THiebert
Dec 27 '18 at 19:28
$begingroup$
It's different in the way that this one is simple enough that you can solve it without using a computer, so it does change a bit on the dynamics of the problem.
$endgroup$
– S. M.
Dec 28 '18 at 9:07
$begingroup$
@THiebert Added the rules from the original post.
$endgroup$
– S. M.
Dec 28 '18 at 10:37
add a comment |
$begingroup$
This question already has an answer here:
Eight coins for the fair king
6 answers
Based on the question Eight coins for the fair king:
I saw a comment saying "There isn't a good solution known even with three coins in all cases".
So the challenge here is to try to solve the same problem placed above, except with only 3 coins.
The rules are:
You must create 3 coins of different value, no more.
Any sum of money must be paid with only 3 coins. This sum should be paid without giving change.
You must set N such that no price is allowed to be greater than N.
I've tried to solve it myself and the best combination I could get to was
Coins of
1,2and5, which can get me to a maximum of N = 12.
The highest number that follows the rules wins, and if there's proof that it's definitely the highest answer possible, it gets the tick.
Note: You may only use up to 3 coins to pay every amount, rather than 8.
mathematics combinatorics optimization open-ended
asked Dec 27 '18 at 14:23
S. M.S. M.
953419
$endgroup$
This question already has an answer here:
Eight coins for the fair king
6 answers
Based on the question Eight coins for the fair king:
I saw a comment saying "There isn't a good solution known even with three coins in all cases".
So the challenge here is to try to solve the same problem placed above, except with only 3 coins.
The rules are:
You must create 3 coins of different value, no more.
Any sum of money must be paid with only 3 coins. This sum should be paid without giving change.
You must set N such that no price is allowed to be greater than N.
I've tried to solve it myself and the best combination I could get to was
Coins of
1,2and5, which can get me to a maximum of N = 12.
The highest number that follows the rules wins, and if there's proof that it's definitely the highest answer possible, it gets the tick.
Note: You may only use up to 3 coins to pay every amount, rather than 8.
This question already has an answer here:
Eight coins for the fair king
6 answers
mathematics combinatorics optimization open-ended
mathematics combinatorics optimization open-ended
asked Dec 27 '18 at 14:23
S. M.S. M.
953419
asked Dec 27 '18 at 14:23
S. M.S. M.
953419
edited Dec 28 '18 at 10:37
S. M.
asked Dec 27 '18 at 14:23
S. M.S. M.
953419
asked Dec 27 '18 at 14:23
S. M.S. M.
953419
asked Dec 27 '18 at 14:23
S. M.S. M.
953419
953419
marked as duplicate by Glorfindel, Chowzen, athin, JonMark Perry, n_palum Dec 28 '18 at 13:52
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Glorfindel, Chowzen, athin, JonMark Perry, n_palum Dec 28 '18 at 13:52
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
4
$begingroup$
Can you repeat the context of the original problem here? Relying on a link to maintain that context isn't the best idea.
$endgroup$
– THiebert
Dec 27 '18 at 19:28
$begingroup$
It's different in the way that this one is simple enough that you can solve it without using a computer, so it does change a bit on the dynamics of the problem.
$endgroup$
– S. M.
Dec 28 '18 at 9:07
$begingroup$
@THiebert Added the rules from the original post.
$endgroup$
– S. M.
Dec 28 '18 at 10:37
add a comment |
4
$begingroup$
Can you repeat the context of the original problem here? Relying on a link to maintain that context isn't the best idea.
$endgroup$
– THiebert
Dec 27 '18 at 19:28
$begingroup$
It's different in the way that this one is simple enough that you can solve it without using a computer, so it does change a bit on the dynamics of the problem.
$endgroup$
– S. M.
Dec 28 '18 at 9:07
$begingroup$
@THiebert Added the rules from the original post.
$endgroup$
– S. M.
Dec 28 '18 at 10:37
4
4
$begingroup$
Can you repeat the context of the original problem here? Relying on a link to maintain that context isn't the best idea.
$endgroup$
– THiebert
Dec 27 '18 at 19:28
$begingroup$
Can you repeat the context of the original problem here? Relying on a link to maintain that context isn't the best idea.
$endgroup$
– THiebert
Dec 27 '18 at 19:28
$begingroup$
It's different in the way that this one is simple enough that you can solve it without using a computer, so it does change a bit on the dynamics of the problem.
$endgroup$
– S. M.
Dec 28 '18 at 9:07
$begingroup$
It's different in the way that this one is simple enough that you can solve it without using a computer, so it does change a bit on the dynamics of the problem.
$endgroup$
– S. M.
Dec 28 '18 at 9:07
$begingroup$
@THiebert Added the rules from the original post.
$endgroup$
– S. M.
Dec 28 '18 at 10:37
$begingroup$
@THiebert Added the rules from the original post.
$endgroup$
– S. M.
Dec 28 '18 at 10:37
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Fact 1:
There must be a $1 coin
Fact 2:
2nd-value coin <=4, else would overflow
Proof:
Exhaustion...
Maximizing possibilities:
Notation: (x,y,z) : highest possible value
Possibility 1: (1,2,?)
(1,2,3):9
(1,2,4):10
(1,2,5):12(@S.M. in question)
(1,2,6):10
(1,2,7):11
(1,2,8+):7
For (1,2,?), (1,2,5):12=greatest
Possibility 2: (1,3,?)
(1,3,4):12
(1,3,5):11
(1,3,6):10
(1,3,7):11
(1,3,8):12
(1,3,9+):7
For (1,3,?), (1,3,8):12=greatest
Possibility 3: (1,4,?)
(1,4,5):15(Credits to @M)
(1,4,6):13
(1,4,7):9
(1,4,8+):6
For (1,4,?), (1,4,5):15=greatest
Overall:
(1,4,5):15=greatest
answered Dec 27 '18 at 15:19
Omega KryptonOmega Krypton
4,0851338
$endgroup$
$begingroup$
This is basically a properly organized version of the scribbles I made trying to figure it out (plus you found an extra answer). The explanation is very straight-forward and seems correct, so I'll attribute it a tick.
$endgroup$
– S. M.
Dec 27 '18 at 15:23
$begingroup$
Man, there was a lot I didn't see either, my bad. xD Still think it's the best explained answer and with further edits will get to the best answer.
$endgroup$
– S. M.
Dec 27 '18 at 15:33
1
$begingroup$
Fact 3 is not a true statement. 1,2,7 can generate all values up to 11 (not the best, but still...).
$endgroup$
– asgallant
Dec 27 '18 at 22:29
add a comment |
$begingroup$
Anders Kaseorg's answer on the 8/8 list has the most optimal N/N answers up to N = 7 in a spoiler. And he has...
{1, 4, 5}
With a little enumeration, it's easy to see that you can use that set to get up to...
15.
EDIT
It's actually pretty simple to reason this out without brute forcing it (too much).
Say you have three denominations of coins - A, B, and C. Then clearly one of them has to be worth #1, or else you can't pay for things that are worth #1. So let's let A be worth #1. Now, assuming that C is the most valuable form of coinage, the most you can pay is #3C.
However, what if you want to pay #3C-1? We can safely assume that you'd have to use either 2C+A or 2C+B. But if you can use A, then C would have to be worth #2, which you can rule out with some quick figuring ({1,2,3} can get you #9, which {1, 1 < n < 2, 2} can't). So you're left with B being C-1.
As a result, you only need to check triples of the form {1, N, N+1}, where N can be at most 4.
answered Dec 27 '18 at 15:31
M DirrM Dirr
712
$endgroup$
$begingroup$
"The most you can pay is 3C". What if i choose {A,B,D} with D > C, but i can't pay 3D-1. The most i can pay is 3D-2 > 3C, which still makes it a better solution? The answer is correct, but the logic at the end is flawed
$endgroup$
– Tibos
Dec 29 '18 at 10:42
$begingroup$
There are only three denominations of coins, so in that case C = D. The logic is actually flawed (it doesn't work if you can't reach 3C, for one), but that's not why.
$endgroup$
– M Dirr
Dec 31 '18 at 14:32
$begingroup$
Perhaps my explanation of the problem with only checking {1, X, X+1} triplets was weirdly framed, let me give it another try. By putting the constraint C = B+1 you are limiting the value of C. Let's call mC that highest C achievable with your constraint. What you have not proven (and is in fact false) is that by choosing values for C higher than mC you will get a max that is lower than 3mC. Case in point: {1,2,3} => 9 while {1,2,6} => 10.
$endgroup$
– Tibos
Jan 1 at 14:40
1
$begingroup$
That is true - my issue is that my logic went "clearly the highest you can possibly get is 3C", made the false assumption that the best possible solution required you to reach 3C (it happens to be true in this case, but it doesn't generally hold), and then back-figured from there.
$endgroup$
– M Dirr
Jan 4 at 16:23
add a comment |
$begingroup$
This is a little bit (read: a lot bit) of trickery, but
I can get up to 44 with coins of -1, 1, 10. The -1 helps because it allows you to get a units digit of 6 through 9.
I can't prove this is optimal, but it's a start (and I'm not sure if this is even good for the kingdom to have this type of coin :P)
answered Dec 27 '18 at 14:27
Excited RaichuExcited Raichu
6,51521166
$endgroup$
$begingroup$
I do think he means it as 3/3 problem, not a 3/8 problem
$endgroup$
– Thomas Blue
Dec 27 '18 at 14:30
$begingroup$
Yes, I mean it as a 3/3 problem, I'll specify it in the post just in case :p Very out-of-the-box answer though!
$endgroup$
– S. M.
Dec 27 '18 at 14:31
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Fact 1:
There must be a $1 coin
Fact 2:
2nd-value coin <=4, else would overflow
Proof:
Exhaustion...
Maximizing possibilities:
Notation: (x,y,z) : highest possible value
Possibility 1: (1,2,?)
(1,2,3):9
(1,2,4):10
(1,2,5):12(@S.M. in question)
(1,2,6):10
(1,2,7):11
(1,2,8+):7
For (1,2,?), (1,2,5):12=greatest
Possibility 2: (1,3,?)
(1,3,4):12
(1,3,5):11
(1,3,6):10
(1,3,7):11
(1,3,8):12
(1,3,9+):7
For (1,3,?), (1,3,8):12=greatest
Possibility 3: (1,4,?)
(1,4,5):15(Credits to @M)
(1,4,6):13
(1,4,7):9
(1,4,8+):6
For (1,4,?), (1,4,5):15=greatest
Overall:
(1,4,5):15=greatest
answered Dec 27 '18 at 15:19
Omega KryptonOmega Krypton
4,0851338
$endgroup$
$begingroup$
This is basically a properly organized version of the scribbles I made trying to figure it out (plus you found an extra answer). The explanation is very straight-forward and seems correct, so I'll attribute it a tick.
$endgroup$
– S. M.
Dec 27 '18 at 15:23
$begingroup$
Man, there was a lot I didn't see either, my bad. xD Still think it's the best explained answer and with further edits will get to the best answer.
$endgroup$
– S. M.
Dec 27 '18 at 15:33
1
$begingroup$
Fact 3 is not a true statement. 1,2,7 can generate all values up to 11 (not the best, but still...).
$endgroup$
– asgallant
Dec 27 '18 at 22:29
add a comment |
$begingroup$
Fact 1:
There must be a $1 coin
Fact 2:
2nd-value coin <=4, else would overflow
Proof:
Exhaustion...
Maximizing possibilities:
Notation: (x,y,z) : highest possible value
Possibility 1: (1,2,?)
(1,2,3):9
(1,2,4):10
(1,2,5):12(@S.M. in question)
(1,2,6):10
(1,2,7):11
(1,2,8+):7
For (1,2,?), (1,2,5):12=greatest
Possibility 2: (1,3,?)
(1,3,4):12
(1,3,5):11
(1,3,6):10
(1,3,7):11
(1,3,8):12
(1,3,9+):7
For (1,3,?), (1,3,8):12=greatest
Possibility 3: (1,4,?)
(1,4,5):15(Credits to @M)
(1,4,6):13
(1,4,7):9
(1,4,8+):6
For (1,4,?), (1,4,5):15=greatest
Overall:
(1,4,5):15=greatest
answered Dec 27 '18 at 15:19
Omega KryptonOmega Krypton
4,0851338
$endgroup$
$begingroup$
This is basically a properly organized version of the scribbles I made trying to figure it out (plus you found an extra answer). The explanation is very straight-forward and seems correct, so I'll attribute it a tick.
$endgroup$
– S. M.
Dec 27 '18 at 15:23
$begingroup$
Man, there was a lot I didn't see either, my bad. xD Still think it's the best explained answer and with further edits will get to the best answer.
$endgroup$
– S. M.
Dec 27 '18 at 15:33
1
$begingroup$
Fact 3 is not a true statement. 1,2,7 can generate all values up to 11 (not the best, but still...).
$endgroup$
– asgallant
Dec 27 '18 at 22:29
add a comment |
$begingroup$
Fact 1:
There must be a $1 coin
Fact 2:
2nd-value coin <=4, else would overflow
Proof:
Exhaustion...
Maximizing possibilities:
Notation: (x,y,z) : highest possible value
Possibility 1: (1,2,?)
(1,2,3):9
(1,2,4):10
(1,2,5):12(@S.M. in question)
(1,2,6):10
(1,2,7):11
(1,2,8+):7
For (1,2,?), (1,2,5):12=greatest
Possibility 2: (1,3,?)
(1,3,4):12
(1,3,5):11
(1,3,6):10
(1,3,7):11
(1,3,8):12
(1,3,9+):7
For (1,3,?), (1,3,8):12=greatest
Possibility 3: (1,4,?)
(1,4,5):15(Credits to @M)
(1,4,6):13
(1,4,7):9
(1,4,8+):6
For (1,4,?), (1,4,5):15=greatest
Overall:
(1,4,5):15=greatest
answered Dec 27 '18 at 15:19
Omega KryptonOmega Krypton
4,0851338
$endgroup$
Fact 1:
There must be a $1 coin
Fact 2:
2nd-value coin <=4, else would overflow
Proof:
Exhaustion...
Maximizing possibilities:
Notation: (x,y,z) : highest possible value
Possibility 1: (1,2,?)
(1,2,3):9
(1,2,4):10
(1,2,5):12(@S.M. in question)
(1,2,6):10
(1,2,7):11
(1,2,8+):7
For (1,2,?), (1,2,5):12=greatest
Possibility 2: (1,3,?)
(1,3,4):12
(1,3,5):11
(1,3,6):10
(1,3,7):11
(1,3,8):12
(1,3,9+):7
For (1,3,?), (1,3,8):12=greatest
Possibility 3: (1,4,?)
(1,4,5):15(Credits to @M)
(1,4,6):13
(1,4,7):9
(1,4,8+):6
For (1,4,?), (1,4,5):15=greatest
Overall:
(1,4,5):15=greatest
answered Dec 27 '18 at 15:19
Omega KryptonOmega Krypton
4,0851338
edited Dec 28 '18 at 0:44
answered Dec 27 '18 at 15:19
Omega KryptonOmega Krypton
4,0851338
answered Dec 27 '18 at 15:19
Omega KryptonOmega Krypton
4,0851338
answered Dec 27 '18 at 15:19
Omega KryptonOmega Krypton
4,0851338
4,0851338
$begingroup$
This is basically a properly organized version of the scribbles I made trying to figure it out (plus you found an extra answer). The explanation is very straight-forward and seems correct, so I'll attribute it a tick.
$endgroup$
– S. M.
Dec 27 '18 at 15:23
$begingroup$
Man, there was a lot I didn't see either, my bad. xD Still think it's the best explained answer and with further edits will get to the best answer.
$endgroup$
– S. M.
Dec 27 '18 at 15:33
1
$begingroup$
Fact 3 is not a true statement. 1,2,7 can generate all values up to 11 (not the best, but still...).
$endgroup$
– asgallant
Dec 27 '18 at 22:29
add a comment |
$begingroup$
This is basically a properly organized version of the scribbles I made trying to figure it out (plus you found an extra answer). The explanation is very straight-forward and seems correct, so I'll attribute it a tick.
$endgroup$
– S. M.
Dec 27 '18 at 15:23
$begingroup$
Man, there was a lot I didn't see either, my bad. xD Still think it's the best explained answer and with further edits will get to the best answer.
$endgroup$
– S. M.
Dec 27 '18 at 15:33
1
$begingroup$
Fact 3 is not a true statement. 1,2,7 can generate all values up to 11 (not the best, but still...).
$endgroup$
– asgallant
Dec 27 '18 at 22:29
$begingroup$
This is basically a properly organized version of the scribbles I made trying to figure it out (plus you found an extra answer). The explanation is very straight-forward and seems correct, so I'll attribute it a tick.
$endgroup$
– S. M.
Dec 27 '18 at 15:23
$begingroup$
This is basically a properly organized version of the scribbles I made trying to figure it out (plus you found an extra answer). The explanation is very straight-forward and seems correct, so I'll attribute it a tick.
$endgroup$
– S. M.
Dec 27 '18 at 15:23
$begingroup$
Man, there was a lot I didn't see either, my bad. xD Still think it's the best explained answer and with further edits will get to the best answer.
$endgroup$
– S. M.
Dec 27 '18 at 15:33
$begingroup$
Man, there was a lot I didn't see either, my bad. xD Still think it's the best explained answer and with further edits will get to the best answer.
$endgroup$
– S. M.
Dec 27 '18 at 15:33
1
1
$begingroup$
Fact 3 is not a true statement. 1,2,7 can generate all values up to 11 (not the best, but still...).
$endgroup$
– asgallant
Dec 27 '18 at 22:29
$begingroup$
Fact 3 is not a true statement. 1,2,7 can generate all values up to 11 (not the best, but still...).
$endgroup$
– asgallant
Dec 27 '18 at 22:29
add a comment |
$begingroup$
Anders Kaseorg's answer on the 8/8 list has the most optimal N/N answers up to N = 7 in a spoiler. And he has...
{1, 4, 5}
With a little enumeration, it's easy to see that you can use that set to get up to...
15.
EDIT
It's actually pretty simple to reason this out without brute forcing it (too much).
Say you have three denominations of coins - A, B, and C. Then clearly one of them has to be worth #1, or else you can't pay for things that are worth #1. So let's let A be worth #1. Now, assuming that C is the most valuable form of coinage, the most you can pay is #3C.
However, what if you want to pay #3C-1? We can safely assume that you'd have to use either 2C+A or 2C+B. But if you can use A, then C would have to be worth #2, which you can rule out with some quick figuring ({1,2,3} can get you #9, which {1, 1 < n < 2, 2} can't). So you're left with B being C-1.
As a result, you only need to check triples of the form {1, N, N+1}, where N can be at most 4.
answered Dec 27 '18 at 15:31
M DirrM Dirr
712
$endgroup$
$begingroup$
"The most you can pay is 3C". What if i choose {A,B,D} with D > C, but i can't pay 3D-1. The most i can pay is 3D-2 > 3C, which still makes it a better solution? The answer is correct, but the logic at the end is flawed
$endgroup$
– Tibos
Dec 29 '18 at 10:42
$begingroup$
There are only three denominations of coins, so in that case C = D. The logic is actually flawed (it doesn't work if you can't reach 3C, for one), but that's not why.
$endgroup$
– M Dirr
Dec 31 '18 at 14:32
$begingroup$
Perhaps my explanation of the problem with only checking {1, X, X+1} triplets was weirdly framed, let me give it another try. By putting the constraint C = B+1 you are limiting the value of C. Let's call mC that highest C achievable with your constraint. What you have not proven (and is in fact false) is that by choosing values for C higher than mC you will get a max that is lower than 3mC. Case in point: {1,2,3} => 9 while {1,2,6} => 10.
$endgroup$
– Tibos
Jan 1 at 14:40
1
$begingroup$
That is true - my issue is that my logic went "clearly the highest you can possibly get is 3C", made the false assumption that the best possible solution required you to reach 3C (it happens to be true in this case, but it doesn't generally hold), and then back-figured from there.
$endgroup$
– M Dirr
Jan 4 at 16:23
add a comment |
$begingroup$
Anders Kaseorg's answer on the 8/8 list has the most optimal N/N answers up to N = 7 in a spoiler. And he has...
{1, 4, 5}
With a little enumeration, it's easy to see that you can use that set to get up to...
15.
EDIT
It's actually pretty simple to reason this out without brute forcing it (too much).
Say you have three denominations of coins - A, B, and C. Then clearly one of them has to be worth #1, or else you can't pay for things that are worth #1. So let's let A be worth #1. Now, assuming that C is the most valuable form of coinage, the most you can pay is #3C.
However, what if you want to pay #3C-1? We can safely assume that you'd have to use either 2C+A or 2C+B. But if you can use A, then C would have to be worth #2, which you can rule out with some quick figuring ({1,2,3} can get you #9, which {1, 1 < n < 2, 2} can't). So you're left with B being C-1.
As a result, you only need to check triples of the form {1, N, N+1}, where N can be at most 4.
answered Dec 27 '18 at 15:31
M DirrM Dirr
712
$endgroup$
$begingroup$
"The most you can pay is 3C". What if i choose {A,B,D} with D > C, but i can't pay 3D-1. The most i can pay is 3D-2 > 3C, which still makes it a better solution? The answer is correct, but the logic at the end is flawed
$endgroup$
– Tibos
Dec 29 '18 at 10:42
$begingroup$
There are only three denominations of coins, so in that case C = D. The logic is actually flawed (it doesn't work if you can't reach 3C, for one), but that's not why.
$endgroup$
– M Dirr
Dec 31 '18 at 14:32
$begingroup$
Perhaps my explanation of the problem with only checking {1, X, X+1} triplets was weirdly framed, let me give it another try. By putting the constraint C = B+1 you are limiting the value of C. Let's call mC that highest C achievable with your constraint. What you have not proven (and is in fact false) is that by choosing values for C higher than mC you will get a max that is lower than 3mC. Case in point: {1,2,3} => 9 while {1,2,6} => 10.
$endgroup$
– Tibos
Jan 1 at 14:40
1
$begingroup$
That is true - my issue is that my logic went "clearly the highest you can possibly get is 3C", made the false assumption that the best possible solution required you to reach 3C (it happens to be true in this case, but it doesn't generally hold), and then back-figured from there.
$endgroup$
– M Dirr
Jan 4 at 16:23
add a comment |
$begingroup$
Anders Kaseorg's answer on the 8/8 list has the most optimal N/N answers up to N = 7 in a spoiler. And he has...
{1, 4, 5}
With a little enumeration, it's easy to see that you can use that set to get up to...
15.
EDIT
It's actually pretty simple to reason this out without brute forcing it (too much).
Say you have three denominations of coins - A, B, and C. Then clearly one of them has to be worth #1, or else you can't pay for things that are worth #1. So let's let A be worth #1. Now, assuming that C is the most valuable form of coinage, the most you can pay is #3C.
However, what if you want to pay #3C-1? We can safely assume that you'd have to use either 2C+A or 2C+B. But if you can use A, then C would have to be worth #2, which you can rule out with some quick figuring ({1,2,3} can get you #9, which {1, 1 < n < 2, 2} can't). So you're left with B being C-1.
As a result, you only need to check triples of the form {1, N, N+1}, where N can be at most 4.
answered Dec 27 '18 at 15:31
M DirrM Dirr
712
$endgroup$
Anders Kaseorg's answer on the 8/8 list has the most optimal N/N answers up to N = 7 in a spoiler. And he has...
{1, 4, 5}
With a little enumeration, it's easy to see that you can use that set to get up to...
15.
EDIT
It's actually pretty simple to reason this out without brute forcing it (too much).
Say you have three denominations of coins - A, B, and C. Then clearly one of them has to be worth #1, or else you can't pay for things that are worth #1. So let's let A be worth #1. Now, assuming that C is the most valuable form of coinage, the most you can pay is #3C.
However, what if you want to pay #3C-1? We can safely assume that you'd have to use either 2C+A or 2C+B. But if you can use A, then C would have to be worth #2, which you can rule out with some quick figuring ({1,2,3} can get you #9, which {1, 1 < n < 2, 2} can't). So you're left with B being C-1.
As a result, you only need to check triples of the form {1, N, N+1}, where N can be at most 4.
answered Dec 27 '18 at 15:31
M DirrM Dirr
712
edited Dec 27 '18 at 16:36
answered Dec 27 '18 at 15:31
M DirrM Dirr
712
answered Dec 27 '18 at 15:31
M DirrM Dirr
712
answered Dec 27 '18 at 15:31
M DirrM Dirr
712
712
$begingroup$
"The most you can pay is 3C". What if i choose {A,B,D} with D > C, but i can't pay 3D-1. The most i can pay is 3D-2 > 3C, which still makes it a better solution? The answer is correct, but the logic at the end is flawed
$endgroup$
– Tibos
Dec 29 '18 at 10:42
$begingroup$
There are only three denominations of coins, so in that case C = D. The logic is actually flawed (it doesn't work if you can't reach 3C, for one), but that's not why.
$endgroup$
– M Dirr
Dec 31 '18 at 14:32
$begingroup$
Perhaps my explanation of the problem with only checking {1, X, X+1} triplets was weirdly framed, let me give it another try. By putting the constraint C = B+1 you are limiting the value of C. Let's call mC that highest C achievable with your constraint. What you have not proven (and is in fact false) is that by choosing values for C higher than mC you will get a max that is lower than 3mC. Case in point: {1,2,3} => 9 while {1,2,6} => 10.
$endgroup$
– Tibos
Jan 1 at 14:40
1
$begingroup$
That is true - my issue is that my logic went "clearly the highest you can possibly get is 3C", made the false assumption that the best possible solution required you to reach 3C (it happens to be true in this case, but it doesn't generally hold), and then back-figured from there.
$endgroup$
– M Dirr
Jan 4 at 16:23
add a comment |
$begingroup$
"The most you can pay is 3C". What if i choose {A,B,D} with D > C, but i can't pay 3D-1. The most i can pay is 3D-2 > 3C, which still makes it a better solution? The answer is correct, but the logic at the end is flawed
$endgroup$
– Tibos
Dec 29 '18 at 10:42
$begingroup$
There are only three denominations of coins, so in that case C = D. The logic is actually flawed (it doesn't work if you can't reach 3C, for one), but that's not why.
$endgroup$
– M Dirr
Dec 31 '18 at 14:32
$begingroup$
Perhaps my explanation of the problem with only checking {1, X, X+1} triplets was weirdly framed, let me give it another try. By putting the constraint C = B+1 you are limiting the value of C. Let's call mC that highest C achievable with your constraint. What you have not proven (and is in fact false) is that by choosing values for C higher than mC you will get a max that is lower than 3mC. Case in point: {1,2,3} => 9 while {1,2,6} => 10.
$endgroup$
– Tibos
Jan 1 at 14:40
1
$begingroup$
That is true - my issue is that my logic went "clearly the highest you can possibly get is 3C", made the false assumption that the best possible solution required you to reach 3C (it happens to be true in this case, but it doesn't generally hold), and then back-figured from there.
$endgroup$
– M Dirr
Jan 4 at 16:23
$begingroup$
"The most you can pay is 3C". What if i choose {A,B,D} with D > C, but i can't pay 3D-1. The most i can pay is 3D-2 > 3C, which still makes it a better solution? The answer is correct, but the logic at the end is flawed
$endgroup$
– Tibos
Dec 29 '18 at 10:42
$begingroup$
"The most you can pay is 3C". What if i choose {A,B,D} with D > C, but i can't pay 3D-1. The most i can pay is 3D-2 > 3C, which still makes it a better solution? The answer is correct, but the logic at the end is flawed
$endgroup$
– Tibos
Dec 29 '18 at 10:42
$begingroup$
There are only three denominations of coins, so in that case C = D. The logic is actually flawed (it doesn't work if you can't reach 3C, for one), but that's not why.
$endgroup$
– M Dirr
Dec 31 '18 at 14:32
$begingroup$
There are only three denominations of coins, so in that case C = D. The logic is actually flawed (it doesn't work if you can't reach 3C, for one), but that's not why.
$endgroup$
– M Dirr
Dec 31 '18 at 14:32
$begingroup$
Perhaps my explanation of the problem with only checking {1, X, X+1} triplets was weirdly framed, let me give it another try. By putting the constraint C = B+1 you are limiting the value of C. Let's call mC that highest C achievable with your constraint. What you have not proven (and is in fact false) is that by choosing values for C higher than mC you will get a max that is lower than 3mC. Case in point: {1,2,3} => 9 while {1,2,6} => 10.
$endgroup$
– Tibos
Jan 1 at 14:40
$begingroup$
Perhaps my explanation of the problem with only checking {1, X, X+1} triplets was weirdly framed, let me give it another try. By putting the constraint C = B+1 you are limiting the value of C. Let's call mC that highest C achievable with your constraint. What you have not proven (and is in fact false) is that by choosing values for C higher than mC you will get a max that is lower than 3mC. Case in point: {1,2,3} => 9 while {1,2,6} => 10.
$endgroup$
– Tibos
Jan 1 at 14:40
1
1
$begingroup$
That is true - my issue is that my logic went "clearly the highest you can possibly get is 3C", made the false assumption that the best possible solution required you to reach 3C (it happens to be true in this case, but it doesn't generally hold), and then back-figured from there.
$endgroup$
– M Dirr
Jan 4 at 16:23
$begingroup$
That is true - my issue is that my logic went "clearly the highest you can possibly get is 3C", made the false assumption that the best possible solution required you to reach 3C (it happens to be true in this case, but it doesn't generally hold), and then back-figured from there.
$endgroup$
– M Dirr
Jan 4 at 16:23
add a comment |
$begingroup$
This is a little bit (read: a lot bit) of trickery, but
I can get up to 44 with coins of -1, 1, 10. The -1 helps because it allows you to get a units digit of 6 through 9.
I can't prove this is optimal, but it's a start (and I'm not sure if this is even good for the kingdom to have this type of coin :P)
answered Dec 27 '18 at 14:27
Excited RaichuExcited Raichu
6,51521166
$endgroup$
$begingroup$
I do think he means it as 3/3 problem, not a 3/8 problem
$endgroup$
– Thomas Blue
Dec 27 '18 at 14:30
$begingroup$
Yes, I mean it as a 3/3 problem, I'll specify it in the post just in case :p Very out-of-the-box answer though!
$endgroup$
– S. M.
Dec 27 '18 at 14:31
add a comment |
$begingroup$
This is a little bit (read: a lot bit) of trickery, but
I can get up to 44 with coins of -1, 1, 10. The -1 helps because it allows you to get a units digit of 6 through 9.
I can't prove this is optimal, but it's a start (and I'm not sure if this is even good for the kingdom to have this type of coin :P)
answered Dec 27 '18 at 14:27
Excited RaichuExcited Raichu
6,51521166
$endgroup$
$begingroup$
I do think he means it as 3/3 problem, not a 3/8 problem
$endgroup$
– Thomas Blue
Dec 27 '18 at 14:30
$begingroup$
Yes, I mean it as a 3/3 problem, I'll specify it in the post just in case :p Very out-of-the-box answer though!
$endgroup$
– S. M.
Dec 27 '18 at 14:31
add a comment |
$begingroup$
This is a little bit (read: a lot bit) of trickery, but
I can get up to 44 with coins of -1, 1, 10. The -1 helps because it allows you to get a units digit of 6 through 9.
I can't prove this is optimal, but it's a start (and I'm not sure if this is even good for the kingdom to have this type of coin :P)
answered Dec 27 '18 at 14:27
Excited RaichuExcited Raichu
6,51521166
$endgroup$
This is a little bit (read: a lot bit) of trickery, but
I can get up to 44 with coins of -1, 1, 10. The -1 helps because it allows you to get a units digit of 6 through 9.
I can't prove this is optimal, but it's a start (and I'm not sure if this is even good for the kingdom to have this type of coin :P)
answered Dec 27 '18 at 14:27
Excited RaichuExcited Raichu
6,51521166
answered Dec 27 '18 at 14:27
Excited RaichuExcited Raichu
6,51521166
answered Dec 27 '18 at 14:27
Excited RaichuExcited Raichu
6,51521166
answered Dec 27 '18 at 14:27
Excited RaichuExcited Raichu
6,51521166
6,51521166
$begingroup$
I do think he means it as 3/3 problem, not a 3/8 problem
$endgroup$
– Thomas Blue
Dec 27 '18 at 14:30
$begingroup$
Yes, I mean it as a 3/3 problem, I'll specify it in the post just in case :p Very out-of-the-box answer though!
$endgroup$
– S. M.
Dec 27 '18 at 14:31
add a comment |
$begingroup$
I do think he means it as 3/3 problem, not a 3/8 problem
$endgroup$
– Thomas Blue
Dec 27 '18 at 14:30
$begingroup$
Yes, I mean it as a 3/3 problem, I'll specify it in the post just in case :p Very out-of-the-box answer though!
$endgroup$
– S. M.
Dec 27 '18 at 14:31
$begingroup$
I do think he means it as 3/3 problem, not a 3/8 problem
$endgroup$
– Thomas Blue
Dec 27 '18 at 14:30
$begingroup$
I do think he means it as 3/3 problem, not a 3/8 problem
$endgroup$
– Thomas Blue
Dec 27 '18 at 14:30
$begingroup$
Yes, I mean it as a 3/3 problem, I'll specify it in the post just in case :p Very out-of-the-box answer though!
$endgroup$
– S. M.
Dec 27 '18 at 14:31
$begingroup$
Yes, I mean it as a 3/3 problem, I'll specify it in the post just in case :p Very out-of-the-box answer though!
$endgroup$
– S. M.
Dec 27 '18 at 14:31
add a comment |
4
$begingroup$
Can you repeat the context of the original problem here? Relying on a link to maintain that context isn't the best idea.
$endgroup$
– THiebert
Dec 27 '18 at 19:28
$begingroup$
It's different in the way that this one is simple enough that you can solve it without using a computer, so it does change a bit on the dynamics of the problem.
$endgroup$
– S. M.
Dec 28 '18 at 9:07
$begingroup$
@THiebert Added the rules from the original post.
$endgroup$
– S. M.
Dec 28 '18 at 10:37