28

You are the knight of a great kingdom in an unknown world. Your king sent you to a dungeon and you killed the dragon and got 1000 gold coins from the dragon’s lair. Normally, you are supposed to give all gold coins to the kingdom but the King says;

Congratulations, you collected 1000 gold with your quest, but I would like to share these gold with you for your brave effort in the dungeon. To do so, I will give you as many bags as you want, and you can put as many gold coins as you want in each bag but you should put all 1000 coins in the bags.

After that, I will check every bag that contains gold coins, to see how many gold coins are in each of them. I will think of a number and take all bags with that number of gold coins! But I may cheat and take some coins out from some bags to reduce the number of coins in those bag to that number of coins so that I can keep those bags as well. You will be able to keep any coins I remove from the bags.

Naturally you would like to maximize the amount of coins you can have.

What is the maximum amount of gold coins you can guarantee to have at the end of the King's game?

For example:

If there were 25 coins, and you put those coins into 6 bags where the number of coins in each bag is 4, 4, 4, 4, 7, 2, the maximum number of gold coins the King can take would be 20 because the King may choose the number 4, take the first 4 bags, give 3 coins to you from the bag which contains 7 gold coins, then keep the remaining 4 coins in that bag. You will keep 3 + 2 = 5 coins at most at the end.

RobPratt
  • 13,685
  • 1
  • 29
  • 56
Oray
  • 30,307
  • 6
  • 61
  • 215
  • 5
    Why would the King not chose "1", and then "put out" all gold coins in excess of 1, giving the King all the gold? – Michael Richardson Oct 23 '20 at 19:22
  • 7
    I think the meaning of "put out" is unclear. I think you mean the Knight gets the put out coins? – Douglas Leeder Oct 23 '20 at 20:27
  • 3
    You mean "dragon's lair," not "dragon layer." You need to spell out the rules for the king putting out (taking out) coins from the bags. Why can't the king just take all coins out of all bags and keep all the gold for himself? – David Conrad Oct 23 '20 at 23:02

4 Answers4

27

It might be possible to do a little better, but I think I can get

814

Explanation:

Consider first the continuous problem.

The king will always choose the number matching a bag (else he can get more by going up to the next biggest number that matches a bag). Thus, he can get the number in the biggest bag, or twice the number in the next biggest bag, three times the number in the third biggest bag, etc. It is best to equalize these numbers (else re-balancing the bags will improve our strategy.) In the continuous setting, then, let $1$ represent the number in the biggest bag. That is also the most the king can get. The total is then $1+1/2+1/3+\dots+1/n$ where $n$ is the number of bags. This number diverges (harmonic series) as $n$ increases, so the king's fraction goes to zero.

But, the problem is discrete. We can approximate such strategies with discrete numbers. The best I've been able to do is to allocate $181$ bags as follows: $186$, $93$, $62$, $46$, $37$, $31$, $26$, $23$, $20$, $18$, $16$, $15$, $14$, $13$, $12$, $11$, then start having multiple bags of the same size: 2x $10$ (until $18$ bags are full), 2x $9$ (to $20$ bags), 3x $8$ (to $23$ bags), $7$ to $26$ bags, $6$ to $31$ bags, $5$ to $37$ bags, $4$ to $46$ bags, $3$ to $62$ bags $2$ to $93$ bags and $1$ for the rest.

So, for example if the king chooses $1$, he gets $181$ ($1$ from each bag). If he chooses $2$, he gets $2 \times 93$ because there are $93$ bags with $2$ or more.

