A Fun Interview Question

[goodstudent]

There are n lions in a cage. If a piece of meat is thrown in, the closest lion can choose to either eat all of it, or walk away from it. If he chooses to eat, he will fall asleep afterward and becomes a piece of meat. Assume the only way of dying is been eaten by other lions (so they can't starve to death). Also assume that lions are intelligent so they prefer meat over no meat, but being alive over starvation.

What happens if a piece of meat is thrown in.

 

[WilliamRFrost]

I'll have to assume where you said starvation at the end, you meant being eaten, because otherwise it makes no sense.

If n > 1, the meat won't get eaten. If n = 1, the meat gets eaten, if n < 1, there are no lions to eat the meat.

 

[Shlomi]

if n=1 the meat will be eaten and the lion will fall asleep but wont get eaten by other lion.
if n=2 the meat wont get eaten (if one lion will eat the meat he will get eaten by the second lion)
if n=3 the meat will be eaten since the lion that will eat it knows that after he will eat it n will be equal to 2 and in that case he wont get eaten.
if n=4 the meat wont get eaten (like n=2)

and so on...Its easy to conclude that if n is even the meat wont get eaten and if n is odd the meat will get eaten.

 

[Bastian Gross]

It's an funny brainteaser

Thanks

 

[goodstudent]

Yup the meat is eaten if n is odd .

At first I also thought, what a dumb question and guessed that the meat will not be eaten if n > 1.

And Bastian, I agree, this is one of my favorites so far.

 

[tobias elbert]

Nice variation on the lion problem. Not the same, but similar:

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

 

[goodstudent]

Nice variation on the lion problem. Not the same, but similar:

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

Do backward induction:

If there are only 2 pirates: P2 takes 500, P1 takes nothing

If there are only 3 pirates: P3 takes 499, P2 takes nothing, P1 takes 1 (P1 will vote for the plan since he prefer 1 over nothing)

If there are only 4 pirates: P4 takes 499, P3 takes nothing, P2 takes 1, P1 takes nothing (P2 will vote for this since he prefer taking 1 in this plan rather than taking nothing in the 3 pirate case)

So P5's strategy will be, take 498, give 1 to P1, give 1 to P3, nothing to P2 and P4. He will receive the vote from P1 and P3

 

[IlyaKEightSix]

I'd argue against that. I'd say that you split it evenly across 50%, otherwise they can have to vote you executed if you get more.

So if we have two pirates, P1 gets everything.
If we have three pirates, P1 splits evenly with P2, and P3 gets nothing. If P1 tried taking 99% and giving P2 1%, P2 would know that if they'd kill P1, P2 would then become P1 and would instead get everything. So P1 gets killed, and you backwards induct to get that you split it evenly among 51% of the pirates.

Either way, with the 500 counting down by 1 or by splitting in half, you arrive at the same answer, but the splitting in half it goes in O(log(n)) where as the counting by 1 goes in O(n), so to speak, to reach steady state.

 

[WilliamRFrost]

if n=1 the meat will be eaten and the lion will fall asleep but wont get eaten by other lion.
if n=2 the meat wont get eaten (if one lion will eat the meat he will get eaten by the second lion)
if n=3 the meat will be eaten since the lion that will eat it knows that after he will eat it n will be equal to 2 and in that case he wont get eaten.
if n=4 the meat wont get eaten (like n=2)

and so on...Its easy to conclude that if n is even the meat wont get eaten and if n is odd the meat will get eaten.

I'll be nit-picky and say that only happens if the lions know the other lions are intelligent, which was not stated (so I assume to be false).

Is that something you're supposed to ask in the interview if they don't say?

For the pirate problem, Pirate 2 won't ever vote for anything that gives him less than 500, P3 won't vote for anything that gives him less than 499, P4 won't vote for anything that gives him less than 499, and P5 wants to live, so I say:

P5 proposes a split of P5 gets 0 P3 or P4 gets 499, P2 gets 0, and P1 gets 1. It's accepted, everyone lives.

I looked at it like this...

If it gets down to P2, the split is P2 gets 500, P1 gets 0. P2 votes for it, it passes.
If it gets down to P3, the split is P3 gets 499, P2 gets 0, P1 gets 1. P3 and P1 vote for it, it passes.
If it gets down to P4, the split is P4 gets 499, P3 gets 0, P2 gets 0, P1 gets 1. P4 and P1 vote for it, it passes. (P4 could also give the 1 to P2, doesn't matter)

P5 must satisfy two people other than himself, and the only way to do that is to give it all up. Since he wants to live, he does give it all up.

 

[marilapi]

With three pirates, (P3 being more senior, P1 being least). P2, if offered half, will know that P1 was offered nothing so he will vote against it. Then if P2 himself votes against it he knows he will be the most senior leader (66 2/3 % vote against means P3 is executed) and can vote for all the money to himself and get it. The question is asked what the most senior pirate proposes out of greed, which means he would take as much money as he can, not split it with anyone.

I'd argue against that. I'd say that you split it evenly across 50%, otherwise they can have to vote you executed if you get more.

So if we have two pirates, P1 gets everything.
If we have three pirates, P1 splits evenly with P2, and P3 gets nothing. If P1 tried taking 99% and giving P2 1%, P2 would know that if they'd kill P1, P2 would then become P1 and would instead get everything. So P1 gets killed, and you backwards induct to get that you split it evenly among 51% of the pirates.

Either way, with the 500 counting down by 1 or by splitting in half, you arrive at the same answer, but the splitting in half it goes in O(log(n)) where as the counting by 1 goes in O(n), so to speak, to reach steady state.

<input id="gwProxy" type="hidden"><!--Session data--><input onclick="jsCall();" id="jsProxy" type="hidden">

 

[goodstudent]

If it gets down to P2, the split is P2 gets 500, P1 gets 0. P2 votes for it, it passes.
If it gets down to P3, the split is P3 gets 499, P2 gets 0, P1 gets 1. P3 and P1 vote for it, it passes.
If it gets down to P4, the split is P4 gets 499, P3 gets 0, P2 gets 0, P1 gets 1. P4 and P1 vote for it, it passes. (P4 could also give the 1 to P2, doesn't matter)

P5 must satisfy two people other than himself, and the only way to do that is to give it all up. Since he wants to live, he does give it all up.

P4 will not give 1 to P1, he will give 1 to P2. If P4 gives 1 to P1, P1 might still vote against him, since he knows that P3 would give him 1 anyway. So he is indifferent between voting for or against P4. Therefore P4 will choose to give himself 499, and give P2 1. Since P2 will not get anything from P3, he prefer following P4's plan.

Therefore, as P5 looks at P4 case, he notices that P3 and P1 are getting nothing. So he offers each of them 1, and keeps 498 himself.

But of course, he is taking a lot of risk by assuming P3 prefers 1 over 0, since P3 might choose to sacrifice his 1 dollar to teach P5 a lesson :prayer:

By the way, this is also assuming that there is no collusion going on.

---------- Post added at 11:04 PM ---------- Previous post was at 11:00 PM ----------

I'll be nit-picky and say that only happens if the lions know the other lions are intelligent, which was not stated (so I assume to be false).

Yeah I guess I should've stated that. Lions know that everyone has complete access to info.

 

[Geoffrey]

Assumptions:
1)I am assuming whenever any pirate know that at any case they will never get any coins, they will always votes against any proposal.

2) When there is a situation that N is the maximum number of coins a pirate can get, he will vote for that proposal, when he is offered N coins for the first time.

Solution using induction::
------------------------------------------------------
If there was only 1 pirate, he takes all 100 coins
-----------------------------------------------------
If there were 2 pirates, P2 takes all 100 coins, since he can get 50% votes.
-----------------------------------------------------
If there were 3 pirates,
P3 takes 99 coins
P2 gets 0
P1 gets 1 {This is the best he can get, he will vote}
-----------------------------------------------------
If there were 4 pirates,
P4 will take 99, since P1 knows P1/P2 will support it, that is the maximum they can get {Assumption 2}
P3 will get 0
One among P1 & P2 gets 1, other gets 0
--------------------------------------------------------
If there were 5 pirates,
P5 takes 98
P4 will get 0
2 among P1, P2 & P3 will get 1 coin each, other get 0.

I think my post above is pretty much same as goodstudent, the only differences are the assumptions, and few alternate answer options, so that it can be generalized to any number of pirates.

 

[IlyaKEightSix]

It all depends on what we assume in my opinion.

There can also be a case that all pirates are absurdly greedy and the second-to-least senior one gets all the coins, if every pirate will only vote for the solution in which he gets all the coins.

Basically, say every pirate goes with my algorithm--if you get all the coins, accept. Otherwise, if anyone else even gets a single coin, reject it.

If they accept, they get a suboptimal number.

If they reject, the situation recurs with one less pirate (because one got killed).

In other words:

int Pirates(n)
if (n==2)
{
P2=max_gold;
P1=0;
}
else if (n==1)
{
P1=max_gold;
}
else if(n>=3)
{
return Pirates(n-1);/*because no pirate would accept a vote in which they don't get all the coins, so whoever proposed whatever solution, regardless of the solution, will get killed*/
}

This of course starts a game of Yomi (you know that I know that you know that I know and so on)

If everyone knows that everyone else would have them killed if they're not offered a single coin, then this recursive process will in short order kill them. So they would then have to collude with a situation that the majority all equally agree upon, which would be to split it evenly amongst the majority, otherwise they all die except for the two lowest-ranking pirates.

 

[goodstudent]

It all depends on what we assume in my opinion.

There can also be a case that all pirates are absurdly greedy and the second-to-least senior one gets all the coins, if every pirate will only vote for the solution in which he gets all the coins.

Basically, say every pirate goes with my algorithm--if you get all the coins, accept. Otherwise, if anyone else even gets a single coin, reject it.

If they accept, they get a suboptimal number.

If they reject, the situation recurs with one less pirate (because one got killed).

In other words:

int Pirates(n)
if (n==2)
{
P2=max_gold;
P1=0;
}
else if (n==1)
{
P1=max_gold;
}
else if(n>=3)
{
return Pirates(n-1);/*because no pirate would accept a vote in which they don't get all the coins, so whoever proposed whatever solution, regardless of the solution, will get killed*/
}

This of course starts a game of Yomi (you know that I know that you know that I know and so on)

If everyone knows that everyone else would have them killed if they're not offered a single coin, then this recursive process will in short order kill them. So they would then have to collude with a situation that the majority all equally agree upon, which would be to split it evenly amongst the majority, otherwise they all die except for the two lowest-ranking pirates.

I have to disagree with your algorithm because, since P1 (youngest) is not getting anything if n = 2, he would vote for other pirates' plan if they offer him even one single coin. For example, in n=3, if P3 offers P1 a coin, P1 prefers P3's 1 coin over P2's 0 coin, and there, P3 would have the majority.

Therefore, in n=4 case, P4 sees that P2 gets nothing in n=3, he offers him a coin to gain 50%.

P5 would offer P1 and P3 a coin each, because both of them know that they wouldn't receive anything if they kill P5 (P4 is only giving a coin to P2).

Generalization:
If n is odd, give a coin to each of the other odd-numbered pirates, and take the rest himself.
If n is even, give a coin to each of the other even pirates, and take the rest himself.

 

[Geoffrey]

I think the generalization should be

Case 1: For 4 < N <= 200
---------------------------------------
P(N) gets {100 - (N/2)} coins. {N/2 == only the integral part of the quotient}

P(N-1) gets nothing
Among P(1) to P(N-2), any {N/2} of them get 1 coin each. { The explanation for this is given in my previous post}
----------------------------------------
Case 2: For 200 < N
All P(N), for (N > 200 ) will be killed
And Case (1) will come into effect.

------------------------------------------------------------------------------------

Quotes from my previous post:

Assumptions:
2) When there is a situation that N is the maximum number of coins a pirate can get, he will vote for that proposal, when he is offered N coins for the first time.

------------------------------------------------------------------------------------
"Pirate 2 won't ever vote for anything that gives him less than 500, P3 won't vote for anything that gives him less than 499, P4 won't vote for anything that gives him less than 499"

<o:p>I didn't consider the above assumption in my solution because of the following:</o:p>
<o:p>--------------------------------------------------------------
</o:p>
If everyone from top start thinking this way, the only guy benefiting from this is P4, since he is the first guy (from top) who is guaranteed of his proposal getting approved. Every pirate knows this fact.<o:p>
P4 knows that "every pirate knows this fact". Hence he knows there is no point in waiting for 499, since the chain may end before and he may get nothing. So he ALSO (as other pirates) would not wait for getting 499, instead vote for 1 coin.

</o:p>[FONT=&quot]
[/FONT]

---------- Post added at 03:08 PM ---------- Previous post was at 03:00 PM ----------

I have to disagree with your algorithm because, since P1 (youngest) is not getting anything if n = 2, he would vote for other pirates' plan if they offer him even one single coin. For example, in n=3, if P3 offers P1 a coin, P1 prefers P3's 1 coin over P2's 0 coin, and there, P3 would have the majority.

Therefore, in n=4 case, P4 sees that P2 gets nothing in n=3, he offers him a coin to gain 50%.

P5 would offer P1 and P3 a coin each, because both of them know that they wouldn't receive anything if they kill P5 (P4 is only giving a coin to P2).

