1000 gold coins to share with the knight

Question

Note: This riddle is similar to this riddle: 1000 gold coins to share with the king, except now YOU are the king, and the rules are switched up a bit. And the situation is wackier...

You are the King of a great kingdom in an unknown world. You sent a knight to a dungeon and he killed the dragon and retrieved 1000 gold coins from the dragon’s lair. Normally, you are supposed to reward the knight.

Congratulations, you've collected 1000 gold coins for my kingdom. I would like to reward for your brave effort in the dungeon. To do so, I will place all the coins into my chosen number of bags. Each bag will not be empty, but the number of coins in each bag may vary.

After that, you can see how many gold coins are in each of them, and you will choose a number and take all bags with that amount of gold coins. To make it better for you, you may take along with you 100 extra gold coins from my castle, and put some into the bags to increase amount of gold coins you can acquire. The remaining coins you don't use will be returned to my castle.

After that, naturally you would like to minimize the amount of coins the knight will take.

What is the minimum amount of gold coins you can guarantee to lose in total at the end of your game? (The extra coins also count)

For example;

If there were 20 coins, and the knight has 3 gold coins to use, and you put those coins into 6 bags; 2-2-2-3-7-4, the maximum number of gold coins the knight can take would be 14 because the knight may choose the number 7 and put the three coins into the four-coined bag.

Answer 1

We can limit the loss to

258 coins using 350 bags [for earlier revisions of this answer, I had 260, 264 and 270 coins - see the edit history]

Bags are as follows:

15 bags containing the following coin counts: 158, 57, 41, 34, 27, 23, 21, 17, 17, 14, 14, 12, 11, 11, 10
2 bags with 9 coins
3 bags with 8 coins
3 bags with 7 coins
5 bags with 6 coins
6 bags with 5 coins
7 bags with 4 coins
22 bags with 3 coins
29 bags with 2 coins
258 bags with 1 coin

Examples of results for different sizes the knight could pick:

• Picking the size 158 bag, and adding 100 coins to it to make 258

• Picking the size 41 bag, using a total of 83 coins to top the next 5 smaller bags to 41, then adding 2 more coins to each bag (total 12), leaving 5 coins unused. 43 x 6 = 258.

• Picking the size 3 bags, using 29 coins to top up all the size 2 bags, and a further 70 coins to top up 35 size 1 bags. 3 x 86 = 258.

• Picking the size 10 bag, using a total of 97 coins to top up all the bags of size 5-9, and 5 of the size 4 bags. 25 bags total. 10 x 25 = 250 - the knight has several better options!

This seems even closer to optimal because

Even 260 was particularly tight when using a manual search, and I'd previously speculated that there may be insufficient "wiggle room" to get the maximum any lower. Now I've resorted to an exhaustive computer search, better solutions are presenting themselves...

Some notes on technique and strategy:

I put together a spreadsheet which

starts from the smallest bag sizes, and calculates for each larger bag size how many bags can actually be taken using the budget of 100 extra coins to top up the next-smallest bags, and gives a FULL total of how much the knight will get using the obvious bag-filling strategy (keep filling the next-largest bag until you've not got enough coins, then if possible split any remaining coins evenly between the bags you're taking).

In the final configuration shown above, it looks like this:

Some explanation:

"Simple" is just how many coins there are in the bags of the specified size.
"FULL" is the total amount the knight can take, comprising Simple, Upgraded, and Bags x XtraCount
"Upgraded" is the total coins in bags that have had coins added.
"Upcount1" is the number of bags of the next-smallest size that have had coins added, which is then multiplied by the difference in bag size to get "upcoins1".
Next 9 columns are implied as "Upcount2" to "Upcount10", which was as many as I needed.
"Bags" is the total of the number bags of that size, plus all the bags that could be upgraded by adding coins.
"SpareCoins" is the number of coins left over from the 100 after upgrading as many bags as possible.
"XtraCount" divides "SpareCoins" evenly into the "Bags".

The spreadsheet can also automatically calculate

