﻿ The Four travelers
21 May, 2013, 12:49:04
 OmnomIRC You must Register, be logged in and have at least 40 posts to use this shout-box! If it still doesn't show up afterward, it might be that OmnomIRC is disabled for your group or under maintenance.Note: You can also use an IRC client like mIRC, X-Chat or Mibbit to connect to an EFnet server and #omnimaga.

 Pages: [1]   Go Down
 Author Topic: The Four travelers -  (Read 856 times) 0 Members and 1 Guest are viewing this topic.
AngelFish
This is my custom title
LV12 Extreme Poster (Next: 5000)

Offline

Gender:
Last Login: 18 May, 2013, 00:41:29
Date Registered: 15 August, 2010, 09:18:54
Posts: 3187

Topic starter
Total Post Ratings: +218

 « on: 17 June, 2011, 01:22:00 » 0

Four travelers, Mr. A, B, C, and D, have to cross a bridge over a deep ravine. It 's a very dark night and the they have only an old fashioned oil lamp for light. The light is essential for successfully crossing the ravine because the bridge is very old and has a lot of holes and loose boards. Even worse, its construction is really quite weak, and in its dilapidated condition, it can only support two of the men at a time. They are also out of cell phone range and are so unable to call for help. If two men cross the bridge together, the time for them to cross is equal to the crossing time of the slower man because the faster man must help the other along.

How should the men arrange themselves to cross the bridge in the fastest possible time?

Mr. A takes 1 minute to cross the bridge.
Mr. B takes 2 minutes to cross.
Mr. C takes 5 minutes to cross.
Mr. D is recovering from surgery and takes 10 minutes to cross.

Example (not the best solution):

A and D cross first, taking 10 minutes to cross.
A returns with the light, taking another 1 minute.
B and C cross, taking 5 minutes.
B returns with the light in 2 minutes.
A and B cross, taking 2 more minutes.
Total time = 10+1+5+2+2 = 20 Minutes.

It took me about 5 minutes to solve this problem. How long did it take you?
 « Last Edit: 17 June, 2011, 01:23:05 by Qwerty.55 » Logged

∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ
Guest
 « Reply #1 on: 17 June, 2011, 01:34:12 » 0

A, D over, 10
A back, 1
A, C over, 5
A back, 1
A, B over, 2

Total, 19

Optimized one cycle
 « Last Edit: 17 June, 2011, 01:34:31 by Ashbad » Logged
AngelFish
This is my custom title
LV12 Extreme Poster (Next: 5000)

Offline

Gender:
Last Login: 18 May, 2013, 00:41:29
Date Registered: 15 August, 2010, 09:18:54
Posts: 3187

Topic starter
Total Post Ratings: +218

 « Reply #2 on: 17 June, 2011, 01:36:00 » 0

That's still not the optimal solution
 Logged

∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ
Guest
 « Reply #3 on: 17 June, 2011, 01:37:56 » 0

Really?  O.o. All I did for mine is make A cross over with the light instead of B on the second pass, saves 1 minute.  I wonder what it is
 Logged
Quigibo
The Executioner
LV11 Super Veteran (Next: 3000)

Offline

Gender:
Date Registered: 22 January, 2010, 05:02:37
Location: Los Angeles
Posts: 2022

Total Post Ratings: +1019

 « Reply #4 on: 17 June, 2011, 04:12:31 » 0

From a game theory perspective, I'd have to agree that 19 is the minimum amount of time it can take unless there is something fundamental about this problem that I'm not understanding (which I assume there is).

-Each trip across must be a full trip due to the 3 person rule.  Otherwise it could only increase the time.
-Mr. A has to travel with every person or else it could only increase time.
-I'm assuming you can't "toss" the lamp over the bridge, set it on fire, or cut it and swing to the other side.
 Logged

___Axe_Parser___
Today the calculator, tomorrow the world!
leafy
Coder Of Tomorrow
LV10 31337 u53r (Next: 2000)

Offline

Gender:
Date Registered: 26 December, 2010, 05:27:03
Location: the ninth circle of hell
Posts: 1545

Total Post Ratings: +371

 « Reply #5 on: 17 June, 2011, 04:17:55 » 0

I saw this problem, and I remember it was either 15 or 17 for the optimal solution. I'll try working it out again ^^
 Logged

