r/puzzles • u/okayboomer2023 • 1h ago
[SOLVED] The King and his Salary
A kingdom contains a king and 65 citizens. Everyone (king included!) initially receives a salary of one gold coin.
Democracy has arrived to this little kingdom, and while the king cannot vote, he has the power to suggest changes: in particular, redistribution of salaries.
The king may propose redistributing the salaries, subject to two rules: the total must remain 66 coins at all times, and every salary must be a nonnegative whole number (zero is fine!).
While the king cannot vote, each citizen votes according to what the proposal does to their current salary:
- A raise means a yes vote.
- A cut means a no vote.
- No change means they abstain.
A proposal passes whenever there are more yes votes than no votes.
The king’s proposals: The king may make a sequence of proposals for such salary redistributions, with a separate vote on each proposal. Whenever a proposal passes, the new salaries take effect immediately. He may then propose another redistribution of those salaries. There is no limit to the number of proposals he can make.
Here's the question/puzzle:
(1) What is the maximum salary the king can obtain for himself, and
(2) how many (optimal number) referenda does he need to get it?
Note: part (1) has a unique numerical answer. For part (2), if you interpret it as "what are the fewest votes needed to achieve it?", this also has a unique numerical answer. If, on the other hand, you interpret (2) as asking "how can he achieve it?", this admits multiple possible sequences of moves (where, say, the intermediate salaries are distributed in different ways). So (2) is about the fewest votes needed to achieve the answer in (1), not about the unique valid sequence (which there strictly isn’t).
Important assumptions/rules (on how the citizens vote) wortth stressing:
- Citizens judge each proposal against their current salaries, not their original one-coin salaries. They also do not consider what the king may propose in later rounds. With each vote, they just respond to the effect of the current proposal on their current salary. (So don’t assume that citizens are capable of thinking strategically about future votes. That's a different problem!)
- Anyone whose salary would stay the same abstains.
- A salary of zero is allowed.
(Source: I first saw this puzzle in Peter Winkler’s Mathematical Puzzles book.)
