IB interview brain teaser (1 Viewer)

[BoganBoy]

Hi guys i came upon this supposedly interview brainteaser on an american forum . I thought the americans had sum pretty half arsed attempt at it so i thought we might give it a go. I do not have the correct solution so anyone could be right. The question goes sumthing like this

'' Imagine we have 25 horses in a stable and we want to know which are the 3 fastest horses. We can run races up to 5 horses only at a time. We cannot find out the exact race time of horses, only their ranking in their particular race.

what is the minimum number of races we need to run in order to find out the 3 fastest horses, order matters) ''

 

[BoganBoy]

Heres what i think.

1. Split up 25 horses into 5 groups (group 1-5) and race them. (5 races)

2. Label winner of each group A1, ...A5. 2nd place of each group B1........B5, 3rd place comers C1...C5

3. Race A1-A5, the fastest horse out of that race must be the fastest overall. (6 races)

4. Imagine A1 won, but it is also possible that B1 C1 are the 2nd and 3rd fastest horses overall. So we need to race B1 with A2-A5. Then two things can happen

a) B1 wins, proving its the 2nd fastest horse, then we need to race C1 with the A2-A5 to see if it is actually the 3rd fastest horse overall' (8 races all up)

b) B1 loses and one of the A2-A5 wins (lets say A2), then it is possible that B2 is the 3rd fastest horse. Then we race B2 with B1, A3-A5, winner is the 3rd fastest (again its 8 races all up)

Therefore minimum number of races is 8. Im fairly sure my way gives the right order, but pretty sure its not the most efficient way.

smart ppl out there please help?

bb

PS. if this really comes up in any interview then im F***ED.

 

[inasero]

I was thinking is it possible that B2 (or B3-B5) is faster than A1?
And also, in step 4 I think you're assuming that the five fastest horses are distrubuted one each among the five groups (1-5), whereas it might be the case that the five fastest horses are in one particular group, which could lead to a different interpretation.

 

[BoganBoy]

Well yeah you are right in saying that B2-B5 could be faster than A1, which is only the fastest of its group. However in my case i assumed A1 is the winner of the race between A1-A5, once that happens then its not possible for B2-B5 to be faster.

Without that particular race then any of the A1-A5 could be the fastest horse. saying A1 is the winner is just an example but it's also alright if we assume A2 wins out etc.

 

[BoganBoy]

The only way to prove that a particular horse is the fastest is to race that horse against every other horse in the whole group of 25.

ok, agree that the group could comprise of the top 3 horses by chance (the fact that it could contain the top 5 is irrelevant since we are only asked to find the top 3).

i disagree with what u said in the quote. the fastest horse would win every single race it's in no matter how many races it competes in. So by splitting the 25 horses into 5 groups (1-5), the fastest horse will win out of its group. We then race the WINNER from each group against each other. The fastest horse will win once again for obvious reason, and all it did was race against 8 other horses (not 24).

 

[XrealEmotion]

I used a similar method to zimmerman's and got 11 races

1) Group horses into random groups of 5 and race them (5 races)
2) The slowest 2 in each group are eliminated, leaving 25 - 10 = 15 horses
3) Group horses into random groups of 5 again and race them (3 races)
4) Eliminate slowest 2 in each group again, leaving 15 - 6 = 9 horses
5) Select a group of 5 and race them (1 race)
6) Eliminate slowest 2 in the group, leaving 9 - 2 = 7 horses
7) Keep the 3 horses that were in the previous race, and bring in 2 new horses.
8) Race them (1 race) and eliminate slowest 2 in the group, leaving 7 - 2 = 5 horses
9) Finally race the remaining horses and you will find the fastest 3 (1 race)

So a total of 11

 

[KFunk]

That is so wrong. I'll ignore the rest because it was overly complicated and annoying.

If you split them into groups randomly, one group could have been comprised of the five fastest to begin with, purely by chance.

The only way to prove that a particular horse is the fastest is to race that horse against every other horse in the whole group of 25.

Nah, assuming that the horses run constant times Boganboy's method for finding the fastest horse appears to be correct (since, as he said, it will necessarily win every race it is in --> thus his A1-5 race may not have the five fastest horses, but it will necessarily have the fastest horse, singular).

 

[KFunk]

A method that is similar, but faster, than those that have so far been provided:


1) Start with five races [Cumulative total races (CT) = 5], with racing groups labelled G1 through to G5

2) Eliminate the bottom two from every race (since they cannot be in the top three) leaving 15 horses

3) Race the winners (call them H1 - H5) from each of the groups G1 - G5 and eliminate NOT ONLY the bottom two horses in this race, but also the horses from their respective initial racing groups, leaving 9 horses. Note also that the winner of the race can be isolated as the fastest horse. Thus the task is to find the fastest two of the reamining 8 horses (CT = 6).

