1000 gold coins to share with the king

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 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