3
$\begingroup$

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:

  1. You must create 3 coins of different value, no more.

  2. Any sum of money must be paid with only 3 coins. This sum should be paid without giving change.

  3. 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, 2 and 5, 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.

Improve this question
$\endgroup$
3
  • 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, 2018 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, 2018 at 9:07
  • $\begingroup$ @THiebert Added the rules from the original post. $\endgroup$
    – S. M.
    Dec 28, 2018 at 10:37

3 Answers 3

Reset to default
8
$\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

Improve this answer
$\endgroup$
3
  • $\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, 2018 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, 2018 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, 2018 at 22:29
7
$\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.

Improve this answer
$\endgroup$
4
  • $\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, 2018 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, 2018 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, 2019 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, 2019 at 16:23
4
$\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)

Improve this answer
$\endgroup$
2
  • $\begingroup$ I do think he means it as 3/3 problem, not a 3/8 problem $\endgroup$
    – Thomas Blue
    Dec 27, 2018 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, 2018 at 14:31

Not the answer you're looking for? Browse other questions tagged or ask your own question.