Author |
Topic: General River Crossing (Read 2843 times) |
|
kens
Junior Member
Posts: 59
|
 |
General River Crossing
« on: Feb 4th, 2008, 11:51am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: General River Crossing
« Reply #1 on: Feb 5th, 2008, 1:26am » |
Quote Modify
|
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.
|
| « Last Edit: Feb 5th, 2008, 1:28am by Grimbal » |
IP Logged |
|
|
|
JiNbOtAk
Uberpuzzler
Hana Hana No Mi
Gender:
Posts: 1187
|
|
Re: General River Crossing
« Reply #2 on: Feb 5th, 2008, 3:19am » |
Quote Modify
|
What if A = C ? Is it solvable for N > 3 ? ( Maybe we would need a bigger boat )
|
|
IP Logged |
Quis custodiet ipsos custodes?
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: General River Crossing
« Reply #3 on: Feb 5th, 2008, 5:11am » |
Quote Modify
|
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.
|
| « Last Edit: Feb 5th, 2008, 5:21am by Grimbal » |
IP Logged |
|
|
|
JiNbOtAk
Uberpuzzler
Hana Hana No Mi
Gender:
Posts: 1187
|
|
Re: General River Crossing
« Reply #4 on: Feb 5th, 2008, 4:39pm » |
Quote Modify
|
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.
|
|
IP Logged |
Quis custodiet ipsos custodes?
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: General River Crossing
« Reply #5 on: Feb 5th, 2008, 10:30pm » |
Quote Modify
|
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
|
| « Last Edit: Feb 5th, 2008, 10:34pm by Grimbal » |
IP Logged |
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: General River Crossing
« Reply #6 on: Mar 3rd, 2008, 6:08am » |
Quote Modify
|
But, what is the algorithm in this case?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: General River Crossing
« Reply #7 on: Mar 3rd, 2008, 6:19am » |
Quote Modify
|
In which case?
|
|
IP Logged |
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: General River Crossing
« Reply #8 on: Mar 3rd, 2008, 6:28am » |
Quote Modify
|
For any n and required b.
Is it the same as in the case of 3 cannibals and 3 anthropologists?
|
| « Last Edit: Mar 3rd, 2008, 6:29am by mad » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: General River Crossing
« Reply #9 on: Mar 3rd, 2008, 8:21am » |
Quote Modify
|
Yes, 3 cannibals and 3 anthropologists can be solved with a 2-seated boat, that's what I mean with
N=3: B=2
|
|
IP Logged |
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: General River Crossing
« Reply #10 on: Mar 3rd, 2008, 9:19am » |
Quote Modify
|
on Feb 5th, 2008, 1:26am, Grimbal wrote: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.
|
|
I meant an algorithm of this type for any n and its required b.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: General River Crossing
« Reply #11 on: Mar 3rd, 2008, 9:25am » |
Quote Modify
|
For large N's you need a 4-seated boat. And in that case, the solution is obvious. Can't you see it?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print