TOAD 20 - Democracy

这个题目似乎比较简单。

Problem

某国有 2kw 选民，国王的支持者只占 1% 。现在有一种“民主”的选举方式：我们将全部的选民分为 \(n_1\) 组（每组选民数目相同），每组内的选民再分为 \(n_2\) 组（仍然要求选民数目相同），再这样分下去，直至只剩一个人。每一组的投票结果为这一组分成的若干个小组的投票结果中，出现次数最多的候选人。如果有多个相同的，我们假定国王会输。

是否存在一种分组方式，使得国王通过一定的分配方案使得他获得整个选举的胜利？

Solution

浪费可耻，于是国王的最优策略肯定是：要么不派人，一旦派人则这个人要一直是多数。

由于要求国王赢的话出现次数必须严格超过一半。假设我们把一堆人分成 \(2k - 1\) 组，则我们只需争取 \(k\) 组的胜利即可。在这个过程中，我们需要的人数可以减小到总人数的 \(\frac{k}{2k - 1}\) 。

由于 2kw 分解后 5 的指数为 7 ，所以我们可以分 7 次，每次分成 5 组。在所有的 \(5^7\) 组中，我们只需赢得 \(3^7\) 组胜利即可，这组数只占全部的 2.79936% ，离 1% 还差了一点。

注意到现在每组还有 256 个人，我们可以通过一定的分组方式再减小人数。如果只分成 1 组，需要 1.410615% 的人口；考虑分成 16 组，每组的 16 个人中派 9 个人，则只需要 0.885735% 的人口，小于 1% 了。