4) At this point note that we want to find the fastest TWO horses of the remaining 8. Suppose that the top three horses in the previous race (HX, HY & HZ) came from initial races GX, GY and GZ, respectively --> we can then eliminate those horses which came third in races GY and GZ, leaving 6 horses.

5) Furthermore, HX > HY > HZ, and HZ > the horse which came 2nd in race GZ. Thus we can eliminate this horse also, leaving 5 horses.

6) Race the remaining 5 horses to find the top two. (CT = 7)


Voila, we have determined the top 3 horses in seven races. Apologies if my reasoning is poorly communicated (late night posting!).

 

[KFunk]

EDIT: lol b10 by 4mins by Kfunk, but at least we backed each other up.

Haha, amusing timing (and I agree that consistency is nice). It probably helps to have two versions of the same argument given how hard it is to express clearly, though I suspect your formulation is more easily understood.

 

[KFunk]

Oh dear - I closed my eyes to fall asleep but I couldn't help thinking of a slightly more abstracted version of the horse problem:

Using the same reasoning , if you want to find the top three out of n^2 horses, but can only race them n at a time, then the minimum number of races required will = n + 2.

For the mathematically inclined: I wonder what the answer to the more generalised question is (i.e. what is the minimum number of races required to find the top 'x' when you have 'y' horses but can only race 'z' at a time).

 

[KFunk]

And again... (sleep is not forthcoming)

Using brogan's simpler way of expressing things. Suppose that we have n^2 horses which we can race 'n' at a time, but where we want to find the top m fastest horses (where m < n).

Again we can run n races of n horses. The winner of each is entered into a new race after which the horses may then be ranked H1, H2, ... Hn (with each of these horses coming from the initial heat groups G1, G2, ... Gn respectively). As brogan argued, the horses which are still in the running are:

The first m from G1
The first m -1 from G2
The first m -2 from G3
...
The first 2 from G(m-1)
The first 1 from Gm

Thus the number of remaining horses is just the sum of natural numbers up to 'm' (= m(m+1)/2 ... but subtract 1 for the fastest horse). So long as m(m+1)/2 - 1 does not exceed n we can still work out the top 'm' horses in n+2 races.

 

[KFunk]

Thus the number of remaining horses is just the sum of natural numbers up to 'm' (= m(m+1)/2 ... but subtract 1 for the fastest horse). So long as m(m+1)/2 - 1 does not exceed n we can still work out the top 'm' horses in n+2 races.

And sadly there doesn't seem to be an elegant expression for the m(m+1)/2 -1 > n cases (You end up with a recursive algorithmic process - i.e. where you use roughly the same procedure as in the 25 horse example - which makes use of division and remainders, so perhaps a modulo arithmetic formulation could be more effective. Sadly a numerical substitution where n=1000 and m=999 showed that it needn't terminate after the first repitition. Easily operationalised, but not easily expressed in an equation which can quickly give you the required number of races - alas!). Sleep time.

 

[BoganBoy]

Kfunk and Brogan thanks for your inputs and now i agree you can do it in 7 races.

anyone thinks they can get less than 7?

just out of curiosity how long did it take you guys to come up with a solution? took me a good 10min pen and paper in hand, and its suppose to be an interiew questions?!!??!

 

[wrong_turn]

haha counting sheep?....the new age way...counting horses

 

[lolokay]

Kfunk and Brogan thanks for your inputs and now i agree you can do it in 7 races.

anyone thinks they can get less than 7?

just out of curiosity how long did it take you guys to come up with a solution? took me a good 10min pen and paper in hand, and its suppose to be an interiew questions?!!??!

i'm quite sure you can't get it in less than 7. you have to race each horse at least once, or you'll have horses you don't know the relative placing of. and you have to race some horses more than once to get their placing relative to each other, so you need more than 5 races.
I know this doesn't rule out 6 races, but i just don't see how you could possibly get it in less than 7

(btw, got the 7 race scenario in a matter of seconds)

 

[jb_nc]

Here's a discussion on the problem generalised for j horses: http://www.wilmott.com/messageview.cfm?catid=26&threadid=64478&STARTPAGE=1

I got 7. I think that is right.

 

[KFunk]

Here's a discussion on the problem generalised for j horses: http://www.wilmott.com/messageview.cfm?catid=26&threadid=64478&STARTPAGE=1

I got 7. I think that is right.

Cheers for the link. It's quite interesting, especially the special cases illustrated by the dude 'altoz'. They too seem to find that the problem seems to require recursive algorithms once the parameters exceed certain bounds.

just out of curiosity how long did it take you guys to come up with a solution? took me a good 10min pen and paper in hand, and its suppose to be an interiew questions?!!??!

Once I drew up a 5x5 matrix/grid and started crossing off horses the answer followed pretty quickly (~1-2 mins?). I would likely have been a lot slower without the visual representation.