Interesting Question

September 6, 2007 at 7:04 pm 2 comments

                 Today i was reading an article about

 “What recruiters and project managers expect from the candidate they are recruiting “.

                 They say they want people who think different , not those who say  area = length * breadth given length and breadth but people who are creative and will come out with different solutions. So they have been trying to put up different questions which can bring out their IQ .
                 I am always very much interested in solving such type questions…  There was a sample question and it is the most interesting question i had ever seen as for now. check it out .

Question:
                Five pirates have 100 gold coins. they have to divide up the loot. in order of seniority (suppose pirate 5 is most senior, pirate 1 is least senior), the most senior pirate proposes a distribution of the loot. They vote and if at least 50% accept the proposal, the loot is divided as proposed. otherwise the most senior pirate is executed, and they start over again with the next senior pirate. what solution does the most senior pirate propose? assume they are very intelligent and extremely greedy (and that they would prefer not to die).(to be clear on what 50% means, 3 pirates must vote for the proposal when there are 5 for it to pass. 2 if there are 4. 2 if there are 3. etc… )

solution:
               
    Most of the time i get people who give answers like “the most
senior pirate takes half and divides the rest up among the least senior
pirates.” um, you missed the whole point to begin with. sorry.

                    Any answer without a specific logic behind it is invalid. if i ask you why
pirate 5 gave x coins to pirate 1, please don’t say “because he’s nice”.
now for the real solution. pirate 5 being the most senior knows that he needs
to get 2 other people to vote for his solution in order for him not to be
executed. so who can he get to vote for him, and why would they choose to vote
for him? if you start thinking that pirate 4 will never vote for him, because he
would rather have 5 die and then be in charge and take it all for himself, you
are on the right track. but it gets more complicated.

lets consider if there were only 1 pirate. obviously he would take it all for
himself and no one would complain.

if there were 2 pirates, pirate 2 being the most senior, he would just vote
for himself and that would be 50% of the vote, so he’s obviously going to keep
all the money for himself.

            If there were 3 pirates, pirate 3 has to convince at least one other person
to join in his plan. so who can he convince and how? here is the leap that needs
to be made to solve this problem. pirate 3 realizes that if his plan is not
adopted he will be executed and they will be left with 2 pirates. he already
knows what happens when there are 2 pirates as we just figured out. pirate 2
takes all the money himself and gives nothing to pirate 1. so pirate 3 proposes
that he will take 99 gold coins and give 1 coin to pirate 1. pirate 1 says,
well, 1 is better than none, and since i know if i don’t vote for pirate 3, i
get nothing, i should vote for this plan.

                now we know what happens when there are 3 pirates. so what happens with 4?
well pirate 4 has to convince 1 other person to join in his plan. he knows if he
walks the plank then pirate 3 will get 99 coins and pirate 1 will get 1 coin.
pirate 4 could propose giving pirate 1 two coins, and surely pirate 1 would vote
for him, since 2 is better than 1. but as greedy as he is, pirate 4 would rather
not part with 2 whole coins. he realizes that if he gets executed, then pirate
3’s scenario happens and pirate 2 gets the shaft in that scenario (he gets zero
coins). so pirate 4 proposes that he will give 1 coin to pirate 2, and pirate 2
seeing that 1 is better than 0 will obviously vote for this plan.

                A common objection is that pirate 2 is not guaranteed to vote for this plan
since he might hope for the case when there are only 2 pirates and then he gets
all the booty. but that is why i said that the pirates are extremely
intelligent. pirate 2 realizes that pirate 3 is smart enough to make the optimal
proposal, so he realizes that there will never be 2 pirates left, because 3
doesn’t want to die and we just showed that 3 has a winning proposal.

so lets sum up at this point

Pirate 1  2  3  4  5
5. ? ? ? ? ?
4. 0 1 0 99 -
3. 1 0 99 - -
2. 0 100 - - -
1.100

                once you see the pattern it becomes very clear. you have to realize that when
a pirate’s plan does not succeed then that means you are in the same situation
with one less pirate.
1. pirate 1 needs 0 other people to vote for him. so he
votes for himself and takes all the money. 2. pirate 2 needs 0 other people to
vote for him. so he votes for himself and takes all the money. pirate 1 gets 0.
3. pirate 3 needs 1 other person to vote for him. he gives 1 coin to pirate 1
for his vote – if we are reduced to 2 pirates, pirate 1 gets 0 so pirate 1 knows
1 is better than none. pirate 3 takes 99. pirate 2 gets 0. 4. pirate 4 needs 1
other person to vote for him. he gives 1 coin to pirate 2 – if we reduce to 3
pirates, pirate 2 gets 0 so pirate 2 knows 1 is better than none. pirate 4 takes
99. pirate 3 gets 0. pirate 1 gets 0. 5. pirate 5 needs 2 other people to vote
for him. its clear now that the 2 people he needs to convince are the 2 who get
shafted in the 4 pirate scenario – pirate 3 and pirate 1. so he can give them
each 1 coin (which is better than 0 – what they would get otherwise) and keep 98
for himself.

Pirate 1  2  3  4  5
5. 1 0 1 0 98

                what happens if there are 15 pirates? pirate 15 needs 7 other people to vote
for him, so he recruits pirates 13,11,9,7,5,3, and 1 with 1 coin each and keeps
93 coins himself. those pirates will all vote for him because they know that
they get 0 coins if he dies and pirate 14 is in charge.

hope you enjoyed this one. its my favorite interview question of all.

Powered by ScribeFire.

Entry filed under: Friends, Fun, technical. Tags: .

Life as it is “Happy Programmer’s Day”

2 Comments Add your own

  • 1. nila  |  September 6, 2007 at 10:12 pm

    HI..
    good to see that u are posting things regularly..
    keep goin..

    nila..

    Reply
  • 2. subbu  |  September 10, 2007 at 4:45 pm

    Really Good One.Explaination is also good.I was lazy to solve this by myself so peeped into the answer immediately.🙂

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed


September 2007
S M T W T F S
« Aug   Oct »
 1
2345678
9101112131415
16171819202122
23242526272829
30  

Blog Stats

  • 225,929 hits

Java software

Flickr Photos

Red and Gold

Sol Duc Falls

Wasting Light

More Photos

%d bloggers like this: