2 Really Hard Questions

[muchspl2]

1. There are 5 pirates, ordered "5" through "1".

The pirates are maximally greedy.

There are 100 coins.

The highest-numbered pirate gets to determine a coin distribution: assigning a specific number of coins to each specific pirate.

All pirates then vote on accepting the distribution.

If at least half of the pirates agree to accept that distribution, the pirates go on their way.

If the vote doesn't carry at least 50% of the votes, the highest-numbered pirate is killed, and the process is repeated with the remaining pirates.

You are the 5th pirate: how do you distribute the coins?


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


2. You have a 5 lane race track.

You have 25 runners.

A race only determines relative ordering (who came in 1st, 2nd, 3rd, 4th, and 5th), not individual times.

What is the minimal number of races you must run to determine the 3 fastest runners?

[muchspl2]

these are M$ interview questions

[4th gen]

Originally posted by muchspl2@24 April 2004 - 18:54
1. There are 5 pirates, ordered "5" through "1".

The pirates are maximally greedy.

There are 100 coins.

The highest-numbered pirate gets to determine a coin distribution: assigning a specific number of coins to each specific pirate.

All pirates then vote on accepting the distribution.

If at least half of the pirates agree to accept that distribution, the pirates go on their way.

If the vote doesn't carry at least 50% of the votes, the highest-numbered pirate is killed, and the process is repeated with the remaining pirates.

You are the 5th pirate: how do you distribute the coins?
Half to the first pirate, half to the second and none to yourself. Presumably you and the other two will vote happily, giving a 3-2 majority?

[sexfem]

Muchspl2.

Runners: six races would determine first three places. But not necessary the fastest runner.

With the runners you cant determine who is the fastest runner without timing them. The winnere of race three for example could come last in the final race. Yet in race three he could have broke the world record.

[muchspl2]

nope and nope :D

[4th gen]

Originally posted by muchspl2@24 April 2004 - 19:12
nope and nope :D
The ordering is 1->5 not 5->1, so you give it all to yourself?

[sexfem]

Originally posted by muchspl2@24 April 2004 - 20:12
nope and nope :D
If it is a catch question then it is one race. Probably over 5000m. :rolleyes:

[4th gen]

Only one race, there are 3 fastest people in that race?

[Peerzy]

6 Races,

5 races with 5 people each, and the person who comes first in each race will race in one last race, the top three people win.

