?

Log in

No account? Create an account
Puzzle - Arvind Narayanan's journal [entries|archive|friends|userinfo]

Puzzle [Jul. 11th, 2007|04:08 pm]
Arvind Narayanan
[Tags|]
[Current Mood |working]

Due to popular demand one comment, I'm updating again. I don't have anything very interesting to say right now, so I'll throw out a cute puzzle I came across recently.

There are four people trying to cross a bridge. The bridge can only carry two at a time. The four have one flashlight between them. No one can be on the bridge without a flashlight. The four take 1, 2, 5 and 10 minutes respectively to cross (if more than one cross at the same time, they cross at the speed of the slowest). How can they all cross in no more than 17 minutes total?

If you think it's impossible, keep thinking. (There is no catch :-)

I'm guessing the straightforward generalization of the problem is NP-complete, but I haven't thought about it.
LinkReply

Comments:
[User Picture]From: helger
2007-07-12 07:02 am (UTC)
Thanks, that was cute. Offer something more challenging. :-)
(Reply) (Thread)
[User Picture]From: skthewimp
2007-07-13 01:46 pm (UTC)
dunno if i'm allowed to post it here but anyways...

1 and 2 cross... 1 comes back... 5 and 10 cross... 2 comes back... 1 and 2 cross... key is to make sure that the second slowest gets masked by the lowest!

what is the generalization of this probelm?
(Reply) (Thread)
[User Picture]From: arvindn
2007-07-14 01:41 am (UTC)
yup, that's it :)

think of n people with speeds a_1, a_2, ... a_n

is there an algorithm that finds the minimum time to cross, given the speeds as input?
(Reply) (Parent) (Thread)
From: (Anonymous)
2007-07-14 05:05 am (UTC)
I am guessing that perhaps it can be solved by greedy appproaches. If not, then its probably an interesting problem for a STOC/FOCS paper (prove NP-complete, prove hard to approximate using PCP etc) :)


Vipul

(Reply) (Parent) (Thread)
[User Picture]From: arvindn
2007-07-14 08:07 am (UTC)
"If not, then its probably an interesting problem for a STOC/FOCS paper"

I hope not! I'd like to think STOC and FOCS publish less frivolous stuff :)
(Reply) (Parent) (Thread)
From: (Anonymous)
2007-07-16 09:35 pm (UTC)

Frivolousness is subjective. What do you think of "Cake cutting really is not a piece of cake"? :)

-vinod
(Reply) (Parent) (Thread)
From: (Anonymous)
2007-07-19 06:14 pm (UTC)

Alternate

How about the following?
1 and 2 cross, 2 comes back, 5 and 10 cross, 1 comes back and then 1 and 2 cross (2 + 2 + 10 + 1 + 2 = 17)
In the general case, there might be lots of optimal solutions.
(Reply) (Parent) (Thread)