Find the most unfortunate compact combination of coins to have in LOLandia

Question

You live in LOLandia. Its currency is called 'lulz' and comes in the form of coins and paper banknotes. The smallest paper banknote has a nominal value of 500 lulz. There are six types of coins, each with a different nominal value:

• 200 lulz coin
• 100 lulz coin
• 50 lulz coin
• 20 lulz coin
• 10 lulz coin
• 5 lulz coin

You prefer to keep all your pocket money in the most compact form possible. By "compact" I mean that if you have, say, four 20 lulz coins, plus one 10 lulz coin, plus two 5 lulz coins, then you will exchange them for one 100 lulz coin. Or if the total sum of coins that you have exceeds 500 lulz, then you will exchange all/some of them to banknote(s).

One day you discover that you have the most unfortunate compact combination of coins possible. This means the following:

• This combination is already compact, so it can't be improved.
• Out of all possible compact combinations of coins, this one has the largest total number of all coins.
• Out of all possible compact combinations of coins with the largest number of coins, this one holds the smallest total value of the coins.

What is this combination? You need to say how many coins of each type you have, the total number of coins of all types, and their total value in lulz. It's acceptable to have zero coins of particular type.

P.S. You may use your programming skills to find the answer.

P.P.S. You can make 50,20,20,20 more compact by exchanging 50,20,20,20 to 100,10. Yes, we get 10 and 10<20, but it doesn't matter, what matters is that we got 100, and you exchanged some coins for a higher nominal value. If you can reduce the number of coins by exchanging them, then said combination is not compact.

Answer 1

Let $f(n)$ be a function equal to the smallest number of coins needed to pay $n$ lulz. So, we need to find the maximum value of $f$ for $n$ in $\{5,10,15...495\}$ (since if $n\geqslant500$, you can always exchange some coins for banknotes).

We have a following recurrent relation for $f$: $$f(x)=\min_{s\in S, n-s\geqslant0} 1+f(n-s)$$ where $S=\{5,10,20,50,100,200\}$ is the set of all coin values. Obviously, $f(0)=0$ (you need no coins to pay nothing).

The following Python program (Try it online!) evaluates $f(x)$ for all the values needed. It turns out that the maximum number of coins is 6 for a number of different amounts of money, the smallest of them being $n=385$. The 6 coins needed to pay 385 luls are 200, 100, 50, 20, 10 and 5 (i.e. 1 coin of each type present).

  S = {5, 10, 20, 50, 100, 200}


  f = {}
  f[0] = 0


  for n in range(5, 500, 5):
      f[n] = min(1 + f[n - s] for s in S if n - s >= 0)
      print(n, f[n])

Answer 2

The maximum number of coins is

8

with a minimum total value of

435

achieved by

one 200, one 100, one 50, four 20, and one 5

The integer linear programming solution approach I used might be of interest. Let nonnegative integer decision variable $x_c$ be the number of coins of type $c$. The first problem is to maximize $\sum_c x_c$ subject to $\sum_c c\cdot x_c \le 495$ and "compactness" constraints. Rather than enumerate all of the compactness constraints explicitly, I started with the obvious $x_5 \le 1$, $x_{10} \le 1$, $x_{20} \le 4$, $x_{50} \le 1$, $x_{100} \le 1$, and generated the rest dynamically only when they were violated. The first solve yielded $x_5=1$, $x_{10}=1$, $x_{20}=4$, $x_{50}=1$, $x_{100}=1$, $x_{200}=1$. But $10+20+20=50$, so we want to enforce the disjunction $x_{10} < 1 \lor x_{20} < 2$. To do this, I introduced binary variables $y_{c,v}$ to indicate whether $x_{c}=v$, together with linear constraints \begin{align} \sum_v y_{c,v} &= 1 &\text{for all $c$} \\ \sum_v v\cdot y_{c,v} &= x_c &\text{for all $c$} \\ y_{10,0} + y_{20,0} + y_{20,1} &\ge 1 \end{align} The next solve yielded $x_5=1$, $x_{10}=0$, $x_{20}=4$, $x_{50}=1$, $x_{100}=1$, $x_{200}=1$, with no violations (under my initial understanding of the definition of compact) and $8$ coins. Then I added an "objective cut" to enforce this maximum number of coins: $$\sum_c x_c \ge 8$$ Finally, minimizing $\sum_c c \cdot x_c$ yielded the same solution with total value $435$.

