Eight coins for the fair king
Clash Royale CLAN TAG#URR8PPP
You are responsible for creating new types of coins for the court.
King respects the forgetful: he wants you to create 8 coins of different value, no more.
King respects the feeble: he wants that any (integer) sum of money (price) could be paid with no more than 8 coins, since they can be heavy. This sum should be paid without giving change.
- But my king, no matter how big is the largest coin, you can't pay more than 8 of them! How would you pay any sum?
- The king respects the poor: he wants you to set N such that no price in the kingdom is allowed to be greater than N. Thus, the contradiction with the rule (2) can be satisfied.
However, you, as a wealthy customer, are very troubled with this last rule. You want to maximize N so you can continue buying ludicrously overpriced things.
What is the maximum N you can reach by creating the coin standard?
mathematics optimization money
asked Dec 24 '18 at 10:51
Thomas Blue
1,8901441
|
show 7 more comments
You are responsible for creating new types of coins for the court.
King respects the forgetful: he wants you to create 8 coins of different value, no more.
King respects the feeble: he wants that any (integer) sum of money (price) could be paid with no more than 8 coins, since they can be heavy. This sum should be paid without giving change.
- But my king, no matter how big is the largest coin, you can't pay more than 8 of them! How would you pay any sum?
- The king respects the poor: he wants you to set N such that no price in the kingdom is allowed to be greater than N. Thus, the contradiction with the rule (2) can be satisfied.
However, you, as a wealthy customer, are very troubled with this last rule. You want to maximize N so you can continue buying ludicrously overpriced things.
What is the maximum N you can reach by creating the coin standard?
mathematics optimization money
asked Dec 24 '18 at 10:51
Thomas Blue
1,8901441
5
Related: codegolf.stackexchange.com/q/178015
– Joel Reyes Noche
Dec 25 '18 at 14:08
2
"The king respects the poor: he wants you to set N such that no price in the kingdom is allowed to be greater than N." FYI, price controls tend to create shortages. This is bound to wreck the king's economy in some way, ultimately hurting the poor. ;)
– jpmc26
Dec 27 '18 at 0:35
7
The answer is in this paper.
– alephalpha
Dec 27 '18 at 13:35
1
@ThomasBlue self-answer it and/or mark as accepted any answer giving the optimal solution.
– Cœur
Dec 27 '18 at 17:43
1
@ThomasBlue I made a community wiki answer giving the optimal solution, which you can accept.
– isaacg
Dec 28 '18 at 6:50
|
show 7 more comments
You are responsible for creating new types of coins for the court.
King respects the forgetful: he wants you to create 8 coins of different value, no more.
King respects the feeble: he wants that any (integer) sum of money (price) could be paid with no more than 8 coins, since they can be heavy. This sum should be paid without giving change.
- But my king, no matter how big is the largest coin, you can't pay more than 8 of them! How would you pay any sum?
- The king respects the poor: he wants you to set N such that no price in the kingdom is allowed to be greater than N. Thus, the contradiction with the rule (2) can be satisfied.
However, you, as a wealthy customer, are very troubled with this last rule. You want to maximize N so you can continue buying ludicrously overpriced things.
What is the maximum N you can reach by creating the coin standard?
mathematics optimization money
asked Dec 24 '18 at 10:51
Thomas Blue
1,8901441
You are responsible for creating new types of coins for the court.
King respects the forgetful: he wants you to create 8 coins of different value, no more.
King respects the feeble: he wants that any (integer) sum of money (price) could be paid with no more than 8 coins, since they can be heavy. This sum should be paid without giving change.
- But my king, no matter how big is the largest coin, you can't pay more than 8 of them! How would you pay any sum?
- The king respects the poor: he wants you to set N such that no price in the kingdom is allowed to be greater than N. Thus, the contradiction with the rule (2) can be satisfied.
However, you, as a wealthy customer, are very troubled with this last rule. You want to maximize N so you can continue buying ludicrously overpriced things.
What is the maximum N you can reach by creating the coin standard?
mathematics optimization money
mathematics optimization money
asked Dec 24 '18 at 10:51
Thomas Blue
1,8901441
asked Dec 24 '18 at 10:51
Thomas Blue
1,8901441
edited Dec 24 '18 at 14:18
asked Dec 24 '18 at 10:51
Thomas Blue
1,8901441
asked Dec 24 '18 at 10:51
Thomas Blue
1,8901441
asked Dec 24 '18 at 10:51
Thomas Blue
1,8901441
1,8901441
5
Related: codegolf.stackexchange.com/q/178015
– Joel Reyes Noche
Dec 25 '18 at 14:08
2
"The king respects the poor: he wants you to set N such that no price in the kingdom is allowed to be greater than N." FYI, price controls tend to create shortages. This is bound to wreck the king's economy in some way, ultimately hurting the poor. ;)
– jpmc26
Dec 27 '18 at 0:35
7
The answer is in this paper.
– alephalpha
Dec 27 '18 at 13:35
1
@ThomasBlue self-answer it and/or mark as accepted any answer giving the optimal solution.
– Cœur
Dec 27 '18 at 17:43
1
@ThomasBlue I made a community wiki answer giving the optimal solution, which you can accept.
– isaacg
Dec 28 '18 at 6:50
|
show 7 more comments
5
Related: codegolf.stackexchange.com/q/178015
– Joel Reyes Noche
Dec 25 '18 at 14:08
2
"The king respects the poor: he wants you to set N such that no price in the kingdom is allowed to be greater than N." FYI, price controls tend to create shortages. This is bound to wreck the king's economy in some way, ultimately hurting the poor. ;)
– jpmc26
Dec 27 '18 at 0:35
7
The answer is in this paper.
– alephalpha
Dec 27 '18 at 13:35
1
@ThomasBlue self-answer it and/or mark as accepted any answer giving the optimal solution.
– Cœur
Dec 27 '18 at 17:43
1
@ThomasBlue I made a community wiki answer giving the optimal solution, which you can accept.
– isaacg
Dec 28 '18 at 6:50
5
5
Related: codegolf.stackexchange.com/q/178015
– Joel Reyes Noche
Dec 25 '18 at 14:08
Related: codegolf.stackexchange.com/q/178015
– Joel Reyes Noche
Dec 25 '18 at 14:08
2
2
"The king respects the poor: he wants you to set N such that no price in the kingdom is allowed to be greater than N." FYI, price controls tend to create shortages. This is bound to wreck the king's economy in some way, ultimately hurting the poor. ;)
– jpmc26
Dec 27 '18 at 0:35
"The king respects the poor: he wants you to set N such that no price in the kingdom is allowed to be greater than N." FYI, price controls tend to create shortages. This is bound to wreck the king's economy in some way, ultimately hurting the poor. ;)
– jpmc26
Dec 27 '18 at 0:35
7
7
The answer is in this paper.
– alephalpha
Dec 27 '18 at 13:35
The answer is in this paper.
– alephalpha
Dec 27 '18 at 13:35
1
1
@ThomasBlue self-answer it and/or mark as accepted any answer giving the optimal solution.
– Cœur
Dec 27 '18 at 17:43
@ThomasBlue self-answer it and/or mark as accepted any answer giving the optimal solution.
– Cœur
Dec 27 '18 at 17:43
1
1
@ThomasBlue I made a community wiki answer giving the optimal solution, which you can accept.
– isaacg
Dec 28 '18 at 6:50
@ThomasBlue I made a community wiki answer giving the optimal solution, which you can accept.
– isaacg
Dec 28 '18 at 6:50
|
show 7 more comments
6 Answers
6
active
oldest
votes
The optimal solution is
1, 8, 13, 58, 169, 295, 831, 1036
This set of coins allows N =
3485
This set of coins is given in this paper: Some Extremal Postage Stamp Bases, by Michael F. Challis and John P. Robinson.
This paper was found by @alephalpha.
add a comment |
You can do better than the greedy algorithm. With coins of value
1, 6, 20, 75, 175, 474, 756, 785
you can get N =
3356.
I wrote a search program for this but it isn’t going to finish searching the entire space in reasonable time, so I don’t know whether that’s optimal. Here are all the optimal solutions for up through seven coins:
one coin: 1, N = 1
two coins: 1, 2 or 1, 3, N = 4
three coins: 1, 4, 5, N = 15
four coins: 1, 3, 11, 18, N = 44
five coins: 1, 4, 9, 31, 51, N = 126
six coins: 1, 7, 11, 48, 83, 115, N = 388
seven coins: 1, 7, 18, 62, 104, 244, 259 or 1, 8, 13, 66, 115, 254, 415, N = 1137
edited Dec 25 '18 at 11:32
Glorfindel
13.5k34983
answered Dec 25 '18 at 6:49
Anders Kaseorg
56136
8
Nice! I have a program which I hope is able to finish the entire search space in reasonable time (6-8 weeks).
– Glorfindel
Dec 25 '18 at 12:24
Can confirm results for up to six coins(lang is too slow for seven ones :) ).
– Pavel Mikhailyuk
Dec 26 '18 at 19:21
1
I'll ask my bank to print notes of 1, 5, 20, 75. Should be close enough for a happy kingdom. [edit: oh, after a search, Austria and Germany had notes of 75 in the past]
– Cœur
Dec 27 '18 at 2:42
1
@GauravGandhi 20+6+6+6+6+6+6+1 - good example showing that the greedy algorithm wouldn't give a good result (as starting with 20+20 would mean you won't get there)
– SztupY
Dec 27 '18 at 15:01
4
N = 3485 with 1, 8, 13, 58, 169, 295, 831, 1036 was found in 2002 according to cs.uwaterloo.ca/journals/JIS/VOL13/Challis/challis6.html. (article found by alephalpha)
– Cœur
Dec 27 '18 at 17:22
|
show 5 more comments
I can do a little better, using coins of
1, 2, 5, 13, 34, 89, 233, 610
These are the Fibonacci numbers with odd index, also found in OEIS A001519.
I can pay amounts up to (and including)
$N=1596$
(without change).
Explanation:
According to Zeckendorf's theorem, every number has a (unique) representation as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. $N=1596$ is the smallest number requiring 8 digits in the Zeckendorf representation; it's 101010101010101, corresponding to 987 + 377 + 144 + 55 + 21 + 8 + 3 + 1.
As long as the 1s are on 'even' places (counted from the right), we can use the coins to pay them. In the case of 1596, all the 1s are on 'odd' places. Generally, a number may be a mixture of odds and evens.
The trick is now to combine basic properties of Fibonacci numbers to get rid of 1s on odd places. For instance, each instance of '1010x' can be replaced by '0200(x+1)', and each instance of '1001' by '0200'. The latter is fine since it does not increase the 'coin count'; the former increases the coin count by 1.
I'm having a hard time right now to formalize the proof; I will try again later today or tomorrow. Maybe Zeckendorf isn't the way to go after all ...
One can ask what $N$ is as function of the # of different coin values and maximum # of coins in a single payment.
In this case, $N(8) = 1596$; this sequence is given by OEIS A027941. In particular, note the last comment:
number of nonempty submultisets of multisets of weight n that span an initial interval of integers (see 2nd example). - Gus Wiseman, Feb 10 2015
answered Dec 24 '18 at 13:33
Glorfindel
13.5k34983
I can confirm that this works up to 1596. 1597 requires 9 coins (610,610,233,89,34,13,5,2,1)
– Dr Xorile
Dec 24 '18 at 15:08
While this approach works for 1 or 2 coins, it fails at 3 coins: A027941 gives a value of 12, but the set1, 4, 5shows we can go up to 15.
– Cœur
Dec 27 '18 at 2:34
Yeah, it's something else after all. I guess I wasn't sober when I posted that :)
– Glorfindel
Dec 27 '18 at 8:18
According to the article "Remarks on the postage stamp problem with applications to computers" by R. Alter, J. Barnett, published in 1977, the Fibonacci sequence A027941 is proved to be a lower bound to this problem. So your answer is definitely valuable for a quick estimate for larger number of coins.
– Cœur
Dec 27 '18 at 17:40
add a comment |
I can improve a little bit further using the coins
1, 5, 16, 51, 130, 332, 471, 1082.
chosen by a greedy computer program
With those coins I can express (with at most 8 coins, and no change) every non negative integer up to (and including)
2721
I'm not sure this is the definitive answer, as I was able to outperform the greedy algorithm for a smaller number of coins.
Explanation of how the program works:
There must be a 1 value coin, or else it will impossible to pay 1.
The program calculates what is the smallest unobtainable value with the current combination of coin values.
Then it tests every integer greater than every coin so far, but smaller (or equal) to the unobtainable value.
It picks the one that increases this limit the furthest.
answered Dec 24 '18 at 22:24
Pufe
1635
add a comment |
I would say:
255
Since:
Coins values are
1248163264128
By which you can pay any value, from 1 to 255
Second try:
If we allow duplicate coins, we can pay:
N = 382
Because we can pay any of the below:
2 * 128
2 * 128 + 1 + 2 + 4 + 8 + 16 + 32
2 * 128 + 64
2 * 128 + 64 + 1
2 * 128 + 64 + 1 + 2 + 4 + 8
2 * 128 + 64 + 16
2 * 128 + 64 + 16 + 1 + 2 + 4 + 8
2 * 128 + 64 + 32
2 * 128 + 64 + 32 + 1 + 2 + 4 + 8
...
2 * 128 + 64 + 32 + 16 + 8 + 4 = 380
2 * 128 + 64 + 32 + 16 + 8 + 4 + 1 = 381
2 * 128 + 64 + 32 + 16 + 8 + 4 + 2 = 382
answered Dec 24 '18 at 11:14
Ahmed Ashour
948212
ROT13(Gur pbvaf V guvax ner pbeerpg, ohg A vf abg. Nf sbe rknzcyr, jvgu 2k 128 pbvaf lbh jbhyq unir n inyhr bs 256)
– Jamie Barker
Dec 24 '18 at 11:30
Jryy, jr pna fnl 8 k 128 = 1024, ohg va guvf pnfr, jr pna'g unir 1023 ol 8 pbvaf
– Ahmed Ashour
Dec 24 '18 at 11:32
V ernyvfr gung, ohg lbh fgvyy unir n uvture znkvzhz guna 255 :Q
– Jamie Barker
Dec 24 '18 at 11:35
13
- Wait! - says the blacksmith. - I just can't accept this wild waste of material. Why would anyone need a coin valued 2, 4 or 8 if I can just pay them in single drahms? I can't deny your wiseness - I see, they become necessary later, yet still, I believe you can find a better solution.
– Thomas Blue
Dec 24 '18 at 12:01
add a comment |
This could be absolutely ridiculous since I didn't use anything to prove it is correct for all numbers but here goes:
If you can repeat coins (implied by "no matter how big is the largest coin, you can't pay more than 8 of them"), that means that with a coin of
1we can get up to 8, then we introduce the9, the maximum amount we can get with coins of9is 72, then we introduce the73and so on, leading us to the coins1,9,73,585,4681,37449,299593and2396745
which would lead to a maximum amount of 19173952, using 82396745coins.
TLDR, the answer to the question would be (according to the above):
19 173 952
Edit:
Well, it is incorrect, I could've simply tested it by trying to get 71; you'd need 7 coins of
9and you'd only be left with 1 of1, which would give us 64.
I suppose I'll leave this up anyways as an example of bad reasoning.
Also doubt it is correctly solvable to its full extent without using computers / a specific algorithm.
answered Dec 26 '18 at 12:40
S. M.
953419
As much as this answer is wrong, the last sentence is the point. The standard coin problem gets into some complicated number theory because the costs you can't make shrink as you add more coins, so the divisibility relations get very ugly (it's the wrong way somehow). There isn't a good solution known even with three coins in all cases, thought you can work it out with algorithms and bounds.
– theREALyumdub
Dec 26 '18 at 20:04
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "559"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f77750%2feight-coins-for-the-fair-king%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
6 Answers
6
active
oldest
votes
6 Answers
6
active
oldest
votes
active
oldest
votes
active
oldest
votes
The optimal solution is
1, 8, 13, 58, 169, 295, 831, 1036
This set of coins allows N =
3485
This set of coins is given in this paper: Some Extremal Postage Stamp Bases, by Michael F. Challis and John P. Robinson.
This paper was found by @alephalpha.
add a comment |
The optimal solution is
1, 8, 13, 58, 169, 295, 831, 1036
This set of coins allows N =
3485
This set of coins is given in this paper: Some Extremal Postage Stamp Bases, by Michael F. Challis and John P. Robinson.
This paper was found by @alephalpha.
add a comment |
The optimal solution is
1, 8, 13, 58, 169, 295, 831, 1036
This set of coins allows N =
3485
This set of coins is given in this paper: Some Extremal Postage Stamp Bases, by Michael F. Challis and John P. Robinson.
This paper was found by @alephalpha.
The optimal solution is
1, 8, 13, 58, 169, 295, 831, 1036
This set of coins allows N =
3485
This set of coins is given in this paper: Some Extremal Postage Stamp Bases, by Michael F. Challis and John P. Robinson.
This paper was found by @alephalpha.
answered Dec 28 '18 at 6:49
community wiki
isaacg
add a comment |
add a comment |
You can do better than the greedy algorithm. With coins of value
1, 6, 20, 75, 175, 474, 756, 785
you can get N =
3356.
I wrote a search program for this but it isn’t going to finish searching the entire space in reasonable time, so I don’t know whether that’s optimal. Here are all the optimal solutions for up through seven coins:
one coin: 1, N = 1
two coins: 1, 2 or 1, 3, N = 4
three coins: 1, 4, 5, N = 15
four coins: 1, 3, 11, 18, N = 44
five coins: 1, 4, 9, 31, 51, N = 126
six coins: 1, 7, 11, 48, 83, 115, N = 388
seven coins: 1, 7, 18, 62, 104, 244, 259 or 1, 8, 13, 66, 115, 254, 415, N = 1137
edited Dec 25 '18 at 11:32
Glorfindel
13.5k34983
answered Dec 25 '18 at 6:49
Anders Kaseorg
56136
8
Nice! I have a program which I hope is able to finish the entire search space in reasonable time (6-8 weeks).
– Glorfindel
Dec 25 '18 at 12:24
Can confirm results for up to six coins(lang is too slow for seven ones :) ).
– Pavel Mikhailyuk
Dec 26 '18 at 19:21
1
I'll ask my bank to print notes of 1, 5, 20, 75. Should be close enough for a happy kingdom. [edit: oh, after a search, Austria and Germany had notes of 75 in the past]
– Cœur
Dec 27 '18 at 2:42
1
@GauravGandhi 20+6+6+6+6+6+6+1 - good example showing that the greedy algorithm wouldn't give a good result (as starting with 20+20 would mean you won't get there)
– SztupY
Dec 27 '18 at 15:01
4
N = 3485 with 1, 8, 13, 58, 169, 295, 831, 1036 was found in 2002 according to cs.uwaterloo.ca/journals/JIS/VOL13/Challis/challis6.html. (article found by alephalpha)
– Cœur
Dec 27 '18 at 17:22
|
show 5 more comments
You can do better than the greedy algorithm. With coins of value
1, 6, 20, 75, 175, 474, 756, 785
you can get N =
3356.
I wrote a search program for this but it isn’t going to finish searching the entire space in reasonable time, so I don’t know whether that’s optimal. Here are all the optimal solutions for up through seven coins:
one coin: 1, N = 1
two coins: 1, 2 or 1, 3, N = 4
three coins: 1, 4, 5, N = 15
four coins: 1, 3, 11, 18, N = 44
five coins: 1, 4, 9, 31, 51, N = 126
six coins: 1, 7, 11, 48, 83, 115, N = 388
seven coins: 1, 7, 18, 62, 104, 244, 259 or 1, 8, 13, 66, 115, 254, 415, N = 1137
edited Dec 25 '18 at 11:32
Glorfindel
13.5k34983
answered Dec 25 '18 at 6:49
Anders Kaseorg
56136
8
Nice! I have a program which I hope is able to finish the entire search space in reasonable time (6-8 weeks).
– Glorfindel
Dec 25 '18 at 12:24
Can confirm results for up to six coins(lang is too slow for seven ones :) ).
– Pavel Mikhailyuk
Dec 26 '18 at 19:21
1
I'll ask my bank to print notes of 1, 5, 20, 75. Should be close enough for a happy kingdom. [edit: oh, after a search, Austria and Germany had notes of 75 in the past]
– Cœur
Dec 27 '18 at 2:42
1
@GauravGandhi 20+6+6+6+6+6+6+1 - good example showing that the greedy algorithm wouldn't give a good result (as starting with 20+20 would mean you won't get there)
– SztupY
Dec 27 '18 at 15:01
4
N = 3485 with 1, 8, 13, 58, 169, 295, 831, 1036 was found in 2002 according to cs.uwaterloo.ca/journals/JIS/VOL13/Challis/challis6.html. (article found by alephalpha)
– Cœur
Dec 27 '18 at 17:22
|
show 5 more comments
You can do better than the greedy algorithm. With coins of value
1, 6, 20, 75, 175, 474, 756, 785
you can get N =
3356.
I wrote a search program for this but it isn’t going to finish searching the entire space in reasonable time, so I don’t know whether that’s optimal. Here are all the optimal solutions for up through seven coins:
one coin: 1, N = 1
two coins: 1, 2 or 1, 3, N = 4
three coins: 1, 4, 5, N = 15
four coins: 1, 3, 11, 18, N = 44
five coins: 1, 4, 9, 31, 51, N = 126
six coins: 1, 7, 11, 48, 83, 115, N = 388
seven coins: 1, 7, 18, 62, 104, 244, 259 or 1, 8, 13, 66, 115, 254, 415, N = 1137
edited Dec 25 '18 at 11:32
Glorfindel
13.5k34983
answered Dec 25 '18 at 6:49
Anders Kaseorg
56136
You can do better than the greedy algorithm. With coins of value
1, 6, 20, 75, 175, 474, 756, 785
you can get N =
3356.
I wrote a search program for this but it isn’t going to finish searching the entire space in reasonable time, so I don’t know whether that’s optimal. Here are all the optimal solutions for up through seven coins:
one coin: 1, N = 1
two coins: 1, 2 or 1, 3, N = 4
three coins: 1, 4, 5, N = 15
four coins: 1, 3, 11, 18, N = 44
five coins: 1, 4, 9, 31, 51, N = 126
six coins: 1, 7, 11, 48, 83, 115, N = 388
seven coins: 1, 7, 18, 62, 104, 244, 259 or 1, 8, 13, 66, 115, 254, 415, N = 1137
edited Dec 25 '18 at 11:32
Glorfindel
13.5k34983
answered Dec 25 '18 at 6:49
Anders Kaseorg
56136
edited Dec 25 '18 at 11:32
Glorfindel
13.5k34983
edited Dec 25 '18 at 11:32
Glorfindel
13.5k34983
edited Dec 25 '18 at 11:32
Glorfindel
13.5k34983
13.5k34983
answered Dec 25 '18 at 6:49
Anders Kaseorg
56136
answered Dec 25 '18 at 6:49
Anders Kaseorg
56136
answered Dec 25 '18 at 6:49
Anders Kaseorg
56136
56136
8
Nice! I have a program which I hope is able to finish the entire search space in reasonable time (6-8 weeks).
– Glorfindel
Dec 25 '18 at 12:24
Can confirm results for up to six coins(lang is too slow for seven ones :) ).
– Pavel Mikhailyuk
Dec 26 '18 at 19:21
1
I'll ask my bank to print notes of 1, 5, 20, 75. Should be close enough for a happy kingdom. [edit: oh, after a search, Austria and Germany had notes of 75 in the past]
– Cœur
Dec 27 '18 at 2:42
1
@GauravGandhi 20+6+6+6+6+6+6+1 - good example showing that the greedy algorithm wouldn't give a good result (as starting with 20+20 would mean you won't get there)
– SztupY
Dec 27 '18 at 15:01
4
N = 3485 with 1, 8, 13, 58, 169, 295, 831, 1036 was found in 2002 according to cs.uwaterloo.ca/journals/JIS/VOL13/Challis/challis6.html. (article found by alephalpha)
– Cœur
Dec 27 '18 at 17:22
|
show 5 more comments
8
Nice! I have a program which I hope is able to finish the entire search space in reasonable time (6-8 weeks).
– Glorfindel
Dec 25 '18 at 12:24
Can confirm results for up to six coins(lang is too slow for seven ones :) ).
– Pavel Mikhailyuk
Dec 26 '18 at 19:21
1
I'll ask my bank to print notes of 1, 5, 20, 75. Should be close enough for a happy kingdom. [edit: oh, after a search, Austria and Germany had notes of 75 in the past]
– Cœur
Dec 27 '18 at 2:42
1
@GauravGandhi 20+6+6+6+6+6+6+1 - good example showing that the greedy algorithm wouldn't give a good result (as starting with 20+20 would mean you won't get there)
– SztupY
Dec 27 '18 at 15:01
4
N = 3485 with 1, 8, 13, 58, 169, 295, 831, 1036 was found in 2002 according to cs.uwaterloo.ca/journals/JIS/VOL13/Challis/challis6.html. (article found by alephalpha)
– Cœur
Dec 27 '18 at 17:22
8
8
Nice! I have a program which I hope is able to finish the entire search space in reasonable time (6-8 weeks).
– Glorfindel
Dec 25 '18 at 12:24
Nice! I have a program which I hope is able to finish the entire search space in reasonable time (6-8 weeks).
– Glorfindel
Dec 25 '18 at 12:24
Can confirm results for up to six coins(lang is too slow for seven ones :) ).
– Pavel Mikhailyuk
Dec 26 '18 at 19:21
Can confirm results for up to six coins(lang is too slow for seven ones :) ).
– Pavel Mikhailyuk
Dec 26 '18 at 19:21
1
1
I'll ask my bank to print notes of 1, 5, 20, 75. Should be close enough for a happy kingdom. [edit: oh, after a search, Austria and Germany had notes of 75 in the past]
– Cœur
Dec 27 '18 at 2:42
I'll ask my bank to print notes of 1, 5, 20, 75. Should be close enough for a happy kingdom. [edit: oh, after a search, Austria and Germany had notes of 75 in the past]
– Cœur
Dec 27 '18 at 2:42
1
1
@GauravGandhi 20+6+6+6+6+6+6+1 - good example showing that the greedy algorithm wouldn't give a good result (as starting with 20+20 would mean you won't get there)
– SztupY
Dec 27 '18 at 15:01
@GauravGandhi 20+6+6+6+6+6+6+1 - good example showing that the greedy algorithm wouldn't give a good result (as starting with 20+20 would mean you won't get there)
– SztupY
Dec 27 '18 at 15:01
4
4
N = 3485 with 1, 8, 13, 58, 169, 295, 831, 1036 was found in 2002 according to cs.uwaterloo.ca/journals/JIS/VOL13/Challis/challis6.html. (article found by alephalpha)
– Cœur
Dec 27 '18 at 17:22
N = 3485 with 1, 8, 13, 58, 169, 295, 831, 1036 was found in 2002 according to cs.uwaterloo.ca/journals/JIS/VOL13/Challis/challis6.html. (article found by alephalpha)
– Cœur
Dec 27 '18 at 17:22
|
show 5 more comments
I can do a little better, using coins of
1, 2, 5, 13, 34, 89, 233, 610
These are the Fibonacci numbers with odd index, also found in OEIS A001519.
I can pay amounts up to (and including)
$N=1596$
(without change).
Explanation:
According to Zeckendorf's theorem, every number has a (unique) representation as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. $N=1596$ is the smallest number requiring 8 digits in the Zeckendorf representation; it's 101010101010101, corresponding to 987 + 377 + 144 + 55 + 21 + 8 + 3 + 1.
As long as the 1s are on 'even' places (counted from the right), we can use the coins to pay them. In the case of 1596, all the 1s are on 'odd' places. Generally, a number may be a mixture of odds and evens.
The trick is now to combine basic properties of Fibonacci numbers to get rid of 1s on odd places. For instance, each instance of '1010x' can be replaced by '0200(x+1)', and each instance of '1001' by '0200'. The latter is fine since it does not increase the 'coin count'; the former increases the coin count by 1.
I'm having a hard time right now to formalize the proof; I will try again later today or tomorrow. Maybe Zeckendorf isn't the way to go after all ...
One can ask what $N$ is as function of the # of different coin values and maximum # of coins in a single payment.
In this case, $N(8) = 1596$; this sequence is given by OEIS A027941. In particular, note the last comment:
number of nonempty submultisets of multisets of weight n that span an initial interval of integers (see 2nd example). - Gus Wiseman, Feb 10 2015
answered Dec 24 '18 at 13:33
Glorfindel
13.5k34983
I can confirm that this works up to 1596. 1597 requires 9 coins (610,610,233,89,34,13,5,2,1)
– Dr Xorile
Dec 24 '18 at 15:08
While this approach works for 1 or 2 coins, it fails at 3 coins: A027941 gives a value of 12, but the set1, 4, 5shows we can go up to 15.
– Cœur
Dec 27 '18 at 2:34
Yeah, it's something else after all. I guess I wasn't sober when I posted that :)
– Glorfindel
Dec 27 '18 at 8:18
According to the article "Remarks on the postage stamp problem with applications to computers" by R. Alter, J. Barnett, published in 1977, the Fibonacci sequence A027941 is proved to be a lower bound to this problem. So your answer is definitely valuable for a quick estimate for larger number of coins.
– Cœur
Dec 27 '18 at 17:40
add a comment |
I can do a little better, using coins of
1, 2, 5, 13, 34, 89, 233, 610
These are the Fibonacci numbers with odd index, also found in OEIS A001519.
I can pay amounts up to (and including)
$N=1596$
(without change).
Explanation:
According to Zeckendorf's theorem, every number has a (unique) representation as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. $N=1596$ is the smallest number requiring 8 digits in the Zeckendorf representation; it's 101010101010101, corresponding to 987 + 377 + 144 + 55 + 21 + 8 + 3 + 1.
As long as the 1s are on 'even' places (counted from the right), we can use the coins to pay them. In the case of 1596, all the 1s are on 'odd' places. Generally, a number may be a mixture of odds and evens.
The trick is now to combine basic properties of Fibonacci numbers to get rid of 1s on odd places. For instance, each instance of '1010x' can be replaced by '0200(x+1)', and each instance of '1001' by '0200'. The latter is fine since it does not increase the 'coin count'; the former increases the coin count by 1.
I'm having a hard time right now to formalize the proof; I will try again later today or tomorrow. Maybe Zeckendorf isn't the way to go after all ...
One can ask what $N$ is as function of the # of different coin values and maximum # of coins in a single payment.
In this case, $N(8) = 1596$; this sequence is given by OEIS A027941. In particular, note the last comment:
number of nonempty submultisets of multisets of weight n that span an initial interval of integers (see 2nd example). - Gus Wiseman, Feb 10 2015
answered Dec 24 '18 at 13:33
Glorfindel
13.5k34983
I can confirm that this works up to 1596. 1597 requires 9 coins (610,610,233,89,34,13,5,2,1)
– Dr Xorile
Dec 24 '18 at 15:08
While this approach works for 1 or 2 coins, it fails at 3 coins: A027941 gives a value of 12, but the set1, 4, 5shows we can go up to 15.
– Cœur
Dec 27 '18 at 2:34
Yeah, it's something else after all. I guess I wasn't sober when I posted that :)
– Glorfindel
Dec 27 '18 at 8:18
According to the article "Remarks on the postage stamp problem with applications to computers" by R. Alter, J. Barnett, published in 1977, the Fibonacci sequence A027941 is proved to be a lower bound to this problem. So your answer is definitely valuable for a quick estimate for larger number of coins.
– Cœur
Dec 27 '18 at 17:40
add a comment |
I can do a little better, using coins of
1, 2, 5, 13, 34, 89, 233, 610
These are the Fibonacci numbers with odd index, also found in OEIS A001519.
I can pay amounts up to (and including)
$N=1596$
(without change).
Explanation:
According to Zeckendorf's theorem, every number has a (unique) representation as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. $N=1596$ is the smallest number requiring 8 digits in the Zeckendorf representation; it's 101010101010101, corresponding to 987 + 377 + 144 + 55 + 21 + 8 + 3 + 1.
As long as the 1s are on 'even' places (counted from the right), we can use the coins to pay them. In the case of 1596, all the 1s are on 'odd' places. Generally, a number may be a mixture of odds and evens.
The trick is now to combine basic properties of Fibonacci numbers to get rid of 1s on odd places. For instance, each instance of '1010x' can be replaced by '0200(x+1)', and each instance of '1001' by '0200'. The latter is fine since it does not increase the 'coin count'; the former increases the coin count by 1.
I'm having a hard time right now to formalize the proof; I will try again later today or tomorrow. Maybe Zeckendorf isn't the way to go after all ...
One can ask what $N$ is as function of the # of different coin values and maximum # of coins in a single payment.
In this case, $N(8) = 1596$; this sequence is given by OEIS A027941. In particular, note the last comment:
number of nonempty submultisets of multisets of weight n that span an initial interval of integers (see 2nd example). - Gus Wiseman, Feb 10 2015
answered Dec 24 '18 at 13:33
Glorfindel
13.5k34983
I can do a little better, using coins of
1, 2, 5, 13, 34, 89, 233, 610
These are the Fibonacci numbers with odd index, also found in OEIS A001519.
I can pay amounts up to (and including)
$N=1596$
(without change).
Explanation:
According to Zeckendorf's theorem, every number has a (unique) representation as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. $N=1596$ is the smallest number requiring 8 digits in the Zeckendorf representation; it's 101010101010101, corresponding to 987 + 377 + 144 + 55 + 21 + 8 + 3 + 1.
As long as the 1s are on 'even' places (counted from the right), we can use the coins to pay them. In the case of 1596, all the 1s are on 'odd' places. Generally, a number may be a mixture of odds and evens.
The trick is now to combine basic properties of Fibonacci numbers to get rid of 1s on odd places. For instance, each instance of '1010x' can be replaced by '0200(x+1)', and each instance of '1001' by '0200'. The latter is fine since it does not increase the 'coin count'; the former increases the coin count by 1.
I'm having a hard time right now to formalize the proof; I will try again later today or tomorrow. Maybe Zeckendorf isn't the way to go after all ...
One can ask what $N$ is as function of the # of different coin values and maximum # of coins in a single payment.
In this case, $N(8) = 1596$; this sequence is given by OEIS A027941. In particular, note the last comment:
number of nonempty submultisets of multisets of weight n that span an initial interval of integers (see 2nd example). - Gus Wiseman, Feb 10 2015
answered Dec 24 '18 at 13:33
Glorfindel
13.5k34983
edited Dec 24 '18 at 18:33
answered Dec 24 '18 at 13:33
Glorfindel
13.5k34983
answered Dec 24 '18 at 13:33
Glorfindel
13.5k34983
answered Dec 24 '18 at 13:33
Glorfindel
13.5k34983
13.5k34983
I can confirm that this works up to 1596. 1597 requires 9 coins (610,610,233,89,34,13,5,2,1)
– Dr Xorile
Dec 24 '18 at 15:08
While this approach works for 1 or 2 coins, it fails at 3 coins: A027941 gives a value of 12, but the set1, 4, 5shows we can go up to 15.
– Cœur
Dec 27 '18 at 2:34
Yeah, it's something else after all. I guess I wasn't sober when I posted that :)
– Glorfindel
Dec 27 '18 at 8:18
According to the article "Remarks on the postage stamp problem with applications to computers" by R. Alter, J. Barnett, published in 1977, the Fibonacci sequence A027941 is proved to be a lower bound to this problem. So your answer is definitely valuable for a quick estimate for larger number of coins.
– Cœur
Dec 27 '18 at 17:40
add a comment |
I can confirm that this works up to 1596. 1597 requires 9 coins (610,610,233,89,34,13,5,2,1)
– Dr Xorile
Dec 24 '18 at 15:08
While this approach works for 1 or 2 coins, it fails at 3 coins: A027941 gives a value of 12, but the set1, 4, 5shows we can go up to 15.
– Cœur
Dec 27 '18 at 2:34
Yeah, it's something else after all. I guess I wasn't sober when I posted that :)
– Glorfindel
Dec 27 '18 at 8:18
According to the article "Remarks on the postage stamp problem with applications to computers" by R. Alter, J. Barnett, published in 1977, the Fibonacci sequence A027941 is proved to be a lower bound to this problem. So your answer is definitely valuable for a quick estimate for larger number of coins.
– Cœur
Dec 27 '18 at 17:40
I can confirm that this works up to 1596. 1597 requires 9 coins (610,610,233,89,34,13,5,2,1)
– Dr Xorile
Dec 24 '18 at 15:08
I can confirm that this works up to 1596. 1597 requires 9 coins (610,610,233,89,34,13,5,2,1)
– Dr Xorile
Dec 24 '18 at 15:08
While this approach works for 1 or 2 coins, it fails at 3 coins: A027941 gives a value of 12, but the set
1, 4, 5 shows we can go up to 15.– Cœur
Dec 27 '18 at 2:34
While this approach works for 1 or 2 coins, it fails at 3 coins: A027941 gives a value of 12, but the set
1, 4, 5 shows we can go up to 15.– Cœur
Dec 27 '18 at 2:34
Yeah, it's something else after all. I guess I wasn't sober when I posted that :)
– Glorfindel
Dec 27 '18 at 8:18
Yeah, it's something else after all. I guess I wasn't sober when I posted that :)
– Glorfindel
Dec 27 '18 at 8:18
According to the article "Remarks on the postage stamp problem with applications to computers" by R. Alter, J. Barnett, published in 1977, the Fibonacci sequence A027941 is proved to be a lower bound to this problem. So your answer is definitely valuable for a quick estimate for larger number of coins.
– Cœur
Dec 27 '18 at 17:40
According to the article "Remarks on the postage stamp problem with applications to computers" by R. Alter, J. Barnett, published in 1977, the Fibonacci sequence A027941 is proved to be a lower bound to this problem. So your answer is definitely valuable for a quick estimate for larger number of coins.
– Cœur
Dec 27 '18 at 17:40
add a comment |
I can improve a little bit further using the coins
1, 5, 16, 51, 130, 332, 471, 1082.
chosen by a greedy computer program
With those coins I can express (with at most 8 coins, and no change) every non negative integer up to (and including)
2721
I'm not sure this is the definitive answer, as I was able to outperform the greedy algorithm for a smaller number of coins.
Explanation of how the program works:
There must be a 1 value coin, or else it will impossible to pay 1.
The program calculates what is the smallest unobtainable value with the current combination of coin values.
Then it tests every integer greater than every coin so far, but smaller (or equal) to the unobtainable value.
It picks the one that increases this limit the furthest.
answered Dec 24 '18 at 22:24
Pufe
1635
add a comment |
I can improve a little bit further using the coins
1, 5, 16, 51, 130, 332, 471, 1082.
chosen by a greedy computer program
With those coins I can express (with at most 8 coins, and no change) every non negative integer up to (and including)
2721
I'm not sure this is the definitive answer, as I was able to outperform the greedy algorithm for a smaller number of coins.
Explanation of how the program works:
There must be a 1 value coin, or else it will impossible to pay 1.
The program calculates what is the smallest unobtainable value with the current combination of coin values.
Then it tests every integer greater than every coin so far, but smaller (or equal) to the unobtainable value.
It picks the one that increases this limit the furthest.
answered Dec 24 '18 at 22:24
Pufe
1635
add a comment |
I can improve a little bit further using the coins
1, 5, 16, 51, 130, 332, 471, 1082.
chosen by a greedy computer program
With those coins I can express (with at most 8 coins, and no change) every non negative integer up to (and including)
2721
I'm not sure this is the definitive answer, as I was able to outperform the greedy algorithm for a smaller number of coins.
Explanation of how the program works:
There must be a 1 value coin, or else it will impossible to pay 1.
The program calculates what is the smallest unobtainable value with the current combination of coin values.
Then it tests every integer greater than every coin so far, but smaller (or equal) to the unobtainable value.
It picks the one that increases this limit the furthest.
answered Dec 24 '18 at 22:24
Pufe
1635
I can improve a little bit further using the coins
1, 5, 16, 51, 130, 332, 471, 1082.
chosen by a greedy computer program
With those coins I can express (with at most 8 coins, and no change) every non negative integer up to (and including)
2721
I'm not sure this is the definitive answer, as I was able to outperform the greedy algorithm for a smaller number of coins.
Explanation of how the program works:
There must be a 1 value coin, or else it will impossible to pay 1.
The program calculates what is the smallest unobtainable value with the current combination of coin values.
Then it tests every integer greater than every coin so far, but smaller (or equal) to the unobtainable value.
It picks the one that increases this limit the furthest.
answered Dec 24 '18 at 22:24
Pufe
1635
answered Dec 24 '18 at 22:24
Pufe
1635
answered Dec 24 '18 at 22:24
Pufe
1635
answered Dec 24 '18 at 22:24
Pufe
1635
1635
add a comment |
add a comment |
I would say:
255
Since:
Coins values are
1248163264128
By which you can pay any value, from 1 to 255
Second try:
If we allow duplicate coins, we can pay:
N = 382
Because we can pay any of the below:
2 * 128
2 * 128 + 1 + 2 + 4 + 8 + 16 + 32
2 * 128 + 64
2 * 128 + 64 + 1
2 * 128 + 64 + 1 + 2 + 4 + 8
2 * 128 + 64 + 16
2 * 128 + 64 + 16 + 1 + 2 + 4 + 8
2 * 128 + 64 + 32
2 * 128 + 64 + 32 + 1 + 2 + 4 + 8
...
2 * 128 + 64 + 32 + 16 + 8 + 4 = 380
2 * 128 + 64 + 32 + 16 + 8 + 4 + 1 = 381
2 * 128 + 64 + 32 + 16 + 8 + 4 + 2 = 382
answered Dec 24 '18 at 11:14
Ahmed Ashour
948212
ROT13(Gur pbvaf V guvax ner pbeerpg, ohg A vf abg. Nf sbe rknzcyr, jvgu 2k 128 pbvaf lbh jbhyq unir n inyhr bs 256)
– Jamie Barker
Dec 24 '18 at 11:30
Jryy, jr pna fnl 8 k 128 = 1024, ohg va guvf pnfr, jr pna'g unir 1023 ol 8 pbvaf
– Ahmed Ashour
Dec 24 '18 at 11:32
V ernyvfr gung, ohg lbh fgvyy unir n uvture znkvzhz guna 255 :Q
– Jamie Barker
Dec 24 '18 at 11:35
13
- Wait! - says the blacksmith. - I just can't accept this wild waste of material. Why would anyone need a coin valued 2, 4 or 8 if I can just pay them in single drahms? I can't deny your wiseness - I see, they become necessary later, yet still, I believe you can find a better solution.
– Thomas Blue
Dec 24 '18 at 12:01
add a comment |
I would say:
255
Since:
Coins values are
1248163264128
By which you can pay any value, from 1 to 255
Second try:
If we allow duplicate coins, we can pay:
N = 382
Because we can pay any of the below:
2 * 128
2 * 128 + 1 + 2 + 4 + 8 + 16 + 32
2 * 128 + 64
2 * 128 + 64 + 1
2 * 128 + 64 + 1 + 2 + 4 + 8
2 * 128 + 64 + 16
2 * 128 + 64 + 16 + 1 + 2 + 4 + 8
2 * 128 + 64 + 32
2 * 128 + 64 + 32 + 1 + 2 + 4 + 8
...
2 * 128 + 64 + 32 + 16 + 8 + 4 = 380
2 * 128 + 64 + 32 + 16 + 8 + 4 + 1 = 381
2 * 128 + 64 + 32 + 16 + 8 + 4 + 2 = 382
answered Dec 24 '18 at 11:14
Ahmed Ashour
948212
ROT13(Gur pbvaf V guvax ner pbeerpg, ohg A vf abg. Nf sbe rknzcyr, jvgu 2k 128 pbvaf lbh jbhyq unir n inyhr bs 256)
– Jamie Barker
Dec 24 '18 at 11:30
Jryy, jr pna fnl 8 k 128 = 1024, ohg va guvf pnfr, jr pna'g unir 1023 ol 8 pbvaf
– Ahmed Ashour
Dec 24 '18 at 11:32
V ernyvfr gung, ohg lbh fgvyy unir n uvture znkvzhz guna 255 :Q
– Jamie Barker
Dec 24 '18 at 11:35
13
- Wait! - says the blacksmith. - I just can't accept this wild waste of material. Why would anyone need a coin valued 2, 4 or 8 if I can just pay them in single drahms? I can't deny your wiseness - I see, they become necessary later, yet still, I believe you can find a better solution.
– Thomas Blue
Dec 24 '18 at 12:01
add a comment |
I would say:
255
Since:
Coins values are
1248163264128
By which you can pay any value, from 1 to 255
Second try:
If we allow duplicate coins, we can pay:
N = 382
Because we can pay any of the below:
2 * 128
2 * 128 + 1 + 2 + 4 + 8 + 16 + 32
2 * 128 + 64
2 * 128 + 64 + 1
2 * 128 + 64 + 1 + 2 + 4 + 8
2 * 128 + 64 + 16
2 * 128 + 64 + 16 + 1 + 2 + 4 + 8
2 * 128 + 64 + 32
2 * 128 + 64 + 32 + 1 + 2 + 4 + 8
...
2 * 128 + 64 + 32 + 16 + 8 + 4 = 380
2 * 128 + 64 + 32 + 16 + 8 + 4 + 1 = 381
2 * 128 + 64 + 32 + 16 + 8 + 4 + 2 = 382
answered Dec 24 '18 at 11:14
Ahmed Ashour
948212
I would say:
255
Since:
Coins values are
1248163264128
By which you can pay any value, from 1 to 255
Second try:
If we allow duplicate coins, we can pay:
N = 382
Because we can pay any of the below:
2 * 128
2 * 128 + 1 + 2 + 4 + 8 + 16 + 32
2 * 128 + 64
2 * 128 + 64 + 1
2 * 128 + 64 + 1 + 2 + 4 + 8
2 * 128 + 64 + 16
2 * 128 + 64 + 16 + 1 + 2 + 4 + 8
2 * 128 + 64 + 32
2 * 128 + 64 + 32 + 1 + 2 + 4 + 8
...
2 * 128 + 64 + 32 + 16 + 8 + 4 = 380
2 * 128 + 64 + 32 + 16 + 8 + 4 + 1 = 381
2 * 128 + 64 + 32 + 16 + 8 + 4 + 2 = 382
answered Dec 24 '18 at 11:14
Ahmed Ashour
948212
edited Dec 24 '18 at 11:53
answered Dec 24 '18 at 11:14
Ahmed Ashour
948212
answered Dec 24 '18 at 11:14
Ahmed Ashour
948212
answered Dec 24 '18 at 11:14
Ahmed Ashour
948212
948212
ROT13(Gur pbvaf V guvax ner pbeerpg, ohg A vf abg. Nf sbe rknzcyr, jvgu 2k 128 pbvaf lbh jbhyq unir n inyhr bs 256)
– Jamie Barker
Dec 24 '18 at 11:30
Jryy, jr pna fnl 8 k 128 = 1024, ohg va guvf pnfr, jr pna'g unir 1023 ol 8 pbvaf
– Ahmed Ashour
Dec 24 '18 at 11:32
V ernyvfr gung, ohg lbh fgvyy unir n uvture znkvzhz guna 255 :Q
– Jamie Barker
Dec 24 '18 at 11:35
13
- Wait! - says the blacksmith. - I just can't accept this wild waste of material. Why would anyone need a coin valued 2, 4 or 8 if I can just pay them in single drahms? I can't deny your wiseness - I see, they become necessary later, yet still, I believe you can find a better solution.
– Thomas Blue
Dec 24 '18 at 12:01
add a comment |
ROT13(Gur pbvaf V guvax ner pbeerpg, ohg A vf abg. Nf sbe rknzcyr, jvgu 2k 128 pbvaf lbh jbhyq unir n inyhr bs 256)
– Jamie Barker
Dec 24 '18 at 11:30
Jryy, jr pna fnl 8 k 128 = 1024, ohg va guvf pnfr, jr pna'g unir 1023 ol 8 pbvaf
– Ahmed Ashour
Dec 24 '18 at 11:32
V ernyvfr gung, ohg lbh fgvyy unir n uvture znkvzhz guna 255 :Q
– Jamie Barker
Dec 24 '18 at 11:35
13
- Wait! - says the blacksmith. - I just can't accept this wild waste of material. Why would anyone need a coin valued 2, 4 or 8 if I can just pay them in single drahms? I can't deny your wiseness - I see, they become necessary later, yet still, I believe you can find a better solution.
– Thomas Blue
Dec 24 '18 at 12:01
ROT13(Gur pbvaf V guvax ner pbeerpg, ohg A vf abg. Nf sbe rknzcyr, jvgu 2k 128 pbvaf lbh jbhyq unir n inyhr bs 256)
– Jamie Barker
Dec 24 '18 at 11:30
ROT13(Gur pbvaf V guvax ner pbeerpg, ohg A vf abg. Nf sbe rknzcyr, jvgu 2k 128 pbvaf lbh jbhyq unir n inyhr bs 256)
– Jamie Barker
Dec 24 '18 at 11:30
Jryy, jr pna fnl 8 k 128 = 1024, ohg va guvf pnfr, jr pna'g unir 1023 ol 8 pbvaf
– Ahmed Ashour
Dec 24 '18 at 11:32
Jryy, jr pna fnl 8 k 128 = 1024, ohg va guvf pnfr, jr pna'g unir 1023 ol 8 pbvaf
– Ahmed Ashour
Dec 24 '18 at 11:32
V ernyvfr gung, ohg lbh fgvyy unir n uvture znkvzhz guna 255 :Q
– Jamie Barker
Dec 24 '18 at 11:35
V ernyvfr gung, ohg lbh fgvyy unir n uvture znkvzhz guna 255 :Q
– Jamie Barker
Dec 24 '18 at 11:35
13
13
- Wait! - says the blacksmith. - I just can't accept this wild waste of material. Why would anyone need a coin valued 2, 4 or 8 if I can just pay them in single drahms? I can't deny your wiseness - I see, they become necessary later, yet still, I believe you can find a better solution.
– Thomas Blue
Dec 24 '18 at 12:01
- Wait! - says the blacksmith. - I just can't accept this wild waste of material. Why would anyone need a coin valued 2, 4 or 8 if I can just pay them in single drahms? I can't deny your wiseness - I see, they become necessary later, yet still, I believe you can find a better solution.
– Thomas Blue
Dec 24 '18 at 12:01
add a comment |
This could be absolutely ridiculous since I didn't use anything to prove it is correct for all numbers but here goes:
If you can repeat coins (implied by "no matter how big is the largest coin, you can't pay more than 8 of them"), that means that with a coin of
1we can get up to 8, then we introduce the9, the maximum amount we can get with coins of9is 72, then we introduce the73and so on, leading us to the coins1,9,73,585,4681,37449,299593and2396745
which would lead to a maximum amount of 19173952, using 82396745coins.
TLDR, the answer to the question would be (according to the above):
19 173 952
Edit:
Well, it is incorrect, I could've simply tested it by trying to get 71; you'd need 7 coins of
9and you'd only be left with 1 of1, which would give us 64.
I suppose I'll leave this up anyways as an example of bad reasoning.
Also doubt it is correctly solvable to its full extent without using computers / a specific algorithm.
answered Dec 26 '18 at 12:40
S. M.
953419
As much as this answer is wrong, the last sentence is the point. The standard coin problem gets into some complicated number theory because the costs you can't make shrink as you add more coins, so the divisibility relations get very ugly (it's the wrong way somehow). There isn't a good solution known even with three coins in all cases, thought you can work it out with algorithms and bounds.
– theREALyumdub
Dec 26 '18 at 20:04
add a comment |
This could be absolutely ridiculous since I didn't use anything to prove it is correct for all numbers but here goes:
If you can repeat coins (implied by "no matter how big is the largest coin, you can't pay more than 8 of them"), that means that with a coin of
1we can get up to 8, then we introduce the9, the maximum amount we can get with coins of9is 72, then we introduce the73and so on, leading us to the coins1,9,73,585,4681,37449,299593and2396745
which would lead to a maximum amount of 19173952, using 82396745coins.
TLDR, the answer to the question would be (according to the above):
19 173 952
Edit:
Well, it is incorrect, I could've simply tested it by trying to get 71; you'd need 7 coins of
9and you'd only be left with 1 of1, which would give us 64.
I suppose I'll leave this up anyways as an example of bad reasoning.
Also doubt it is correctly solvable to its full extent without using computers / a specific algorithm.
answered Dec 26 '18 at 12:40
S. M.
953419
As much as this answer is wrong, the last sentence is the point. The standard coin problem gets into some complicated number theory because the costs you can't make shrink as you add more coins, so the divisibility relations get very ugly (it's the wrong way somehow). There isn't a good solution known even with three coins in all cases, thought you can work it out with algorithms and bounds.
– theREALyumdub
Dec 26 '18 at 20:04
add a comment |
This could be absolutely ridiculous since I didn't use anything to prove it is correct for all numbers but here goes:
If you can repeat coins (implied by "no matter how big is the largest coin, you can't pay more than 8 of them"), that means that with a coin of
1we can get up to 8, then we introduce the9, the maximum amount we can get with coins of9is 72, then we introduce the73and so on, leading us to the coins1,9,73,585,4681,37449,299593and2396745
which would lead to a maximum amount of 19173952, using 82396745coins.
TLDR, the answer to the question would be (according to the above):
19 173 952
Edit:
Well, it is incorrect, I could've simply tested it by trying to get 71; you'd need 7 coins of
9and you'd only be left with 1 of1, which would give us 64.
I suppose I'll leave this up anyways as an example of bad reasoning.
Also doubt it is correctly solvable to its full extent without using computers / a specific algorithm.
answered Dec 26 '18 at 12:40
S. M.
953419
This could be absolutely ridiculous since I didn't use anything to prove it is correct for all numbers but here goes:
If you can repeat coins (implied by "no matter how big is the largest coin, you can't pay more than 8 of them"), that means that with a coin of
1we can get up to 8, then we introduce the9, the maximum amount we can get with coins of9is 72, then we introduce the73and so on, leading us to the coins1,9,73,585,4681,37449,299593and2396745
which would lead to a maximum amount of 19173952, using 82396745coins.
TLDR, the answer to the question would be (according to the above):
19 173 952
Edit:
Well, it is incorrect, I could've simply tested it by trying to get 71; you'd need 7 coins of
9and you'd only be left with 1 of1, which would give us 64.
I suppose I'll leave this up anyways as an example of bad reasoning.
Also doubt it is correctly solvable to its full extent without using computers / a specific algorithm.
answered Dec 26 '18 at 12:40
S. M.
953419
edited Dec 26 '18 at 12:48
answered Dec 26 '18 at 12:40
S. M.
953419
answered Dec 26 '18 at 12:40
S. M.
953419
answered Dec 26 '18 at 12:40
S. M.
953419
953419
As much as this answer is wrong, the last sentence is the point. The standard coin problem gets into some complicated number theory because the costs you can't make shrink as you add more coins, so the divisibility relations get very ugly (it's the wrong way somehow). There isn't a good solution known even with three coins in all cases, thought you can work it out with algorithms and bounds.
– theREALyumdub
Dec 26 '18 at 20:04
add a comment |
As much as this answer is wrong, the last sentence is the point. The standard coin problem gets into some complicated number theory because the costs you can't make shrink as you add more coins, so the divisibility relations get very ugly (it's the wrong way somehow). There isn't a good solution known even with three coins in all cases, thought you can work it out with algorithms and bounds.
– theREALyumdub
Dec 26 '18 at 20:04
As much as this answer is wrong, the last sentence is the point. The standard coin problem gets into some complicated number theory because the costs you can't make shrink as you add more coins, so the divisibility relations get very ugly (it's the wrong way somehow). There isn't a good solution known even with three coins in all cases, thought you can work it out with algorithms and bounds.
– theREALyumdub
Dec 26 '18 at 20:04
As much as this answer is wrong, the last sentence is the point. The standard coin problem gets into some complicated number theory because the costs you can't make shrink as you add more coins, so the divisibility relations get very ugly (it's the wrong way somehow). There isn't a good solution known even with three coins in all cases, thought you can work it out with algorithms and bounds.
– theREALyumdub
Dec 26 '18 at 20:04
add a comment |
Thanks for contributing an answer to Puzzling Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f77750%2feight-coins-for-the-fair-king%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
5
Related: codegolf.stackexchange.com/q/178015
– Joel Reyes Noche
Dec 25 '18 at 14:08
2
"The king respects the poor: he wants you to set N such that no price in the kingdom is allowed to be greater than N." FYI, price controls tend to create shortages. This is bound to wreck the king's economy in some way, ultimately hurting the poor. ;)
– jpmc26
Dec 27 '18 at 0:35
7
The answer is in this paper.
– alephalpha
Dec 27 '18 at 13:35
1
@ThomasBlue self-answer it and/or mark as accepted any answer giving the optimal solution.
– Cœur
Dec 27 '18 at 17:43
1
@ThomasBlue I made a community wiki answer giving the optimal solution, which you can accept.
– isaacg
Dec 28 '18 at 6:50