Problem 950

Pirate Treasure

A band of pirates has come into a hoard of treasure, and must decide how to distribute it amongst themselves. The treasure consists of identical, indivisible gold coins.

According to pirate law, the distribution of treasure must proceed as follows:

The most senior pirate proposes a distribution of the coins.
All pirates, including the most senior, vote on whether to accept the distribution.
If at least half of the pirates vote to accept, the distribution stands.
Otherwise, the most senior pirate must walk the plank, and the process resumes from step 1 with the next most senior pirate proposing another distribution.

The happiness of a pirate is equal to $-\infty$ if he doesn’t survive; otherwise, it is equal to $c + p\cdot w$, where $c$ is the number of coins that pirate receives in the distribution, $w$ is the total number of pirates who were made to walk the plank, and $p$ is the bloodthirstiness of the pirate.

The pirates have a number of characteristics:

Greed: to maximise their happiness.
Ruthlessness: incapable of cooperation, making promises or maintaining any kind of reputation.
Shrewdness: perfectly rational and logical.

Consider the happiness $c(n,C,p) + p\cdot w(n,C,p)$ of the most senior surviving pirate in the situation where $n$ pirates, all with equal bloodthirstiness $p$, have found $C$ coins. For example, $c(5,5,\frac{1}{10}) = 3$ and $w(5,5,\frac{1}{10})=0$ because it can be shown that if the most senior pirate proposes a distribution of $3,0,1,0,1$ coins to the pirates (in decreasing order of seniority), the three pirates receiving coins will all vote to accept. On the other hand, $c(5,1,\frac{1}{10}) = 0$ and $w(5,1,\frac{1}{10}) = 1$: the most senior pirate cannot survive with any proposal, and then the second most senior pirate must give the only coin to another pirate in order to survive.

Define $\displaystyle T(N,C,p) = \sum_{n=1}^N \left( c(n,C,p) + w(n,C,p) \right)$. You are given that $T(30,3,\frac{1}{\sqrt{3}}) = 190$, $T(50,3,\frac{1}{\sqrt{31}}) = 385$, and $T(10^3, 101, \frac{1}{\sqrt{101}}) = 142427$.

Find $\displaystyle \sum_{k=1}^6 T(10^{16},10^k+1,\tfrac{1}{\sqrt{10^k+1}})$. Give the last $9$ digits as your answer.

海盗宝藏

一群海盗找到了一堆宝藏，需要决定如何进行分配。这些宝藏由完全相同且不可分割的金币组成。

根据海盗法则，宝藏分配必须按照以下流程进行：

资历最深的海盗提出一个金币分配方案。
所有海盗，包括资历最深的海盗，共同投票决定是否接受该分配方案。
如果至少一半的海盗投票同意，则该分配方案生效。
否则，资历最高的海盗将被迫走跳板投海，然后回到第1步，由资历次深的海盗提出另一个分配方案。

如果一个海盗无法存活，其幸福度是$-\infty$，否则则是$c + p\cdot w$，其中$c$是该海盗在最终生效的分配方案中获得的金币数量，$w$是被迫走跳板投海的海盗数量，$p$则是该海盗的嗜血度。

海盗们有以下特征：

贪婪：总是最大化他们的幸福度。
无情：无法合作、做出承诺或维持任何形式的声誉。
精明：完全理性和有逻辑。

考虑在$n$个（嗜血度均为$p$的）海盗发现了$C$个金币的情况下，幸存海盗中资历最深者的幸福度$c(n,C,p) + p\cdot w(n,C,p)$。例如，$c(5,5,\frac{1}{10}) = 3$且$w(5,5,\frac{1}{10})=0$，这是因为可以证明，如果资历最深的海盗提出将$3,0,1,0,1$个金币分配给海盗们（按资历递减顺序），则获得金币的三个海盗都会投票接受这个方案。另一方面，$c(5,1,\frac{1}{10}) = 0$且$w(5,1,\frac{1}{10}) = 1$：资历最深的海盗无论提出任何提案都无法存活，而资历次深的海盗为了存活必须将唯一的金币给另一个海盗。

定义$\displaystyle T(N,C,p) = \sum_{n=1}^N \left( c(n,C,p) + w(n,C,p) \right)$。已知$T(30,3,\frac{1}{\sqrt{3}}) = 190$，$T(50,3,\frac{1}{\sqrt{31}}) = 385$，$T(10^3, 101, \frac{1}{\sqrt{101}}) = 142427$。

求$\displaystyle \sum_{k=1}^6 T(10^{16},10^k+1,\tfrac{1}{\sqrt{10^k+1}})$，并将其最后$9$位数字作为你的答案。