Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Oct 4, 2009

The King's salary

Puzzle:

After the revolution, each of the 66 citizens of a certain country, including the king, has a salary of $1. The king can no longer vote, but he does retain 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. Each suggestion is voted on, and carried if there are more votes for than against. Each voter can be counted on to vote "yes" if his salary is to be increased, "no" if decreased, and otherwise not to bother voting.

The king is both, selfish and clever. What is the maximum salary he can obtain for himself, and how long does it take him to get it? (from P.Winkler, loosely inspired by real historical events in Sweden)

Update (11/12/09) Solution: Highlight the part between the * symbols for the answer. * 63$ (Thanx to Deeepanshu (Civil, H2) for explanation in comments!! [What a fool I had been :(], Solution provided in Winkler)

To start with there are 66 citizens (including the king) with a salary of $1.
King first proposes that 33 citizens have their salaries doubled to $2, at the expense of the remaining 33 (himself included). 33 citizens whose salaries are being doubled are voting "for" and king is also voting "for" while giving away his $1. So, we have 33 "for" votes and 32 "against" votes. Proposition passed. We now have 33 citizens earning $2 and 33 citizens (including the king) without the salary.
Next, king increases the salaries of 17 of the 33 salaried workers to $3. 17 votes "for", "16" against, others do not care.
In the same manner king slowly reduced the number of salary-receiving citizens to 9, 5, 3, 2. At this point there are two citizens earning $33 each.
As a last trick, 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.

As pointed out by Shantanu in comments, the king can take 65$ (!!!) if he is allowed to vote. *

5 comments:

  1. in the question in second line its mentioned king can no longer vote...so wen only 2 citizens r left wid 33$..he needs three people to counter those two's votes..so he is giving jobless people 1$ each(they were earning nothing so wen they r earning 1$ they ll say yes)..so by majority proposition passes and he gets d leftover money as sum should be 66$.....and in the solution its mentioned king's vote as he cannot vote...but still answer remains unchanged

    ReplyDelete
  2. 63$ is right..chk that king cannot vote as mentioned in d question and solution is written somewat wrong..but answer is correct..he cannot reduce no of citizens in d last to one...think

    ReplyDelete
  3. Update:
    Thanx Deepanshu... appropriate changes made in the post..

    ReplyDelete
  4. With the king casting a vote, he can infact get $65.
    But thats not what the puzzle is :P
    $63 otherwise.

    ReplyDelete
  5. :)
    @shantanu..
    infact... if the king is not allowed to vote,

    It can be proved that the king always takes (n-3)$ after \ceiling{log_2 (n-2)} steps...
    Try it out :)

    ReplyDelete