dino_merlin's blog

Mathematical proof needed
By dino_merlin, history, 5 years ago, In English

Does anyone have mathematical proof for the solution of CF #614 Div. 2 B. The tutorial says that it: "It is easy to see that we will want each question to eliminate one opponent only, since after each elimination, the ratio t/s will be more and more rewarding ". But that doesnt say much. https://mirror.codeforces.com/contest/1293/problem/B

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by dino_merlin (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can prove it with a simple induction on $$$t$$$.

→ Reply
»
5 years ago, # |
← Rev. 6   Vote: I like it +2 Vote: I do not like it

Let f(n) be the max prize with n contestants. Then obviously f(1) = 1. We will prove with mathematical induction that $$$f(n) = \sum_\limits{i=1}^{n}\frac{1}{i}$$$

Assume that for every positive k<n: $$$f(n-k) = \sum\limits_{i=1}^{n-k}\frac{1}{i}$$$.

Then it is clear that $$$f(n) = \max\limits_{k=1}^{n-1}(f(n-k)+\frac{k}{n})$$$. And the maximum is attained at k=1 as the series $$$a_k=f(n-k)+\frac{k}{n}$$$ is strictly decreasing, because: $$$a_k-a_{k-1}=f(n-k)-f(n-(k-1))+\frac{k}{n}-\frac{k-1}{n}=-\frac{1}{n-k+1}+\frac{1}{n}<0$$$, when k>1.

So: $$$f(n)=f(n-1)+\frac{1}{n}=\sum_\limits{i=1}^{n}\frac{1}{i}$$$ which is what we set out to prove.

→ Reply