Generalization:
If n is odd, give a coin to each of the other odd-numbered pirates, and take the rest himself.
If n is even, give a coin to each of the other even pirates, and take the rest himself.

I think when N = 4, P4 takes 99 & gives P1 1 coin, P1 will still vote for the proposal, since even P3 is going to give him only 1 coin, it doesn't make a difference..right?

My point is, if I was in this position I would vote for first time I get 1 coin, even though most probably(99.99% or higher) I will get one coin next time too..But I will not take a chance.

 

[IlyaKEightSix]

I have to disagree with your algorithm because, since P1 (youngest) is not getting anything if n = 2, he would vote for other pirates' plan if they offer him even one single coin. For example, in n=3, if P3 offers P1 a coin, P1 prefers P3's 1 coin over P2's 0 coin, and there, P3 would have the majority.

Therefore, in n=4 case, P4 sees that P2 gets nothing in n=3, he offers him a coin to gain 50%.

P5 would offer P1 and P3 a coin each, because both of them know that they wouldn't receive anything if they kill P5 (P4 is only giving a coin to P2).

Generalization:
If n is odd, give a coin to each of the other odd-numbered pirates, and take the rest himself.
If n is even, give a coin to each of the other even pirates, and take the rest himself.

Hmmm...right you are.

 

[marilapi]