In-progress: Blastlabs, TMJO, qb?, VVVVVV?
Finished: Tag, Tap, MFQT, Nyan
AngelFish
This is my custom title
LV12 Extreme Poster (Next: 5000)

Offline

Gender:
Last Login: 18 May, 2013, 00:41:29
Date Registered: 15 August, 2010, 09:18:54
Posts: 3187

Topic starter
Total Post Ratings: +218

 « Reply #6 on: 17 June, 2011, 06:07:00 » 0

From a game theory perspective, I'd have to agree that 19 is the minimum amount of time it can take unless there is something fundamental about this problem that I'm not understanding (which I assume there is).

-Each trip across must be a full trip due to the 3 person rule.  Otherwise it could only increase the time.

Going forwards across the bridge, yes. One person must necessarily travel back across the bridge to bring the lamp back to the others. But I assure you that 19 is *not* the minimum time required and I also highly recommend not using Google for the answer.
 Logged

∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ
Builderboy
Physics Guru

Offline

Gender:
Date Registered: 20 April, 2009, 00:28:53
Location: Ravenholm
Posts: 5642

Total Post Ratings: +589

 « Reply #7 on: 17 June, 2011, 06:16:49 » 0

17 is the optimal solution and let me assure you the solution does not involve anything tricky like leaving members in the middle of the bridge or anything
 Logged