[J'Pol]

First

33
33
33
1
0

Should guarantee 3 votes and be acceptable.



Second

If times are not measured then 6 races.

5 races to decide the 5 fastest.

6th race decides the top 3 places, of the 5 winners.

[muchspl2]

no correct answers in this thread :(

[Chevy]

Pirates:

Vote 1= yourself
Vote 2= Give just one coin to pirate #1 will guarentee his vote,
Vote 3= Give just one coin to pirate #3 to get his vote (I think)


Races:

Play it as a knockout competition knocking out the last 2 each time
5 races of 5 runners leaving 15
3 races of 5 runners leaving 9
1 race of 5 runners and a race of 4 runners leaving 6
1 race of 5 runners (1 entrant gets a bye) leaving 3 and the bye
the final 4 determine the top 3
=12 (not to sure about this answer)

edit: pirates - pirate 1 is always the top pirate's guarenteed vote with one coin as if it gets down to 2 he'll get nothing. Pirate 3 can be bought with only one coin as if it gets down to 4 (he doesn't vote now) pirate 4 can just buy pirate 1 in the same way that you are.

[Snee]

But if the pirates are "maximally greedy" wont they keep voting against the highest numbered pirate until there are only two left at which point the highest numbered pirate left will take all the money, and vote for his own suggestion.

[sexfem]

The 5th pirate votes

5 = 32
4 = 32
3 = 32
2 = 2
1 = 2

Guaranteed carried vote. B)

[DanB]

Originally posted by sexfem@24 April 2004 - 21:50
The 5th pirate votes

5 = 32
4 = 32
3 = 32
2 = 2
1 = 2

Guaranteed carried vote. B)
Wouldnt they just fight and the winner ie the person still alive, take all? :blink:

[muchspl2]

Originally posted by muchspl2@24 April 2004 - 15:34
no correct answers in this thread :(
:smilie4:

[Chevy]

Was sure I had the pirate one right (see the edit) but for the races one, instead of a cup style knockout tournament (takes 12 races), it could be a race of 5 repeated with the top 3 staying in and the bottom 2 being knocked out.

Race 1 would leave 23 left etc.., with 11 races needed to end up with a final 3.

[muchspl2]

nope, here are some hints:

1. regarding question 1 for those of you with no reading comprehension skills you are the 5th numbered pirate i.e. you decide the first allocation and you try to make the allocation such that the other 4 pirates wouldn't kill you for it, and you end up with the maximum number of gold coins.

please also remember all the pirates are logical, they don't want to die either and are intelligent.

2. regarding question 2 none of the answers given before this post is correct. btw if you mention an answer please show how you get to that number.

[hobbes]

ok, read the clarification. Have to think some more.

As the first distributor, I would give 50 to #4 and 50 to #3 and escape with my life.

If 4 does not vote for it, he will get 0 when he is chosen to distribute, the maximum 3 can get is 50 anyway, so he will vote for it.

1, 50, 49, 0, 0

y, y, n, n, n,-you die

then
50, 50, 0, 0

y, y, n, n

So the max that 3 and 4 can get is 50. You will either get none and live or be killed.

[Chevy]

If there are 2 pirates left #2 can just keep the money as he can give 50% of the vote

If there are 3 pirates left, #3 can just give 1 coin to pirate one to get the vote as if he's killed pirate one will get nothing (scenario above)

If their are 4 pirate left, #4 can give one coin to pirate number 2 as pirate number 2 will be aware of the scenaio above.

Solution, keep 98 coins, one coin to pirate 1 and one to pirate 3. (as my edit on the other page)

[hobbes]

solution

0, 50, 50, 0, 0

as described in edit above. 4&3 are smart and realize that 50 is the most they can get.



Alternate answer, put all the coins in a pillow case and beat the other 4 pirates with death with them. Hey, I saw Sean Penn do it in Bad Boys!

[yonki]

Number 2: 16 is the minimum


First you make 5 races. You pick the first 3 of each race(because the 3 fastest may be in the same race). Now you pick one winner and race against the 4 guys who were 3rd.And you do this with every winner.if a 3rd beats a 1st you switch them.you do the same with the 2nds and one final race with all the 1sts.

EDIT:i dont really get number 1.whats the point there?get all the money?if not, just give 20 coins to each pirate and thats it.

[muchspl2]

nope

[J'Pol]

Races

Round 1 - 5 races - take 3 fastest from each leaves 15 runners.

Round 2 - 3 Races - take 3 fastest runners leaves 9 runners.

Round 3 - 2 Races - take 3 fastest runners leaves 6 runners.

Round 4 - 1 Race with 5 of the 6

Round 5 - 1 Race with 3 from the previous round plus the other man.


Gives 12 Races.

[Chevy]

It has to be worked backwards (rewording of previous post)

If there are 2 left, P2 will definately get all the money leaving p1 with nothing.

Because of this, if there are 3 left, P1 will vote even if he has just one coin (leaving p2 with nothing).

Because of this, if there are 4 left, p2 will vote even if he has just coin (leaving p1 and p3 with nothing).

Therefore, with 5 left, all p5 needs to do is give P1 and p3 a coin each as if you die, they will definately get nothing anyway (it will be settled in the scenario above)




@J'Pol, that is the same as my first post but in the next one I got it down to 11 races by a "top 3 stay in and the last 2 go out and repeat" method.

[muchspl2]

you are getting close on solving the first question, work back wards
no one is close on the second :D

[hobbes]

Originally posted by Chevy@24 April 2004 - 22:23
It has to be worked backwards (rewording of previous post)

If there are 2 left, P2 will definately get all the money leaving p1 with nothing.

Because of this, if there are 3 left, P1 will vote even if he has just one coin (leaving p2 with nothing).

Because of this, if there are 4 left, p2 will vote even if he has just coin (leaving p1 and p3 with nothing).

Therefore, with 5 left, all p5 needs to do is give P1 and p3 a coin each as if you die, they will definately get nothing anyway (it will be settled in the scenario above)




@J'Pol, that is the same as my first post but in the next one I got it down to 11 races by a "top 3 stay in and the last 2 go out and repeat" method.
Chevy, if 3 votes "no", 5 will die.

In the next round, 3 and 4 will split the pot 50/50.

So, I think that it is 98, 0, 0, 1, 1.

Because if 5 dies 4&3 will take all the coins.

Getting 1 is all 1&2 can hope for.

[Chevy]

Originally posted by hobbes@24 April 2004 - 21:33

Getting 1 is all 1&2 can hope for.
Read the scenarios for the amount of pirate left I mentioned. You always get the vote of the person who would be guarenteed nothing before. THis is the case for however many are left and the others can buy just that one pirate with a coin. As the 5th, you have to buy 2 but they are the 2 who would get nothing anyway if you die.

[yonki]

I got the final answer for number 2,and dont tell me its wrong,because it isnt :P

5+3+1=9

5 races again.pick 3 from each.now make 3 races:1sts vs 1sts;2nds vs 2nds and 3rds vs 3rds.from here you get the top 5,and besides you know who is the fastest guy.he doesnt even have to run the last race.

[Chevy]

Originally posted by yonki@24 April 2004 - 21:37
I got the final answer for number 2,and dont tell me its wrong,because it isnt :P

5+3+1=9

5 races again.pick 3 from each.now make 3 races:1sts vs 1sts;2nds vs 2nds and 3rds vs 3rds.from here you get the top 5,and besides you know who is the fastest guy.he doesnt even have to run the last race.
what if the 3 fastest happened to be in the same race at the beginning?

[yonki]

Originally posted by Chevy+24 April 2004 - 22:39--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>QUOTE (Chevy @ 24 April 2004 - 22:39)</td></tr><tr><td id='QUOTE'> <!--QuoteBegin-yonki@24 April 2004 - 21:37
I got the final answer for number 2,and dont tell me its wrong,because it isnt&nbsp; :P

5+3+1=9

5 races again.pick 3 from each.now make 3 races:1sts vs 1sts;2nds vs 2nds and 3rds vs 3rds.from here you get the top 5,and besides you know who is the fastest guy.he doesnt even have to run the last race.
what if the 3 fastest happened to be in the same race at the beginning? [/b][/quote]
thats the worst case and i already thought of that.thats why you need the one last race

[Z-95]

For the second question: one race with all 25 people running. The first 3 to finish will be the 3 fastest. :D

[muchspl2]

Originally posted by hobbes+24 April 2004 - 16:33--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>QUOTE (hobbes @ 24 April 2004 - 16:33)</td></tr><tr><td id='QUOTE'> <!--QuoteBegin-Chevy@24 April 2004 - 22:23
It has to be worked backwards (rewording of previous post)

If there are 2 left, P2 will definately get all the money leaving p1 with nothing.

Because of this, if there are 3 left, P1 will vote even if he has just one coin (leaving p2 with nothing).

Because of this, if there are 4 left, p2 will vote even if he has just coin (leaving p1 and p3 with nothing).

Therefore, with 5 left, all p5 needs to do is give P1 and p3 a coin each as if you die, they will definately get nothing anyway (it will be settled in the scenario above)




@J&#39;Pol, that is the same as my first post but in the next one I got it down to 11 races by a "top 3 stay in and the last 2 go out and repeat" method.
Chevy, if 3 votes "no", 5 will die.

In the next round, 3 and 4 will split the pot 50/50.

So, I think that it is 98, 0, 0, 1, 1.

Because if 5 dies 4&3 will take all the coins.

Getting 1 is all 1&2 can hope for. [/b][/quote]
this is correct

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&#39;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.

1 2 3 4 5
1 0 1 0 98

[hobbes]

2nd question : 15 races

I used 4 people per race, breaking it down into 3 groups of 8, the 25th runner ran only in the final race.

[Chevy]

Originally posted by Chevy+24 April 2004 - 22:23--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>QUOTE (Chevy &#064; 24 April 2004 - 22:23)</td></tr><tr><td id='QUOTE'>&nbsp;

Therefore, with 5 left, all p5 needs to do is give P1 and p3 a coin each as if you die, they will definately get nothing anyway (it will be settled in the scenario above)
[/b]

<!--QuoteBegin-muchspl2@24 April 2004 - 21:46

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.
[/quote]
didn&#39;t you say my answer was wrong before? :unsure:

[Chevy]

Originally posted by hobbes@24 April 2004 - 21:52
2nd question : 15 races

I used 4 people per race, breaking it down into 3 groups of 8, the 25th runner ran only in the final race.
If you give a runner a bye in the semi it can be done in 12, if it&#39;s a "top 3 stay in the other 2 get knocked out and repeat" it can be done in 11.


(is no-one reading other answers?)

[muchspl2]

it less than 11 races

[yonki]

why is 9 wrong?

[hobbes]

I think is 9 as well.

[muchspl2]

because its not right :D
I&#39;d rather wait before giving away the anwser

[hobbes]

deleted because it was a flawed number.

[Chevy]

How did you get 9 (apart from Yonki&#39;s solution)?


I got as far as 10:

Round 1: 25 runners, 5 races=the top 2 in each going through to round 3. The 5 third place contestants go into round 2. <5 races>

Round 2: 5 runners (3rd placers in Round 1) , one race = the fastest one going into round 4 <1 race>

Round 3: 10 runners (top 2 from each race in round 1), 2 races, the top 3 in each go to round 4 <2 races>

Round 4: 7 runners (6 from round 3, 1 from round 2), 2 given a bye, one race of the remaining 5 the top 3 going into round 5. <1 race>

Round 5: 5 runners (top 3 from round 4 and the 2 from round 4 with the bye) Top 3 are the overall top 3. <1 race>


(sorry if it&#39;s not that clear)

[yonki]

ok sorry,7 is the right number

same as before 5 races and pick the first 3 of each round.now a race between the 5 winners.now you have the fastest.and 6 races.you still have to race the 2nd and 3rd of the first race and the 2nd and 3rd of th all winners race.am i wrong again?

[Chevy]

Originally posted by yonki@24 April 2004 - 22:41
ok sorry,8 is the right number
:lol:

Unless you explain how you got it I think you are playing "guess the number"

[Chevy]

Originally posted by yonki@24 April 2004 - 22:41
ok sorry,7 is the right number

same as before 5 races and pick the first 3 of each round.now a race between the 5 winners.now you have the fastest.and 6 races.you still have to race the 2nd and 3rd of the first race and the 2nd and 3rd of th all winners race.am i wrong again?
The 5 fastest arn&#39;t neccessarily the winners from each of the first 5 races - they could all be in the first race.

Even if they were, it would also result in the 6th fastest person being the winner in you "2nd placers race"

[DanB]

I think we need a maths world :lol:

[yonki]

Originally posted by Chevy+24 April 2004 - 23:44--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>QUOTE (Chevy @ 24 April 2004 - 23:44)</td></tr><tr><td id='QUOTE'> <!--QuoteBegin-yonki@24 April 2004 - 22:41
ok sorry,8 is the right number
:lol:

Unless you explain how you got it I think you are playing "guess the number" [/b][/quote]
mekivoke,i meant 7

[muchspl2]

7 is correct

First Groups:
1.2.3.4.5 | 6.7.8.9.10 | 11.12.13.14.15 | 16.17.18.19.20 | 21.22.23.24.25

4,5,9,10,14,15,19,20,24,25 get eliminated since you know for a fact that there are atleast 3 racers faster than them, and we are looking for the top 3.

Remaining groups: 1.2.3 | 6.7.8 | 11.12.13 | 16.17.18 | 21.22.23

Racing the fastest of these groups (1,6,11,16,21) allows us to eliminate all racers in the groups with the slowest of the fastest (17,18,22,23) We can also eliminate 12 and 13 since we know theres atleast 3 faster racers 1, 6 and 11. We can eliminate 8 also because we know that 8 is slower than 7 and 6, and 6 is slower than 1. This makes there atleast 3 faster runners than 8.

left over now are: 1.6.11.2.3.7

We know for sure that 1 is the fastest, so we can race the remaining 5 racers and figure out the second and third fastest.

The races look like this

Race 1: 1.2.3.4.5 Results: Eliminate 4 and 5 (1,2,3 are faster)
Race 2: 6.7.8.9.10 Results: Eliminate 9 and 10 (6,7,8 are faster)
Race 3: 11.12.13.14.15 Results: Eliminate 14 and 15 (13,14,15 are faster)
Race 4: 16.17.18.19.20 Results: Eliminate 19 and 20 (18,19,20 are faster)
Race 5: 21.22.23.24.25 Results: Eliminate 24 and 25 (21,22,23 are faster)
Race 6: 1.6.11.16.21 Results: Eliminate 16,21,12,13,17,18,22,23,8 (1,6,11 are faster)
Race 7: 2.3.6.7.11 Results: Eliminate 6,7,11 (1,2,3 are faster)

The reasoning behind every elimination is that the race proves there&#39;s atleast 3 faster runners than those eliminated.


RESULT: 7 Races.

[Chevy]

Ohhhhhhhhh :o



Thanks Muchspl, was fun (took longer to work out the given answer than it did to try and guess before though :lol: )

http://www.eyecravedvd.com/forums/images/smilies/top.gif

[J'Pol]

Good novel thread, bit of a change from the usual stuff.

Well done that man, thanks for that.

[hobbes]

My head hurts and I feel stupid, thanks for that.

[muchspl2]

no problem, glad to amuse you guys for a bit :D
and congratulations to the winners, you could work for the richest person in the world

I find it funny they seem paranoid about piracy :lol:

[J'Pol]

Originally posted by muchspl2@25 April 2004 - 00:45
you could work for the richest person in the world


They could get a job in IKEA :blink:

Fan-tastic

[muchspl2]

thats right he has been over taken by the ikea guy, but billy still has the bigger house and most likely better furniture

[J'Pol]

Originally posted by muchspl2@25 April 2004 - 00:54
thats right he has been over taken by the ikea guy, but billy still has the bigger house and most likely better furniture
Absolutely correct.

Given that the IKEA guy drives an old Volvo and lives a relatively frugal lifestyle you are spot on.

BG lives in a hollowed out mountain and has an air-conditioned humidor, which contains his collection of a trillion cars which have never been driven.

I am absolutely certain that BG has the better furniture, but then so have I. ;)

[muchspl2]

some fun facts
Bill Gates&#39; home has temperature controlled rooms and art work that changes according to your mood. Everything is digitally programed for him and his family.
-100 million dollar home 66,000 sq. feet
-a trampoline room, the whole floor is a trampoline
- Master bathtub can be filled to the right temperature and depth by Gates
as he drives home from work.
- If you wish, your music will follow you throughout the house - even at
the bottom of the pool.
- Gates insisted on saving a 40 year old maple adjacent to the driveway.
The tree is monitored electronically 24 hours per day via computer. If
it seems dry, it gets just the right amount of water automatically
delivered.
- Security system (automated and personnel) is redundant. Hidden
cameras everywhere including interior stone walls. Sensors in the floor
can track a person to within 6 inches. System is monitored at the
Microsoft campus.
- No visible electrical outlets anywhere. Gates does not like "clutter".

Image Resized
[img]http://www.usnews.com/usnews/tech/billgate/graphics/gates.gif' width='200' height='120' border='0' alt='click for full size view'> ('http://www.usnews.com/usnews/tech/billgate/graphics/gates.gif')