wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> microsoft >> General River Crossing
        
(Message started by: kens on Feb 4^th, 2008, 11:51am)

Title: General River Crossing
Post by kens on Feb 4^th, 2008, 11:51am

X cannibals and Y anthropologists have to cross a river ( Y is greater than or equal to X).
the boat they have is only big enough for two people. if at any point in time there are more cannibals on one side of the river than anthropologists, the cannibals will eat them. Give a generic way to solve this problem.

Title: Re: General River Crossing
Post by Grimbal on Feb 5^th, 2008, 1:26am

[hide]Starting with the boat and all A's and C's on the left side.

While there are more A's than C's on the left side
A and C cross, C crosses back

At that point, we have at least 1 more A right than C's. Left, we have 1 A for each C.

Repeat
A and C cross, A crosses back, A and C cross, C crosses back.
It ends nicely with the last A and the last C crossing together.
[/hide]

Title: Re: General River Crossing
Post by JiNbOtAk on Feb 5^th, 2008, 3:19am

What if A = C ? Is it solvable for N > 3 ? ( Maybe we would need a bigger boat )

Title: Re: General River Crossing
Post by Grimbal on Feb 5^th, 2008, 5:11am

Oops.. I didn't see X can equal Y.

~~I think it still can be done up to 4 A's and 4 C's.~~
OK, 3 A's and 3 C's.

Title: Re: General River Crossing
Post by JiNbOtAk on Feb 5^th, 2008, 4:39pm

Would 4 A's and 4 C's be possible, if the capacity of the boat is now 3 ?

In other words, would there always be solution for A = C, N > 3, B = N - 1 ?

*B = boat's capacity.

Title: Re: General River Crossing
Post by Grimbal on Feb 5^th, 2008, 10:30pm

I think you need 2B-1 >= N.
So yes to your question.

PS: oops, in fact, B=4 is always enough.
So
N=3: B=2,
N=4, 5: B=3
N>=6: B=4

Title: Re: General River Crossing
Post by mad on Mar 3^rd, 2008, 6:08am

But, what is the algorithm in this case?

Title: Re: General River Crossing
Post by Grimbal on Mar 3^rd, 2008, 6:19am

In which case?

Title: Re: General River Crossing
Post by mad on Mar 3^rd, 2008, 6:28am

For any n and required b.
Is it the same as in the case of 3 cannibals and 3 anthropologists?

Title: Re: General River Crossing
Post by Grimbal on Mar 3^rd, 2008, 8:21am

Yes, 3 cannibals and 3 anthropologists can be solved with a 2-seated boat, that's what I mean with
N=3: B=2

Title: Re: General River Crossing
Post by mad on Mar 3^rd, 2008, 9:19am

on 02/05/08 at 01:26:52, Grimbal wrote:

I meant an algorithm of this type for any n and its required b.

Title: Re: General River Crossing
Post by Grimbal on Mar 3^rd, 2008, 9:25am

For large N's you need a 4-seated boat. And in that case, the solution is obvious. Can't you see it?