Juju
Evil Fluttershy (Site issues must be PM'ed to Netham45, Eeems, Shmibs, Deep Thought and AngelFish, not me.)
Coder Of Tomorrow
LV12 Extreme Poster (Next: 5000)

Offline

Gender:
Date Registered: 17 March, 2010, 07:46:57
Location: Québec, North Equestria
Posts: 4535

Total Post Ratings: +394

 « Reply #8 on: 17 June, 2011, 06:26:19 » 0

Hmmm... It's kinda hard.
 Logged

LuaIDE
Reuben Quest HD: The PC Remake

Spoiler for Other stuff:
Also Yuki "ジュジュ" Kagayaki
Support Casio-Scene against the attacks of matt @ matpac.co.uk ! For more information: Casio-Scene shuts down & Matt actions threads
Find what P+4zJ means and you get free candy! cc4daa9c4645bd123ed22e385ed701fd
#omnimaga on OmniNet, EFNet and Pesterchum
Fan of My Little Jim Bauwens: Losing the Game is Magic
Proud member of POLN - Ponys Oppositing Lol Names
Member of OBEL - Omnimaga Board of the EFnrgelnicshh Language - Office Omnimagois de la Langue FArnagnlçaaiiss
あなたはこのゲームを失った
Spoiler for Old spoileryception stuff:

Spoiler for Coming soon...:
Indefinitely halted [|.........] 10%
OmnomIRC Mobile [||||......] 40% (argh threads >_<)
Spoiler for Current/Past TI-related projects:
The Axe Parser Wiki / Founder and maintainer
Keytar Hero [|||||_____] 50% Engine done, wackiness left to do (Halted)
OmniOS
VVVVVV [||||______] 40% (Made most of the engine, extremely glitchy) (Gave it to Leafy)
░█▀█░█░█░█▀▀░█▀█░█▀█░█▀█░▀█▀░█▀▄
░█▀█░▄▀▄░█▀▀░█▀█░█░█░█░█░░█░░█░█
v0.1.0
░▀░▀░▀░▀░▀▀▀░▀░▀░▀░▀░▀▀▀░▀▀▀░▀▀░[|||||||||¦] 95ish% (Completed)
tilibs-wii? [._________] 0% (Nope.)
Spoiler for Spoilers:
<!---->
wxWabbitemu Developer
Spoiler for Other Userbars:

<!--Everything done, got 90% sudo apt-get install z80asm z80dasm-->
Spoiler for Quote:
We are in 2034. The situation on Earth is catastrophic. The ozone layer has been completely destroyed by the carbonic gas of automobiles, the chemical industries, and the poosh-poosh in little cans. In the end, the earth cooks under the rays of the sun. We must find a planet on which can live 6 billion idiots. The planetary federation turns to the strongest country in the world: Canada. It is Canadian knowledge that has allowed, on October 28, 2034, the launch of the spaceship Romano Fafard, which leaves earth to search the confines of the Universe. Where the hand of man has never set foot.
I hate TI right now
Quote from: jimbauwens
You make me lose the game
Spoiler for The real answer to life, the universe and everything:
Spoiler for Old HTML stuff:
<div style="margin:20px; margin-top:5px"><div class="smallfont" style="margin-bottom:2px">Spoiler for This is another spoiler: <input type="button" value="Show" style="width:60px;font-size:10px;margin:0px;padding:0px;" onclick="window.location.replace('http://goo.gl/QMET');"></div><div class="alt2" style="margin: 0px; padding: 6px; border: 1px inset;"><div style="display: none; ">HAHAHA SUCCESSFUL RICKROLL IS SUCCESSFUL</div></div></div><!-- old avatars:
http://fc00.deviantart.net/fs71/f/2011/120/d/f/nepeta_nyan_cat_by_supuru-d3f8tcx.gif
http://th01.deviantart.net/fs70/PRE/i/2011/099/5/b/rainbow_dash_derping_by_moongazeponies-d3dmg7l.png--><!---->
I may or may not be inactive during work hours (9AM to 5PM EST, Monday to Friday), so for any inquiries please leave a message after the beep and I'll answer you when I have time. Beep. Nevermind, I'm on vacation now.
AngelFish
This is my custom title
LV12 Extreme Poster (Next: 5000)

Offline

Gender:
Last Login: 18 May, 2013, 00:41:29
Date Registered: 15 August, 2010, 09:18:54
Posts: 3187

Topic starter
Total Post Ratings: +218

 « Reply #9 on: 17 June, 2011, 06:29:01 » 0

17 is the optimal solution and let me assure you the solution does not involve anything tricky like leaving members in the middle of the bridge or anything

Yep

EDIT: My Linux automatically threw this link into this post, so enjoy  http://community.linuxmint.com/
 « Last Edit: 17 June, 2011, 06:30:11 by Qwerty.55 » Logged

∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ
Hayleia
Programming Absol
LV11 Super Veteran (Next: 3000)

Offline

Date Registered: 01 June, 2011, 20:12:47
Location: ud-ud ?
Posts: 2046

Total Post Ratings: +254

 « Reply #10 on: 17 June, 2011, 06:50:12 » +1

AB     2    →
B       2    ←
CD     10  →
A       1   ←
AB      2   →
Total 17
 « Last Edit: 17 June, 2011, 06:50:34 by Hayleia » Logged

Spoiler for what I am according to...:
me: useless
Pokemon Test: an Absol
turiqwalrus: an eggplant
p2: A HUMAN BEING !
Blackpilar and p2: iplantonlyplantwantplanttoplantknowplantifplantyouplantareplantaplantboyplantorplantaplantgirlplant
AngelFish
This is my custom title
LV12 Extreme Poster (Next: 5000)

Offline

Gender:
Last Login: 18 May, 2013, 00:41:29
Date Registered: 15 August, 2010, 09:18:54
Posts: 3187

Topic starter
Total Post Ratings: +218

 « Reply #11 on: 17 June, 2011, 06:59:03 » 0

Bingo.
 Logged

∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ
Hayleia
Programming Absol
LV11 Super Veteran (Next: 3000)

Offline

Date Registered: 01 June, 2011, 20:12:47
Location: ud-ud ?
Posts: 2046

Total Post Ratings: +254

 « Reply #12 on: 17 June, 2011, 16:44:58 » 0

Do I explain or do you (or do anyone else do) ?
EDIT: I think I'll explain, so.
Well, the only thing is to make C and D cross the bridge together, only one time.
So, AB have to go first, then A or B comes back to give the lamp to C and D so they can cross the bridge and give the lamp to A or B (the one who stayed) so he goes back to look for the last one.
In fact, C can even be slower, his travelling time doesn't count as it is absorbed by D.

All I found on Google was the question... (°-.-)
 « Last Edit: 18 June, 2011, 09:38:54 by Hayleia » Logged

Spoiler for what I am according to...:
me: useless
Pokemon Test: an Absol
turiqwalrus: an eggplant
p2: A HUMAN BEING !
Blackpilar and p2: iplantonlyplantwantplanttoplantknowplantifplantyouplantareplantaplantboyplantorplantaplantgirlplant