"Count" based on how many coins are spare taking into account "Upgraded" for the next proposed coin size, and the maximum value of FULL encountered so far. This was useful for the first solutions, but for the later ones, I found that manually tweaking was easier, especially given that it doesn't take SpareCoins into account (which were added later). When I referred to "wiggle room" it's the ability to slightly change some of the numbers in Size and Count columns whilst still keeping the FULL column within the currently-chosen limit.

One important point not directly known by the spreadsheet is that

The second-largest bag should be at least 101 coins smaller than the largest, so that the knight cannot take both.

A few more notes on how I initially used this spreadsheet:

• First, I was considering the question "Can we limit losses to 200?" This is a special number because, considering only the bags of size 1, the knight can get this much when we have 100 bags of size 1, but he can still only get 200 when we have 200 bags of size 1... so 200 bags with 1 gold seemed a good starting point to investigate. Redoing the investigation with the latest version of the spreadsheet, it's a fairly mechanical process to get 425 gold into bags of up to 30 coins without the knight being able to get more than 200, but as I considered the next bag, I realised there was no larger size of bag possible without breaking the 200 total.

• I then tried a fairly generous maximum of 300, on each row having as many "small" bags as possible without allowing the knight to take that many. Following a similarly mechanical process (maximum number of bags without breaking the total, or next-largest bag that doesn't break the total), this clearly had plenty of spare capacity, as I'd placed 1000 gold before the bag size even reached 30 gold per bag:

• Then I tried 250, which didn't work, and 270 which led to my first posted answer - the only change from following this purely mechanical process was to remove the size 70 bag, allowing the largest bag to be reduced to 170 and the remaining gold shortfall to be made up by removing size 1 bags.

• Noticing that several rows had totals of exactly 270, this suggested that numbers with plenty of factors were good limits, which is why I chose 264 for the next target, although the solution I posted was different to the one that a purely mechanical approach would have got (shown below), because I'd switched to manually tweaking by then...

• Although I didn't perform an EXHAUSTIVE search, the search space for 260 felt very tight - if I'd gone back to the purely mechanical approach, it would have exceeded the gold available by only 7 in the final bag (excess gold is dealt with simply by having fewer size 1 bags), and distribution pretty similar to my actual final result at the time:

• I next tried a 258 limit, and when that seemed insufficient, relaxed that to 259 (allowing more size 1 and 7 bags), but this still didn't seem good enough. For illustration, here's the same mechanical process re-applied to 259 (the size of the very largest bags can be freely increased by 4 gold each without affecting any other totals, and more gold can be squeezed in by re-arranging the exact sizes of some other intermediate bags, where I easily reached 987 and another total higher than 990 which I can't remember, but I can't beat @Oray's 995, and suspect that this is indeed the maximum):

So far, this only established (by example) an upper bound for the final answer, and the only proof of lower bound is "I tried lots of ideas to lower it, and none of them worked". Lacking better ideas for proof of impossibility to establish a lower bound, I converted the calculations in the spreadsheet to an exhaustive computer search. This found

LOTS of solutions for a 260 limit (to confirm the program was working), which I aborted - sample output:
...
1 x 260, 2 x 30, 3 x 21, 4 x 8, 5 x 7, 6 x 4, 7 x 4, 8 x 2, 9 x 2, 10 x 2, 11 x 1, 12 x 1, 13 x 2, 15 x 1, 16 x 1, 18 x 1, 23 x 1, 25 x 1, 39 x 1, 40 x 1, 59 x 1, 160 x 1
1 x 260, 2 x 30, 3 x 21, 4 x 8, 5 x 7, 6 x 4, 7 x 4, 8 x 2, 9 x 2, 10 x 2, 11 x 1, 12 x 1, 13 x 2, 15 x 1, 16 x 1, 18 x 1, 23 x 1, 25 x 1, 39 x 1, 41 x 1, 58 x 1, 160 x 1
1 x 260, 2 x 30, 3 x 21, 4 x 8, 5 x 7, 6 x 4, 7 x 4, 8 x 2, 9 x 2, 10 x 2, 11 x 1, 12 x 1, 13 x 2, 15 x 1, 16 x 1, 18 x 1, 23 x 1, 25 x 1, 40 x 2, 58 x 1, 160 x 1
1 x 260, 2 x 30, 3 x 21, 4 x 8, 5 x 7, 6 x 4, 7 x 4, 8 x 2, 9 x 2, 10 x 2, 11 x 1, 12 x 1, 13 x 2, 15 x 1, 16 x 1, 18 x 1, 23 x 1, 26 x 1, 30 x 1, 48 x 1, 59 x 1, 160 x 1
1 x 260, 2 x 30, 3 x 21, 4 x 8, 5 x 7, 6 x 4, 7 x 4, 8 x 2, 9 x 2, 10 x 2, 11 x 1, 12 x 1, 13 x 2, 15 x 1, 16 x 1, 18 x 1, 23 x 1, 26 x 1, 30 x 1, 49 x 1, 58 x 1, 160 x 1
...
Many more solutions for a 259 limit, so as I went to post an update with this, I ran it for a 258 limit. This initially found a single solution, so speculating this might be a unique solution, I started writing the current update, and just as I was writing it, another batch of solutions were found... full output at time of writing:
1 x 258, 2 x 29, 3 x 22, 4 x 7, 5 x 6, 6 x 5, 7 x 3, 8 x 3, 9 x 2, 10 x 1, 11 x 2, 12 x 1, 14 x 2, 17 x 2, 21 x 1, 23 x 1, 27 x 1, 34 x 1, 41 x 1, 57 x 1, 158 x 1
1 x 258, 2 x 29, 3 x 22, 4 x 7, 5 x 6, 6 x 5, 7 x 3, 8 x 3, 9 x 2, 10 x 1, 11 x 2, 12 x 1, 14 x 1, 15 x 1, 16 x 1, 17 x 1, 21 x 1, 23 x 1, 27 x 1, 34 x 1, 41 x 1, 57 x 1, 158 x 1
1 x 258, 2 x 29, 3 x 22, 4 x 7, 5 x 6, 6 x 5, 7 x 3, 8 x 3, 9 x 2, 10 x 1, 11 x 2, 12 x 1, 14 x 1, 15 x 1, 16 x 1, 17 x 1, 21 x 1, 23 x 1, 27 x 1, 35 x 1, 40 x 1, 57 x 1, 158 x 1
1 x 258, 2 x 29, 3 x 22, 4 x 7, 5 x 6, 6 x 5, 7 x 3, 8 x 3, 9 x 2, 10 x 1, 11 x 2, 12 x 1, 14 x 1, 15 x 1, 16 x 1, 17 x 1, 21 x 1, 23 x 1, 28 x 1, 34 x 1, 40 x 1, 57 x 1, 158 x 1
1 x 258, 2 x 29, 3 x 22, 4 x 7, 5 x 6, 6 x 5, 7 x 3, 8 x 3, 9 x 2, 10 x 1, 11 x 2, 12 x 1, 14 x 1, 15 x 1, 16 x 1, 17 x 1, 21 x 1, 24 x 1, 27 x 1, 34 x 1, 40 x 1, 57 x 1, 158 x 1
1 x 258, 2 x 29, 3 x 22, 4 x 7, 5 x 6, 6 x 5, 7 x 3, 8 x 3, 9 x 2, 10 x 1, 11 x 2, 12 x 1, 14 x 1, 15 x 1, 16 x 1, 17 x 1, 22 x 1, 23 x 1, 27 x 1, 34 x 1, 40 x 1, 57 x 1, 158 x 1
1 x 258, 2 x 29, 3 x 22, 4 x 7, 5 x 6, 6 x 5, 7 x 3, 8 x 3, 9 x 2, 10 x 1, 11 x 2, 12 x 1, 14 x 1, 15 x 1, 16 x 1, 18 x 1, 21 x 1, 23 x 1, 27 x 1, 34 x 1, 40 x 1, 57 x 1, 158 x 1
1 x 258, 2 x 29, 3 x 22, 4 x 7, 5 x 6, 6 x 5, 7 x 3, 8 x 3, 9 x 2, 10 x 1, 11 x 2, 12 x 1, 14 x 1, 15 x 1, 17 x 2, 21 x 1, 23 x 1, 27 x 1, 34 x 1, 40 x 1, 57 x 1, 158 x 1
1 x 258, 2 x 29, 3 x 22, 4 x 7, 5 x 6, 6 x 5, 7 x 3, 8 x 3, 9 x 2, 10 x 1, 11 x 2, 12 x 1, 14 x 1, 16 x 2, 17 x 1, 21 x 1, 23 x 1, 27 x 1, 34 x 1, 40 x 1, 57 x 1, 158 x 1
Trying [...]
The code was sufficiently poorly optimised (and/or the search space sufficiently large) that it didn't make much further progress even when left running for a couple of days. I found additional solutions when running searches starting from different numbers of size 1 bags, including some with fewer bags (349 or 348 bags total rather than the 350 bag solution at the top of this post). I think it would take many years to complete the search with that code.
I also ran searches for 257 and 256 in parallel and got no results. @RobPratt used a different technique that appears to prove 258 optimal.
I personally find it mildly disappointing that there wasn't a unique optimal solution - there seem to be at least a couple of dozen...

Answer 2

Here is my edited improved answer, not sure optimal, there is a methodology but not sure about its optimality anyway:

I will use 344 bags to minimize the lost as 260g in total.

For this,

I will put the coins in the bags as below:

As a result,

our knight would take 260g at most which is the minimum lost for the king.

The idea actually begins with 1 gold coin taking, I wrote a program to find out the minimum with the maximum amount of bags with the minimum amount of coins in them and I got the same end result with @Steve. Not sure it could be improved. a little tweak I used but I couldnt hit to 259 whatsoever.

Here is my best score with 259:

995

as below

1|259|259
2|29|317
3|22|383
4|7|411
5|6|441
6|5|471
7|4|499
8|2|515
9|2|533
10|1|543
11|2|565
12|1|577
13|1|590
14|1|604
15|1|619
16|1|635
19|1|654
23|1|677
25|1|702
30|1|732
47|1|779
57|1|836
159|1|995

Answer 3

You can solve the problem via integer linear programming as follows. Let $n$ be the number of coins, and let $k$ be the number of extra coins the knight can use. For $b \in \{1,\dots,n\}$, let nonnegative integer decision variable $x_b$ be the number of coins the king places in bag $b$, with $x_b$ nonincreasing. Let $z$ represent the number of coins the knight takes. For $1 \le i \le j \le n$, let nonnegative decision variable $$r_{i,j}=\frac{\sum_{b=i}^j x_b + k}{j-i+1},$$ and let nonnegative integer decision variable $f_{i,j} = \left\lfloor r_{i,j} \right\rfloor$. The knight will choose $j-i+1$ bags $\{i,\dots,j\}$, with $x_i \le f_{i,j}$ and $x_j \ge 1$, and use up to $k$ extra coins to get the highest possible multiple of $j-i+1$ in each bag, yielding $(j-i+1)f_{i,j}$ coins.

The king's 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 [x_i \le f_{i,j}] [x_j \ge 1] (j-i+1) f_{i,j} &&\text{for $1\le i\le j \le n$} \tag3 \end{align} Constraint $(1)$ assigns the $n$ coins to bags. Constraint $(2)$ imposes nonincreasing order. Constraint $(3)$ captures the knight's optimal strategy. Although this constraint is nonlinear, it can be linearized by introducing binary decision variables $s_{i,j}$, $p_j$, and $y_{i,j}$, along with linear big-M constraints \begin{align} f_{i,j} + 1 - x_i &\le M^1_{i,j} s_{i,j} \tag{3a} \\ x_j &\le M^2_j p_j \tag{3b} \\ s_{i,j} + p_j - 1&\le y_{i,j} \tag{3c} \\ (j-i+1)f_{i,j} - z &\le M^3_{i,j} (1-y_{i,j}) \tag{3d} \end{align} and other linear constraints that enforce $f_{i,j}= \left\lfloor r_{i,j} \right\rfloor$: \begin{align} f_{i,j} &\le r_{i,j} \tag{3e} \\ (j-i+1)(f_{i,j} + 1) &\ge (j-i+1)r_{i,j} + 1 \tag{3f} \end{align}

Although there are $O(n^2)$ of these constraints, they can be generated dynamically only when violated (a cutting-plane or row generation approach).

For $n=1000$ and $k=100$, the optimal objective value is $258$, which confirms that @Steve's upper bound cannot be improved.