tehtmi
  • 3,241
  • 15
  • 18
  • I just thought the same strategy as this one. – Bubbler Oct 22 '20 at 22:46
  • Can you explain 2x 10 (until 18 bags are full), 2x 9 (to 20 bags), 3x 7 (to 23 bags), 6 to 31 bags, 5 to 37 bags, 4 to 46 bags, 3 to 62 bags 2 to 93 bags and 1 for the rest. ? – risky mysteries Oct 22 '20 at 22:48
  • @riskymysteries: We are filling the bags from largest to smallest. If you count, the bag with $11$ is the 16th bag. So, if we have two bags with $10$, these will be the 17th and 18th bags. Then we start filling with $9$, the next smallest number, until we have filled the 20th bag overall, etc. Counting like this, we just need to check that (index of bag) * (amount in bag) <= 186 for each bag. – tehtmi Oct 22 '20 at 22:52
  • Thank you! ---- – risky mysteries Oct 22 '20 at 22:53
  • I'm pretty sutre this is optimal. – Paul Panzer Oct 22 '20 at 22:55
  • @tehtmi Is it [186, 93, 62, 46, 37, 31, 26, 23, 20, 18, 16, 15, 14, 13, 12, 11]+[10]*2+[9]*2+[7]*3+[6]*(31-23)+[5]*(37-31)+[4]*(46-37)+[3]*(62-46)+[2]*(93-62)+[1]*(187-93)? – risky mysteries Oct 22 '20 at 23:28
  • @riskymysteries Yes, except [1]*(182-93) because there are only $181$ bags (there is some slack), but actually I notice I made a mistake since your calculation comes out to 1000. I skipped $8$ when transcribing my answer. It should be $8$ to $23$ bags and $7$ to $26$ bags. (What you wrote is a valid equivalent answer, and is what I actually wrote except for the number of bags.) – tehtmi Oct 22 '20 at 23:43
  • @riskymysteries Actually `[1](181-93)` I guess. – tehtmi Oct 22 '20 at 23:48
  • @tehtmi Yeah, I noticed :) – risky mysteries Oct 22 '20 at 23:59
  • congratz, right answer! – Oray Oct 23 '20 at 03:56
  • See my answer for why this is optimal. – Bubbler Oct 23 '20 at 05:31
  • @tehtmi , how did you realize that the largest bag will be 186 and not , say, 185 or something ? did you try all possible values for the largest bag using a computer programme, before realizing that the largest bag should be 186 ? Secondly , "It might be possible to do a little better." What makes you think that 186 can be improved upon ? – Hemant Agarwal Oct 23 '20 at 19:08
  • @tehtmi, third question . How can we know that all bags will have different number of coins in the optimal case ? How can we know for sure that there is not another distribution of coins which is optimal and in which, for instance, the bag with the most coins has 180 coins followed by 2 bags with 60 coins each, etc. – Hemant Agarwal Oct 23 '20 at 19:23
  • @HemantAgarwal: I did use a computer progam, but it wasn't really designed properly, so I wasn't that sure and didn't spend the time to check carefully, but I am confident now that 186 is best. Refer to Bubbler's answer about trying 185. We do not know that all bags have different numbers, and nothing assumes that; indeed it is not true in the configuration I suggest. – tehtmi Oct 23 '20 at 19:42
  • @tehtmi , let me rephrase my question . How do we know, for instance, that in the optimal solution, there aren't 2 bags with the second highest number of coins each, 2 bags with the 3rd highest, number of coins, 2 bags with the 4th highest number of coins, etc. To put it in other words, how do we know that in the optimal solution, the total is not 1+2/3+2/5+2/7.... instead of, "The total is then 1+1/2+1/3+⋯+1/n where n is the number of bags." – Hemant Agarwal Oct 23 '20 at 22:39
  • 1
    @HemantAgarwal: If there are two bags with the second highest number of coins, then that is also the third highest number of coins. If the king chooses that number he will get 3 times that many of coins, so that number shouldn't be higher than 1/3 the highest (so we may as well put more coins in the second bag). – tehtmi Oct 23 '20 at 23:12
14

A complementary result of tehtmi's answer: Using the same strategy,

814

is the maximum number of coins you can get, and +1 is impossible. Proof:

Let's assume the largest amount of coins the king can get is $n$. Then the number of total coins cannot exceed $\sum_{i=1}^{n}{\left\lfloor \frac{n}{i} \right\rfloor}$, as each term of this sum represents the number of bags that have at least $i$ coins. If you plug in $n=185$ into the formula, you get $997$, which proves that saving 815 coins is impossible. If $n=186$, the sum is $1005$ which is over 1000, and it is indeed possible to construct the list of bags to save 814 coins (as tehtmi already showed).

