$k$ people start at $h=1$; if there are three people at height $t>0$, they compete and the winner goes up to $t+1$ while the two others go to $t-1$. Reaching height 0 results in the person being eliminated. If there are at most two people at any height, and the person/people at the highest height win. I'm trying to
- prove the game terminates/upper bound on number of competitions
- find how high up the top person will be
- prove that the order of competitions does not change the number of competitions at each height or how many people end up at each height
My reasoning so far:
It seems that $\phi(x_1,...,x_n)=\sum_{i=1}^n$ decreases by one each time there is a competition meaning that it will eventually reach zero -- I'm not sure how to make this a proper proof (induction?)
I'm guessing the height has something to do with $\log_3$ as it takes three people to advance one of the people one.
I don't know how to formalize the idea that a person can only advance once two others join him, so he will "wait", which is what leads to the invariant.