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

## Arvind Narayanan's journal

Research Blog | Web page

Puzzle [Jul. 11th, 2007|04:08 pm]
Arvind Narayanan
 [ Tags | puzzle ] [ 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.

 From: 2007-07-12 07:02 am (UTC) (Link)
Thanks, that was cute. Offer something more challenging. :-)
 From: 2007-07-13 01:46 pm (UTC) (Link)
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?
 From: 2007-07-14 01:41 am (UTC) (Link)
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?
 From: (Anonymous)2007-07-14 05:05 am (UTC) (Link)
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

 From: 2007-07-14 08:07 am (UTC) (Link)
"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 :)
 From: (Anonymous)2007-07-16 09:35 pm (UTC) (Link)

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

-vinod