To enforce the intended meaning of compactness, the same approach works. It turns out that we would just need to enforce $x_{20} \le 2$ (because $20+20+20=10+50$). The resulting solution is $x_5=1$, $x_{10}=0$, $x_{20}=2$, $x_{50}=1$, $x_{100}=0$, $x_{200}=2$, with no violations (under the intended definition of compact), $6$ coins, and total value $495$. The objective cut becomes instead: $$\sum_c x_c \ge 6.$$ Finally, minimizing $\sum_c c \cdot x_c$ yields $x_5=x_{10}=x_{20}=x_{50}=x_{100}=x_{200}=1$, with total value $385$.

Answer 3

Since we will always simplify our amount of luls, prioritizing larger-valued coins over smaller-valued coins, we can find the maximum amount and combination of coins of n luls, given the rules, by starting with the largest-valued coin and continuously subtracting it from the starting amount of luls when possible (meaning the operation must result in an amount >= 0), keeping track of the operations done. When the operation would not be successful, we would then go to the next largest-valued coin and repeat the same process. Doing this systematically until amount == 0, we would get a list of the optimized combination (unless it is not possible with the given coin values, then we would end with amount > 0 and amount < smallest-valued coin). Here is code written in Python that performs this algorithm.

def getOptimizedCombination(amount, values = (5, 10, 20, 50, 100, 200, 500)):
    combination = []
    for value in sorted(values, reverse = True):
        while (amount - value >= 0):
            combination.append(value)
            amount -= value
    return combination if amount == 0 else []


print( getOptimizedCombination(385) )

Answer 4

You don't need any code for that. No spoilers as solution is quite obvious and it has been a day.

3x20 simplifies to 50+10. 20+20+10 simplifies to 50 and 20+20 > 20+10. Therefore, we cannot have 2x20. The same for 200. Anything else is obviously optimal when you have 1 coin of each type because 2 already merge to the next one. So, 6 coins with 385 total.

If you couldn't simplify 3x20 to 50+10 (and 3x200 to 500+100), the obvious solution would be 4x200+50+4x20+5. 10 coins with 935 total.

If you want to actually require a computer to solve this type of problems, perhaps try coins in fibonacci sequence - gap is less than a factor of 2, so you have many combinations you need to check to minimize number of coins (I suggest using a custom sequence with greatly varying factor between the coins to really make it difficult for a no-computer approach)

Answer 5

It can be done without programming or mathematics.

If the set of coins is compact that means

- Among 5's you can have only one because 5+5 converts to 10.
- Among 10's and 20's you cannot have more than one 10 because 10+10 converts to 20.
And 10's and 20's cannot total 50 or more.
This allows only combinations 10, 20, 10+20, and 20+20.
- Among 50's you can have only one because 50+50 converts to 100.
- Among 100's and 200's you cannot have more than one 100 because 100+100 converts to 200.
And 100's and 200's cannot total 500 or more.
This allows only combinations 100, 200, 100+200, and 200+200.

So the maximum number of coins is

Six coins. Just add the maximum count for each category.
- One 5
- Two among 10's and 20's
- One 50
- Two among 100's and 200's

The minimum value is

To take the cheapest max-coin possibility for each set.
For instance among the 10's and 20's, two coins are possible. The two-coin combinations are 10+20 and 20+20. Since 10+20 has lower value, you take that combination.

Collecting that for all categories gives the set { 5, 10, 20, 50, 100, 200 } totalling 385 lulz.