Bubbler
  • 13,734
  • 1
  • 23
  • 89
  • 1
    I found your explanation a little confusing. Its not clear to me why adding up the number of bags that have at least i coins needs to be under 1000. The way I made sense of your maths is to say that each term represented the number of coins in the ith bag. Therefore after summing over i if you have less than 1000 you have coins still needing to go in bags and if the sum is over 1000 you can have a few less one coin bags. I still can't get my head around adding up number of bags... – Chris Oct 23 '20 at 11:21
  • 1
    @Chris Interpret each term of the sum as "the number of bags containing at least i coins". First few terms for n=185 are 185, 92, 61, 46, ... which means 185 bags with at least one coin, 92 bags with at least two coins, ... To see how they add up to the maximum possible total coins, imagine horizontal strips having the lengths, left-aligned, and observe that the vertical strips are the amount of coins in each bag. – Bubbler Oct 23 '20 at 13:34
  • 1
    OK, yeah, I think I can see what you mean now. I was actually quite pleasantly surprised that the numbers in the series were the same your way and as number of coins in ith bag. I guess that's because 1/x is its own inverse so if you swap your axes you basically get the same numbers. – Chris Oct 23 '20 at 15:50
11

You can solve the problem via integer linear programming as follows. Let $n$ be the number of coins, so we need at most $n$ bags. For $b \in \{1,\dots,n\}$, let nonnegative integer decision variable $x_b$ be the number of coins in bag $b$, with $x_b$ nonincreasing. Let $z$ represent $\max_b \{b\cdot x_b\}$, which is the number of coins the king will take. The problem is to minimize $z$ subject to \begin{align} \sum_b x_b &= n \tag1 \\ x_b &\ge x_{b+1} &&\text{for $b\in\{1,\dots,n-1\}$} \tag2 \\ z &\ge b\cdot x_b &&\text{for $b\in\{1,\dots,n\}$} \tag3 \end{align} Constraint $(1)$ assigns all the coins to bags. Constraint $(2)$ imposes nonincreasing order. Constraint $(3)$ enforces $z\ge \max_b \{b\cdot x_b\}$.

For $n=1000$, the optimal objective value is $186$, which yields $1000-186=814$ remaining coins, as shown by others.

RobPratt
  • 13,685
  • 1
  • 29
  • 56
4

I will put 500 coins in one bag and then I will put another 1 coin in each of another 500 bags.

If the king chooses the number 1, I will have 499 coins, if the king chooses the number 500, I will have 500 coins, and if the king chooses anything in between, I will have more than 499 coins.

So my answer is: the maximum amount of gold coin can you guarantee to have at the end of the king's game is 499 coins.

Edit: I'm sure @tehtmi's answer is correct. Kind of irrelevant to my answer, but here is a code for you to experiment with different bag combinations. Simply fill in the bags list and run the program:

For bags I used:

[500, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

And @tehtmi used:

[186, 93, 62, 46, 37, 31, 26, 23, 20, 18, 16, 15, 14, 13, 12, 11, 10, 10, 9, 9, 8, 8, 8, 7, 7, 7, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

bags = [] # Put in this list all the numbers you want, with each number representing a bag of that amount of coins

keeps = [] # Here is where the number of coins I can guarantee to keep in each possible situation
for n in set(bags): # This loop is to loop over each number the king might choose
    lose = 0 # Here is the number of coins the king took
    keep = 0 # Here is the number of coins I keep
    for i in bags: # For each bag
        if i < n: # If the number of coins in that bag is less than the king's number
            keep += i # The king won't be able to score any because he cannot remove from a smaller number to match his number
        else: # If the number of coins in that bag is greater than the king's number
            lose += n # He can score some more coins by taking some out
            keep += i - n # At the same time I can only keep the number of coins in that bag minus the amount the king took
    keeps.append(keep) # Now add the result into our list of results


print(min(keeps)) # Finally, I print out the maximum amount of gold coin can I guarantee to have at the end
risky mysteries
  • 13,072
  • 3
  • 24
  • 96