yes but if the most senior pirate is smart, he wouldn't take the chance of offering P1 a coin. P1 can swing either way. Actually, P1 might very well vote against P4's proposal because P4 would get executed and there would be more rum for the rest of the pirates. They are greedy, aren't they?

I think when N = 4, P4 takes 99 & gives P1 1 coin, P1 will still vote for the proposal, since even P3 is going to give him only 1 coin, it doesn't make a difference..right?

My point is, if I was in this position I would vote for first time I get 1 coin, even though most probably(99.99% or higher) I will get one coin next time too..But I will not take a chance.

 

[Geoffrey]

yes but if the most senior pirate is smart, he wouldn't take the chance of offering P1 a coin. P1 can swing either way. Actually, P1 might very well vote against P4's proposal because P4 would get executed and there would be more rum for the rest of the pirates. They are greedy, aren't they?

I am inclined to disagree with second half of this assumption, which in turn makes the entire assumptions invalid. Especially for large values of N, the risk junior pirates will be taking by not voting may not be worth the expected "more rum" for him (except for P(N-1)).

I think here the answer depends on each individual's perception & the assumptions made. That is the reason I stated my assumption clearly in my first post itself. Based on my assumption my answer is right, based on your assumption your answer is right too...right?

Assumptions:
2) When there is a situation that N is the maximum number of coins a pirate can get, he will vote for that proposal, when he is offered N coins for the first time.

 

[WilliamRFrost]

A question about the general case where N (number of pirates) > 1000... Do pirates of N-index < N-1000 (for instance, the first 200 if N if 1200) vote in favor when they get 0, because they don't want to risk the split coming to them, and they're unable to satisfy enough people, so they die?

 

[goodstudent]

A question about the general case where N (number of pirates) > 1000... Do pirates of N-index < N-1000 (for instance, the first 200 if N if 1200) vote in favor when they get 0, because they don't want to risk the split coming to them, and they're unable to satisfy enough people, so they die?

Yeah, i think so too. If n > 1000, the oldest n-1000 pirates will die, unless they are willing to contribute more coins from their personal savings...