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. *

Comments

  1. Unknown1:49 PM, October 04, 2009

    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. deepanshu1:51 PM, October 04, 2009

    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. Pratik Poddar2:01 PM, October 04, 2009

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

    ReplyDelete
  4. Shantanu9:24 PM, October 04, 2009

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

    ReplyDelete
  5. Pratik Poddar10:54 AM, October 05, 2009

    :)
    @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

Post a Comment

Popular posts from this blog

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more