国王的最高工资
King's Salary
题目详情
革命后某城 66 名市民（含国王）每人薪水都是 1，总薪水为 66。
国王不能投票，但可以提出新的薪水分配方案（每人薪水必须是整数且总和仍为 66）。市民很贪：
- 若新方案让他薪水增加，则投“赞成”；
- 若新方案让他薪水减少，则投“反对”；
- 若不变，则弃权。
若赞成票数严格多于反对票数，则方案通过并执行。国王可以连续提出多轮方案。
问：在最优策略下，国王最终能让自己薪水达到多少的最大值？
After the revolution, each of the 66 citizens of a certain city, including the king, has a salary of 1. King cannot vote, but has the power to suggest changes - namely, redistribution of salaries. Each person's salary must be a whole number of dollars, and the salaries must sum to 66. He suggests a new salary plan for every person including himself in front of the city. Citizens are greedy, and vote yes if their salary is raised, no if decreased, and don't vote otherwise. The suggested plan will be implemented if the number of "yes" votes are more than "no" votes. The king is both, selfish and clever. He proposes a series of such plans. What is the maximum salary he can obtain for himself?
Hint
notice: (1) that the king must temporarily give up his own salary to get things started, and (2) that the game is to reduce the number of salaried citizens at each stage.
解析
最大值为 63。
核心策略：国王通过多轮提案不断“把领薪的人数减少到略多于一半”，同时用少量贿赂换取多数票，最终把几乎全部薪水集中到自己身上。
最优上界也在于：每轮要通过，必须让赞成者人数严格多于反对者；因此无法把“领薪者”一步降到 1 人，只能逐轮缩减，最终最优结果是 63。
Original Explanation
63
Solution
Continuing from the hint, The king begins by proposing that 33 citizens have their salaries doubled to $2, at the expense of the remaining 33 (himself included). Next, he increases the salaries of 17 of the 33 salaried voters (to $3 or $4) while reducing the remaining 16 to $0. In successive turns, the number of salaried voters falls to 9, 5, 3, and 2. Finally, the king bribes three paupers with $1 each to help him turn over the two big salaries to himself, thus finishing with a royal salary of $63. It is not difficult to see that the king can do no better at any stage than to reduce the number of salaried voters to just over half the previous number; in particular, he can never achieve a unique salaried voter. Thus, he can do no better than $63 for himself, and the six rounds above are optimal
Hence the answer is $63
Note: It is possible to reach $65 if the King could vote (that would be a variant of this puzzle).