13
$\begingroup$

You and your friend has found in total 2019 gold coins in a treasure hunt. Since your friend found the place to dig up, he deserves a bit more gold than you so you offer a game to share the coins to him:

"We have 2019 coins, I will put as many of the coins as I want into a bag and you will see how many coins I place inside. Every time I have finished putting coins into a bag, you will (based on the number of coins in the bag) determine whether or not you want that bag. If you don't want that bag, I will take it. Then I will start putting coins into another bag and so on...

After one of us has 13 bags in total, we will stop playing the game, and the rest of the coins will be given to whomever doesn't have 13 bags."

Your friend likes the game and accept the offer. He thinks this is a fair game to share the coins.

At least how many gold coins can you guarantee to win at the end of this game?

for example: you put 50 coins in the first bag then your friend decides not to take that bag, after that you decide to put 100 coins into another bag, this time your friend decides to take that bag... etc.

Improve this question
$\endgroup$
4
  • $\begingroup$ I find the wording a bit confusing, could you clarify a couple of things: 1: Do I fill the bags one-by-one or all at once? 2: Do you get to know in advance how many coins I'm going to put into each bag? 3: If more than one bag is getting filled at the same time, which one of them do you get to choose for you or me? 4: How does the "knowing how many golds inside" thing affect the result? You saw every coin that was put into the bags, so you know exactly how many coins there are. $\endgroup$
    – Bass
    Commented Jun 8, 2019 at 14:23
  • $\begingroup$ Why was this downvoted? Seems like a nice puzzle to me...Perhaps it was because the wording was a little confusing? I'll try an edit. $\endgroup$
    – Brandon_J
    Commented Jun 8, 2019 at 15:00
  • 2
    $\begingroup$ @Brandon_J Sorry what does Since your friend found to place to dig up mean? $\endgroup$
    – Andrew Savinykh
    Commented Jun 9, 2019 at 5:27
  • $\begingroup$ Does this answer your question? The Devil's Brother $\endgroup$
    – Hemant Agarwal
    Commented Jan 30, 2022 at 13:18

2 Answers 2

Reset to default
13
$\begingroup$

I can ensure that I receive at least

1005 coins.


To get this amount of coins, I could apply the following strategy:

I put 78 coins in each bag. Now if I get 13 bags earlier than my friend, then I have $13 \cdot 78 = 1014$ coins,. If my friend however takes 13 bags, then he has 1014 coins, and I get the 1005 remaining coins.

My friend can also ensure that I do not get more coins than this in the following way:

He can take any bag with at least 78 coins, and return any bag with at most 77 coins. Now if I get 13 bags earlier than him, this means that I get at most $13 \cdot 77 = 1001$ coins. But if he get 13 bags earlier than me, he gets at least $13 \cdot 78 = 1014$ coins, and I get at most $2019-1014 = 1005$ coins.


So it appears that I should have chosen a fairer game to distribute the coins...

Improve this answer
$\endgroup$
4
  • $\begingroup$ Looks like we arrived at the same conclusion, but in slightly different ways. You did get there first, of course, so congrats! $\endgroup$
    – Brandon_J
    Commented Jun 8, 2019 at 14:48
  • $\begingroup$ @Brandon_J I found the threshold in the friends strategy by dividing by 26 instead of 25, since he wants to get at least half of the coins when he takes 13 of the bags. $\endgroup$
    – Reinier
    Commented Jun 8, 2019 at 15:01
  • $\begingroup$ Ah - that explains why you got there faster. $\endgroup$
    – Brandon_J
    Commented Jun 8, 2019 at 15:01
  • $\begingroup$ You can actually generalize this approach to work for $n$ coins and stopping at $k$ bags: then we put $\frac{n}{2k}$ coins rounded to the nearest integer in each bag, and our friend only takes bags with at least $\frac{n}{2k}$ coins. $\endgroup$
    – Reinier
    Commented Jun 8, 2019 at 15:03
5
$\begingroup$

A note: @Reinier, besides having an awesome palindromic username, also solved this puzzle first (my solve was still independent). I like my explanation better (but of course I'm biased), but if you upvote my answer, don't forget to upvote Reinier's as well.

So, it's somewhat apparent that we need to find

the optimal strategy (for us) in the worst-case scenario (our friend tries to get as many coins as he can).

Here's my basic strategy:

The maximum number of bags that may be filled is 25. This is because the game ends when one person gains 13 bags. Consequently, if we divide all the coins equally among the bags, then the worst we can get is 12/25 of the loot. Of course, we can't quite divide them equally, so we will fill 6 of them with 80 coins, and 19 of them with 81 coins.

When we present each bag to our friend,

The best-case scenario for him/her is to gather 13 of the 19 81-coin bags. This leaves us with $81 * 6 + 80 *6 = 966$ coins to his $31 * 81 = 1,053$.

Essentially, the friend's strategy is to

keep any bag with more than 80 coins, and give us any bag with 80 coins or less.

There is, of course, a slight work-around that can get us a liiiitle bit more.

If we present a continual stream of

80-coin bags, then the friend's best bet is to give us the first 12 bags, but then give himself the rest of the bags. This improves things a little bit - our friend only gets $1,040$ coins, and we get $979$.

What if we present a continual stream of

79-coin bags? The best our friend can get is $1,027$, and we get $998$ That's even better!

What if we present a continual stream of

78-coin bags? The best our friend can get is $1,014$, and we get $1,005$ That's even better!

What if we present a continual stream of

77-coin bags? The best our friend can get is $1,024$, and this is if he gives us all 13 of the 77-coin bags. Previously, he ended up giving himself all of the bags, so it looks like the highest point we can reach is with 78-coin bags.

So, the altered strategy of our friend is to

keep any bag with more than 77 coins. $13*78$ coins gives him a majority of the coins, while $13*77$ coins gives him a minority of the coins.

We can infer that we can do no better than

78-coin bags

because

Every bag must be above, below, or at 78 coins. If we present to our friend bags with less than 78 coins, he gives them to us, and we're playing a non-optimal strategy. If we present him with more, he goes ahead and takes it, increasing his potential winnings.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I thought about it like this: There are 2019 coins and if I am the friend who chooses, I want to get at least the majority of the coins which is 1010 coins. 1010 coins in 13 bags is 77.69 coins per bag. So If I am the friend, I want to take bags with at least 78 coins or more. I just noticed that Reiner said the same thing with his n/2k formula. $\endgroup$
    – JS1
    Commented Jun 10, 2019 at 21:58

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