You are given k coins, arranged in k stacks of height 1. A “move” involves choosing a stack and redistributing all of its coins into other stacks, but when doing this each of the stacks can receive at most one coin. During the move, you are allowed to make new stacks (in fact this is unavoidable if you don’t have enough existing stacks in which to place all the coins), but again only one coin can go in each new stack. The reward of one move is precisely the number of coins in the stack that you choose to redistribute. Suppose that you get to make some huge number of moves (say, n, far greater than k).
(a) Develop a strategy to maximize your average reward per move (equivalent to maximizing the total reward over n moves). Express this as a function of k, using Θ- notation. Notice that any strategy provides a lower bound on reward optimality. The better the strategy, the better (higher) the lower bound.
(b) Use amortization (specifically, the potential method) to obtain an upper bound on the best possible average reward. If it helps to think in terms of cost instead, pretend that your friend is playing this game and you must pay their reward. In this context, you want to find an upper bound on the average cost per move. For amortization, as usual, you want to show that “expensive” moves do not happen that often. You will need a potential function that offsets expensive moves, making their amortized cost relatively smaller. So, first think about defining what an expensive move is, and what a non-expensive move is. It will help to have a good strategy in part (a) to determine what the cutoff should be. Then think about something that changes a lot in the configuration of stacks whenever you have an expensive move, and use that as your ∆Φ. Always remember that when you evaluate Φi at any given time, you are taking a snapshot of the current state of the world. Φ cannot be a function of “what changed” between two iterations. That is the job of ∆Φ.
My strategy to maximize the average reward is to choose the largest stack of coins in each move. If there are multiple stacks with the same largest number of coins, then randomly choose one of the stacks. I am unable, however, to express this strategy as a function of k. I believe the minimum lower bound using this strategy is k/2 as eventually there will be an oscillation of coins between stacks. I, additionally, am lost on how to even begin calculating the upper bound. Any help would be greatly appreciated.
Here is a target. Let us assume $k$ is a triangular number, so $k=\frac 12m(m+1)$ for some $m$. If I have stacks of $1,2,3,\ldots m$ I can take the stack of $m$, put one coin on each other stack and one coin to start a new stack. After one move I have exactly the same distribution as I started with, so I can keep doing this forever, getting a reward of $m=\frac 12(-1+\sqrt{1+8k})$. As the question states, this is now a lower bound for the achievable reward per round. I suspect it is optimal because if you distribute a huge stack you have lots of small stacks for a while. As we are just asked for $\Theta$ notation this is $\Theta(\sqrt{k})$ and you just have to prove you can't beat that