28
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ Why would the King not chose "1", and then "put out" all gold coins in excess of 1, giving the King all the gold? $\endgroup$
    – Michael Richardson
    Commented Oct 23, 2020 at 19:22
  • 7
    $\begingroup$ I think the meaning of "put out" is unclear. I think you mean the Knight gets the put out coins? $\endgroup$
    – Douglas Leeder
    Commented Oct 23, 2020 at 20:27
  • 3
    $\begingroup$ 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? $\endgroup$
    – David Conrad
    Commented Oct 23, 2020 at 23:02

4 Answers 4

Reset to default
27
$\begingroup$

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.

Improve this answer
$\endgroup$
16
  • $\begingroup$ I just thought the same strategy as this one. $\endgroup$
    – Bubbler
    Commented Oct 22, 2020 at 22:46
  • $\begingroup$ 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. ? $\endgroup$
    – risky mysteries
    Commented Oct 22, 2020 at 22:48
  • $\begingroup$ @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. $\endgroup$
    – tehtmi
    Commented Oct 22, 2020 at 22:52
  • $\begingroup$ Thank you! ---- $\endgroup$
    – risky mysteries
    Commented Oct 22, 2020 at 22:53
  • 1
    $\begingroup$ @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). $\endgroup$
    – tehtmi
    Commented Oct 23, 2020 at 23:12
14
$\begingroup$

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).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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... $\endgroup$
    – Chris
    Commented Oct 23, 2020 at 11:21
  • 1
    $\begingroup$ @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. $\endgroup$
    – Bubbler
    Commented Oct 23, 2020 at 13:34
  • 1
    $\begingroup$ 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. $\endgroup$
    – Chris
    Commented Oct 23, 2020 at 15:50
11
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice application of integer programming. $\endgroup$
    – Idonknow
    Commented Oct 23, 2020 at 14:41
4
$\begingroup$

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
Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ @Jingbothedude You put >! before your sentence. $\endgroup$
    – risky mysteries
    Commented Oct 23, 2020 at 17:14

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