Wednesday, June 08, 2005

Tickle your mind

Ok, I am back, free and unemployed, so I have time to make my favorite hobby, which is to add silly things on this blog :D

Ok, the following was a question in an interview, see if it worth solving :

4 men on one side of a bridge, the bridge can't bear more than 2 men two cross it at a time, the four men has one torch and they can't cross it in the dark without it

the first man takes 1 minute to cross the bridge distance, the second takes 2 minutes, the third takes 5 and the fourth takes 10 minutes

now if two of them walk on the bridge together , they will arrive after a time equal to the time of the slower of them, example if person 1 and person 3 go together, they will arrive in 5 minutes, then person 1 (for example) should return back to return the torch to the others on the other side so they can cross using it .

now the bridge will collapse in exactly 17 minutes, you are required to find a way to make all men cross the bridge in 17 minutes

there is no tricks here, just a simple answer, have fun!!



free soul said...

Not a single answer !!!!

I know it is not that hard, I expected many answers in one day !!

I wonder!

FROGGY said...

hey.. do u expect me to try to use my brain after all that?? just kidding.
i thought a while about it. my conclusion is that if thinking methodetically, not arriving to a solution so we have to think in a different way (u know how we forgot to do that).
anyway i was thinking of unsual answers.
i asked my bro, he said just 2 carry the other 2.. but i guess the bridge can't hold the weight of the 4 or is it just can't hold 2 beside each others?

here are some of the unusual solutions i came up with (just for fun)

1) 1st the 3rd and 4th cross the bridge in 10 minutes then they throw the torche to the other side so that the 1st and 2nd cross the bridge in 2 minutes.

2) 1st and 4th cross the bridge in 10 min then 1st goes back with torch in 1 min (now 11 min) then 2nd and 3rd cross the bridge in 5 min (now 16 min) then the 1st knows already the bridge cos he crossed twice so he doesn't need the torch and cross in 1 min, total is 17 min.

well that's for now.. i used my brain for long time it needs rest.. lol

free soul said...

I know it is really hard to start to think after a 5 years of mathematical work that turned me into a complete donkey!! I even feel my ears longer!!

you know, the first year, I made an IQ test, it was 146, after 2 years , I made a new one, it was 138, now, it is 134 :(

ok, there is no trick here, they won't throw the torch to each other, and the man can't walk in the dark, believe me, it has a simple direct answer (may be not that simple) but no tricks in there :D

I had that question in one of the 101 interviews I had up to now, actually, they stated in the question that you can't throw the torch :)

let your processor -I mean brain- cool up, and think again, sure you will find it :)

Steliano Ponticos said...

Two methods for the solution are possible, mein freund (My friend):

1)This is a scheduling problem. We can try to set up a linear program and solve it.

2)Take an algorithmic approach:

2,1)Define the space of solutions
2,2)Define an efficient way of running over this space
2,3)Good luck

I will have the answer by tonight. I think French time is one hour behind Cairo time, OK.

If I don't have it then you can ask me whatever you want. I like this. Thx for telling me about it.

free soul said...

steliano, you remind me of the AI topics , especially when you talk about state space search :(

free soul said...

just 2 hints to make it easier as I am starting to think it is really hard:

1- it is clear that to minimize the time, we need to move the third (5mins) and the 4th (10mins) together

2- don't think that the lowest time will be walking around all the time holding the torch, others will hold it sometimes too :)

Good luck all :D

Steliano Ponticos said...

Is it so horrible that you remember AI :)

There is one thing I can't understand. If for instance 1 brings back the torch to 5 and 10 he has to come back with one of them...right

It seems however I arrange them they always need more than 17 I lost the can ask me anything you want

Ahmad El-Saeed said...

cross the bridge & stay there in the second side walla cross bass ?

free soul said...

ahmed, they can go and return as much as they want, but at the end of the 17 mins, all of them should BE ON THE OTHER SIDE OF THE BRIDGE