## combinatorics Greedy Trolls

Discussions concerned with knowledge of measurement, properties, and relations quantities, theoretical or applied.

### combinatorics Greedy Trolls

Three trolls go questing in a dungeon in the mountains outside of the village. Deep within the dungeon they encounter a wizard who has powerful magic. The wizard guards a collection of 56 rare magical Elven coins.

The wizard wants to escape unharmed, so he makes a deal with the trolls. He says that he will give you all his magic coins, provided you specify a bag of size k. The coins will be placed into a first bag in sets of exactly size k, and continue to fill up bags until all possible sets of size k are exhausted. Since the coins are magical, they will duplicate themselves until all bags are filled. For example, if a troll were to say his bags all hold one coin (k=1) then he leaves the dungeon with 56 bags.

Original set of 56 coins :

If a bag size is chosen to be two (k=2) then the chooser will get a bag with {a,b} but not a {b,a} bag, as they are the same "set" of coins.

The trolls reason among themselves and know that a bag can easily score 3 silver dugat at the marketplace. Each bag would be sold as one unit, regardless of the number of coins inside that bag. They conclude that they should choose a bag size that maximizes the number of take-home bags.

The first troll speaks quickly, "I want a bag size of 56 coins!" , (expecting to receive a factorial or whatever.) The wizard hands him 1 bag. That is the only set of size 56. He returns to the village humiliated.

The second troll thinks a little and responds, "I want bags of size three." The wizard obliges and hands him 27,720 bags. Later at the market, the troll notices that he has a bag of {d,J,k} but no {J,k,d} bag, as those are the same "set".

I. What size bag should the third troll choose to outdo his competitors?

II. What bag size would maximize the profits at the market?

III. What would be the maximum profit, exactly?
Attachments

hyksos
Active Member

Posts: 1173
Joined: 28 Nov 2014

### Re: combinatorics Greedy Trolls

(bump)

hyksos
Active Member

Posts: 1173
Joined: 28 Nov 2014

### Re: combinatorics Greedy Trolls

Hint

Consider a string of 13 distinct letters.

fijw nqsa potu x

All permutations of that string are unique.

Consider a string of 13 bits.

0110 1000 1010 1

If we produce permutations of these bits, some permutations will match, due to the fact that a 1 is the same as all the other 1's. Consider a string of bits where they are all zeroes.

0000 0000 0000 0

There exists one, and only one, permutation of that string. Itself.

This is all the hints you should need to solve the trolls problem above.

hyksos
Active Member

Posts: 1173
Joined: 28 Nov 2014