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?