23
$\begingroup$

A little kingdom contains 66 people, a king and 65 citizens. Each of them, including the king, has a salary of one gold piece. When democracy comes, the king is denied a vote, but he has the power to suggest a series of changes, in particular regarding the redistribution of salaries. The salaries must total 66, and each salary must be a whole number of gold pieces. The citizens will vote on each suggestion, which will pass if more citizens vote for it than against it. Each voter will reliably support a measure if it will increase their salary, oppose it if it will decrease their salary, and otherwise abstain from voting.

The king is greedy. What’s the highest salary he can arrange for himself?

This puzzle is from futilitycloset.com

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Entertaining problem. $\endgroup$
    – qwr
    Commented Jun 30 at 19:04

1 Answer 1

Reset to default
24
$\begingroup$

The king can pay himself a salary of

63 gold.

In what follows, I will refer to the 65 citizens by numbers 1-65. The king begins by

giving his salary and the salaries of 1-32 to 33-65. The king then divides the salaries of 33-48 among 49-65, then divides 49-56 among 57-65, then 57-60 among 61-65, then 61-62 among 63-65, and finally divides 63's salary between 64 and 65.
For the final touch, the king confiscates the salaries of 64 and 65 and gives one coin each to 1, 2, and 3, securing a salary of 63 gold coins in seven budget proposals.

This is optimal because

at least two citizens must vote for any proposal which decreases another citizen's salary, which means that at least two citizen salaries must increase, and in turn that at least two citizens are being paid at all times. If those two are both being paid one gold, then the last change must have been either:
- give some of those citizens the king's gold (prior to which at most one citizen was paid), or
- give those citizens another citizen's gold (prior to which only the losing citizen was paid).
Both situations are impossible, so at least three gold must be paid out.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I think you can go down to 8 rounds. $\endgroup$
    – Florian F
    Commented Jun 30 at 19:34
  • 1
    $\begingroup$ @Will.Octagon.Gibson I have streamlined my algorithm and given a definite number of rounds. $\endgroup$
    – AxiomaticSystem
    Commented Jul 1 at 2:01
  • 7
    $\begingroup$ @Jeroentetje3: You forgot the king's salary, in the first round the king abandons their own salary (1gp), so they have 33 gps to re-distribute. $\endgroup$
    – Matthieu M.
    Commented Jul 1 at 14:39
  • 1
    $\begingroup$ This is very similar to how some ruthless dictators hold power. $\endgroup$
    – Victor Stafusa
    Commented Jul 1 at 20:54
  • 6
    $\begingroup$ @MatthieuM. In other words, he's greedy but not algorithmically greedy $\endgroup$
    – No Name
    Commented Jul 1 at 23:36

Not the answer you're looking for? Browse other questions tagged or ask your own question.