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