River crossing with boat
Clash Royale CLAN TAG#URR8PPP
up vote
9
down vote
favorite
Alan, Bill, Charly, Dean and Edgar are going to cross a river to reach the opposite river bank by using a small boat. The rules are very strict because the river is deep and dangerous:
For the boat not to sink, the 5 friends must be seated one behind the other, starting from the lightest, in order of weight. All friends are of different weight!
All they have with them is a balance scale. Given that their time is limited, they must determine the order by the least number of weightings. Can you help them?
Starting with A+B we determine AB.
Say we have $A>B$. Then we add C and weight it against, say, the lightest. $B+C$. If we have $C<B$ then $C<B<A$. But we can't go on with such a simplistic approach. There must be something clever which I am missing.
combinatorics
asked Sep 2 at 10:33
Chen Aavaz
1315
 |Â
show 1 more comment
up vote
9
down vote
favorite
Alan, Bill, Charly, Dean and Edgar are going to cross a river to reach the opposite river bank by using a small boat. The rules are very strict because the river is deep and dangerous:
For the boat not to sink, the 5 friends must be seated one behind the other, starting from the lightest, in order of weight. All friends are of different weight!
All they have with them is a balance scale. Given that their time is limited, they must determine the order by the least number of weightings. Can you help them?
Starting with A+B we determine AB.
Say we have $A>B$. Then we add C and weight it against, say, the lightest. $B+C$. If we have $C<B$ then $C<B<A$. But we can't go on with such a simplistic approach. There must be something clever which I am missing.
combinatorics
asked Sep 2 at 10:33
Chen Aavaz
1315
2
What you're looking for is a sorting algorithm.
– Arthur
Sep 2 at 10:40
Donald Knuth, "The Art of Computer Programming, Vol. 3, Sorting and Searching", section 5.3.1, shows that the minimum number of comparisons is 7. He attributes the method to H. B. Demuth, Ph.D. thesis, Stanford University, Oct. 1956.
– awkward
Sep 2 at 12:42
Since we often have real river crossing problems here I suggest a different title.
– Christian Blatter
Sep 2 at 15:50
@awkward: I am a bit confused. The document you suggest ("The Art of Computer Programming, Vol. 3, Sorting and Searching"), gives a solution in 7 weighings, whereas TonyK solution needs 9. Which one is correct?
– Preechapak Tekasuk
Sep 3 at 18:05
@PreechapakTekasuk If Knuth says he can do it in 7 comparisons, I am inclined to believe him. $7 < 9$.
– awkward
Sep 3 at 18:35
 |Â
show 1 more comment
up vote
9
down vote
favorite
up vote
9
down vote
favorite
Alan, Bill, Charly, Dean and Edgar are going to cross a river to reach the opposite river bank by using a small boat. The rules are very strict because the river is deep and dangerous:
For the boat not to sink, the 5 friends must be seated one behind the other, starting from the lightest, in order of weight. All friends are of different weight!
All they have with them is a balance scale. Given that their time is limited, they must determine the order by the least number of weightings. Can you help them?
Starting with A+B we determine AB.
Say we have $A>B$. Then we add C and weight it against, say, the lightest. $B+C$. If we have $C<B$ then $C<B<A$. But we can't go on with such a simplistic approach. There must be something clever which I am missing.
combinatorics
asked Sep 2 at 10:33
Chen Aavaz
1315
Alan, Bill, Charly, Dean and Edgar are going to cross a river to reach the opposite river bank by using a small boat. The rules are very strict because the river is deep and dangerous:
For the boat not to sink, the 5 friends must be seated one behind the other, starting from the lightest, in order of weight. All friends are of different weight!
All they have with them is a balance scale. Given that their time is limited, they must determine the order by the least number of weightings. Can you help them?
Starting with A+B we determine AB.
Say we have $A>B$. Then we add C and weight it against, say, the lightest. $B+C$. If we have $C<B$ then $C<B<A$. But we can't go on with such a simplistic approach. There must be something clever which I am missing.
combinatorics
combinatorics
asked Sep 2 at 10:33
Chen Aavaz
1315
asked Sep 2 at 10:33
Chen Aavaz
1315
edited Sep 2 at 10:39
asked Sep 2 at 10:33
Chen Aavaz
1315
asked Sep 2 at 10:33
Chen Aavaz
1315
asked Sep 2 at 10:33
Chen Aavaz
1315
1315
2
What you're looking for is a sorting algorithm.
– Arthur
Sep 2 at 10:40
Donald Knuth, "The Art of Computer Programming, Vol. 3, Sorting and Searching", section 5.3.1, shows that the minimum number of comparisons is 7. He attributes the method to H. B. Demuth, Ph.D. thesis, Stanford University, Oct. 1956.
– awkward
Sep 2 at 12:42
Since we often have real river crossing problems here I suggest a different title.
– Christian Blatter
Sep 2 at 15:50
@awkward: I am a bit confused. The document you suggest ("The Art of Computer Programming, Vol. 3, Sorting and Searching"), gives a solution in 7 weighings, whereas TonyK solution needs 9. Which one is correct?
– Preechapak Tekasuk
Sep 3 at 18:05
@PreechapakTekasuk If Knuth says he can do it in 7 comparisons, I am inclined to believe him. $7 < 9$.
– awkward
Sep 3 at 18:35
 |Â
show 1 more comment
2
What you're looking for is a sorting algorithm.
– Arthur
Sep 2 at 10:40
Donald Knuth, "The Art of Computer Programming, Vol. 3, Sorting and Searching", section 5.3.1, shows that the minimum number of comparisons is 7. He attributes the method to H. B. Demuth, Ph.D. thesis, Stanford University, Oct. 1956.
– awkward
Sep 2 at 12:42
Since we often have real river crossing problems here I suggest a different title.
– Christian Blatter
Sep 2 at 15:50
@awkward: I am a bit confused. The document you suggest ("The Art of Computer Programming, Vol. 3, Sorting and Searching"), gives a solution in 7 weighings, whereas TonyK solution needs 9. Which one is correct?
– Preechapak Tekasuk
Sep 3 at 18:05
@PreechapakTekasuk If Knuth says he can do it in 7 comparisons, I am inclined to believe him. $7 < 9$.
– awkward
Sep 3 at 18:35
2
2
What you're looking for is a sorting algorithm.
– Arthur
Sep 2 at 10:40
What you're looking for is a sorting algorithm.
– Arthur
Sep 2 at 10:40
Donald Knuth, "The Art of Computer Programming, Vol. 3, Sorting and Searching", section 5.3.1, shows that the minimum number of comparisons is 7. He attributes the method to H. B. Demuth, Ph.D. thesis, Stanford University, Oct. 1956.
– awkward
Sep 2 at 12:42
Donald Knuth, "The Art of Computer Programming, Vol. 3, Sorting and Searching", section 5.3.1, shows that the minimum number of comparisons is 7. He attributes the method to H. B. Demuth, Ph.D. thesis, Stanford University, Oct. 1956.
– awkward
Sep 2 at 12:42
Since we often have real river crossing problems here I suggest a different title.
– Christian Blatter
Sep 2 at 15:50
Since we often have real river crossing problems here I suggest a different title.
– Christian Blatter
Sep 2 at 15:50
@awkward: I am a bit confused. The document you suggest ("The Art of Computer Programming, Vol. 3, Sorting and Searching"), gives a solution in 7 weighings, whereas TonyK solution needs 9. Which one is correct?
– Preechapak Tekasuk
Sep 3 at 18:05
@awkward: I am a bit confused. The document you suggest ("The Art of Computer Programming, Vol. 3, Sorting and Searching"), gives a solution in 7 weighings, whereas TonyK solution needs 9. Which one is correct?
– Preechapak Tekasuk
Sep 3 at 18:05
@PreechapakTekasuk If Knuth says he can do it in 7 comparisons, I am inclined to believe him. $7 < 9$.
– awkward
Sep 3 at 18:35
@PreechapakTekasuk If Knuth says he can do it in 7 comparisons, I am inclined to believe him. $7 < 9$.
– awkward
Sep 3 at 18:35
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
1
down vote
Edited to add:
The algorithm presented in this answer is not optimal, as @awkward points out in a comment to the OP. There is a faster method, due to H. B. DeMuth, that requires only seven comparisons.
The algorithm given below is the best you can do if your sequence of comparisons has to be specified in advance.
John M. Gamble's Sorting Networks is the place to go when you want to sort a small list with the fewest comparisons. Selecting N=5 gives you this list of nine weighings to perform:
SWAP(0, 1);
SWAP(3, 4);
SWAP(2, 4);
SWAP(2, 3);
SWAP(0, 3);
SWAP(0, 2);
SWAP(1, 4);
SWAP(1, 3);
SWAP(1, 2);
Here, SWAP(x,y) means "Swap x and y if x weighs more than y."
Note that you can't just replace $0$ with $A$, $1$ with $B$ etc, because the numbers refer to positions in the list, not to people. So what you do is this:
Make five flash cards, with the numbers $0,1,2,3,4$ written on them. Give everybody a card. Then SWAP(x,y) means:
Put the holders of flash cards x and y on the balance scale. If the holder of flash card x weighs more than the holder of flash card y, have them swap cards.
After the nine weighings in the list, have them line up in the order of the cards that they hold.
answered Sep 2 at 11:11
TonyK
38.7k348127
1
TonyK thank you for your reply. Can you possibly explain in a simpler way? I didn't quite understand your method and, most importantly, why this gives the minimum number of weighings.
– Chen Aavaz
Sep 3 at 8:01
@ChenAavaz: I suggest you google Bose-Nelson for more information.
– TonyK
Sep 3 at 11:21
1
@TonyK I don't think this is the proper way to reply! I don't understand either - maybe a couple of hints would be more useful than asking us to do a research on google. Btw I did already and didn't find any clear reference, so that someone can understand! Thanking you in advance.
– Jason
Sep 3 at 13:03
1
@TonyK: So in practical terms, who do we weight against whom, and how do we proceed basis each result?
– Creton Laplace
Sep 3 at 13:06
@CretonLaplace: the answer gives that. You could think of them all being in line and the first step is to weigh the first two and put them back with the lighter first. Then you weigh the fourth and fifth people and put them back in order. In the third step you weigh the middle person against the one who is now last and so on.
– Ross Millikan
Sep 3 at 14:44
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Edited to add:
The algorithm presented in this answer is not optimal, as @awkward points out in a comment to the OP. There is a faster method, due to H. B. DeMuth, that requires only seven comparisons.
The algorithm given below is the best you can do if your sequence of comparisons has to be specified in advance.
John M. Gamble's Sorting Networks is the place to go when you want to sort a small list with the fewest comparisons. Selecting N=5 gives you this list of nine weighings to perform:
SWAP(0, 1);
SWAP(3, 4);
SWAP(2, 4);
SWAP(2, 3);
SWAP(0, 3);
SWAP(0, 2);
SWAP(1, 4);
SWAP(1, 3);
SWAP(1, 2);
Here, SWAP(x,y) means "Swap x and y if x weighs more than y."
Note that you can't just replace $0$ with $A$, $1$ with $B$ etc, because the numbers refer to positions in the list, not to people. So what you do is this:
Make five flash cards, with the numbers $0,1,2,3,4$ written on them. Give everybody a card. Then SWAP(x,y) means:
Put the holders of flash cards x and y on the balance scale. If the holder of flash card x weighs more than the holder of flash card y, have them swap cards.
After the nine weighings in the list, have them line up in the order of the cards that they hold.
answered Sep 2 at 11:11
TonyK
38.7k348127
1
TonyK thank you for your reply. Can you possibly explain in a simpler way? I didn't quite understand your method and, most importantly, why this gives the minimum number of weighings.
– Chen Aavaz
Sep 3 at 8:01
@ChenAavaz: I suggest you google Bose-Nelson for more information.
– TonyK
Sep 3 at 11:21
1
@TonyK I don't think this is the proper way to reply! I don't understand either - maybe a couple of hints would be more useful than asking us to do a research on google. Btw I did already and didn't find any clear reference, so that someone can understand! Thanking you in advance.
– Jason
Sep 3 at 13:03
1
@TonyK: So in practical terms, who do we weight against whom, and how do we proceed basis each result?
– Creton Laplace
Sep 3 at 13:06
@CretonLaplace: the answer gives that. You could think of them all being in line and the first step is to weigh the first two and put them back with the lighter first. Then you weigh the fourth and fifth people and put them back in order. In the third step you weigh the middle person against the one who is now last and so on.
– Ross Millikan
Sep 3 at 14:44
 |Â
show 1 more comment
up vote
1
down vote
Edited to add:
The algorithm presented in this answer is not optimal, as @awkward points out in a comment to the OP. There is a faster method, due to H. B. DeMuth, that requires only seven comparisons.
The algorithm given below is the best you can do if your sequence of comparisons has to be specified in advance.
John M. Gamble's Sorting Networks is the place to go when you want to sort a small list with the fewest comparisons. Selecting N=5 gives you this list of nine weighings to perform:
SWAP(0, 1);
SWAP(3, 4);
SWAP(2, 4);
SWAP(2, 3);
SWAP(0, 3);
SWAP(0, 2);
SWAP(1, 4);
SWAP(1, 3);
SWAP(1, 2);
Here, SWAP(x,y) means "Swap x and y if x weighs more than y."
Note that you can't just replace $0$ with $A$, $1$ with $B$ etc, because the numbers refer to positions in the list, not to people. So what you do is this:
Make five flash cards, with the numbers $0,1,2,3,4$ written on them. Give everybody a card. Then SWAP(x,y) means:
Put the holders of flash cards x and y on the balance scale. If the holder of flash card x weighs more than the holder of flash card y, have them swap cards.
After the nine weighings in the list, have them line up in the order of the cards that they hold.
answered Sep 2 at 11:11
TonyK
38.7k348127
1
TonyK thank you for your reply. Can you possibly explain in a simpler way? I didn't quite understand your method and, most importantly, why this gives the minimum number of weighings.
– Chen Aavaz
Sep 3 at 8:01
@ChenAavaz: I suggest you google Bose-Nelson for more information.
– TonyK
Sep 3 at 11:21
1
@TonyK I don't think this is the proper way to reply! I don't understand either - maybe a couple of hints would be more useful than asking us to do a research on google. Btw I did already and didn't find any clear reference, so that someone can understand! Thanking you in advance.
– Jason
Sep 3 at 13:03
1
@TonyK: So in practical terms, who do we weight against whom, and how do we proceed basis each result?
– Creton Laplace
Sep 3 at 13:06
@CretonLaplace: the answer gives that. You could think of them all being in line and the first step is to weigh the first two and put them back with the lighter first. Then you weigh the fourth and fifth people and put them back in order. In the third step you weigh the middle person against the one who is now last and so on.
– Ross Millikan
Sep 3 at 14:44
 |Â
show 1 more comment
up vote
1
down vote
up vote
1
down vote
Edited to add:
The algorithm presented in this answer is not optimal, as @awkward points out in a comment to the OP. There is a faster method, due to H. B. DeMuth, that requires only seven comparisons.
The algorithm given below is the best you can do if your sequence of comparisons has to be specified in advance.
John M. Gamble's Sorting Networks is the place to go when you want to sort a small list with the fewest comparisons. Selecting N=5 gives you this list of nine weighings to perform:
SWAP(0, 1);
SWAP(3, 4);
SWAP(2, 4);
SWAP(2, 3);
SWAP(0, 3);
SWAP(0, 2);
SWAP(1, 4);
SWAP(1, 3);
SWAP(1, 2);
Here, SWAP(x,y) means "Swap x and y if x weighs more than y."
Note that you can't just replace $0$ with $A$, $1$ with $B$ etc, because the numbers refer to positions in the list, not to people. So what you do is this:
Make five flash cards, with the numbers $0,1,2,3,4$ written on them. Give everybody a card. Then SWAP(x,y) means:
Put the holders of flash cards x and y on the balance scale. If the holder of flash card x weighs more than the holder of flash card y, have them swap cards.
After the nine weighings in the list, have them line up in the order of the cards that they hold.
answered Sep 2 at 11:11
TonyK
38.7k348127
Edited to add:
The algorithm presented in this answer is not optimal, as @awkward points out in a comment to the OP. There is a faster method, due to H. B. DeMuth, that requires only seven comparisons.
The algorithm given below is the best you can do if your sequence of comparisons has to be specified in advance.
John M. Gamble's Sorting Networks is the place to go when you want to sort a small list with the fewest comparisons. Selecting N=5 gives you this list of nine weighings to perform:
SWAP(0, 1);
SWAP(3, 4);
SWAP(2, 4);
SWAP(2, 3);
SWAP(0, 3);
SWAP(0, 2);
SWAP(1, 4);
SWAP(1, 3);
SWAP(1, 2);
Here, SWAP(x,y) means "Swap x and y if x weighs more than y."
Note that you can't just replace $0$ with $A$, $1$ with $B$ etc, because the numbers refer to positions in the list, not to people. So what you do is this:
Make five flash cards, with the numbers $0,1,2,3,4$ written on them. Give everybody a card. Then SWAP(x,y) means:
Put the holders of flash cards x and y on the balance scale. If the holder of flash card x weighs more than the holder of flash card y, have them swap cards.
After the nine weighings in the list, have them line up in the order of the cards that they hold.
answered Sep 2 at 11:11
TonyK
38.7k348127
edited Sep 12 at 12:59
answered Sep 2 at 11:11
TonyK
38.7k348127
answered Sep 2 at 11:11
TonyK
38.7k348127
answered Sep 2 at 11:11
TonyK
38.7k348127
38.7k348127
1
TonyK thank you for your reply. Can you possibly explain in a simpler way? I didn't quite understand your method and, most importantly, why this gives the minimum number of weighings.
– Chen Aavaz
Sep 3 at 8:01
@ChenAavaz: I suggest you google Bose-Nelson for more information.
– TonyK
Sep 3 at 11:21
1
@TonyK I don't think this is the proper way to reply! I don't understand either - maybe a couple of hints would be more useful than asking us to do a research on google. Btw I did already and didn't find any clear reference, so that someone can understand! Thanking you in advance.
– Jason
Sep 3 at 13:03
1
@TonyK: So in practical terms, who do we weight against whom, and how do we proceed basis each result?
– Creton Laplace
Sep 3 at 13:06
@CretonLaplace: the answer gives that. You could think of them all being in line and the first step is to weigh the first two and put them back with the lighter first. Then you weigh the fourth and fifth people and put them back in order. In the third step you weigh the middle person against the one who is now last and so on.
– Ross Millikan
Sep 3 at 14:44
 |Â
show 1 more comment
1
TonyK thank you for your reply. Can you possibly explain in a simpler way? I didn't quite understand your method and, most importantly, why this gives the minimum number of weighings.
– Chen Aavaz
Sep 3 at 8:01
@ChenAavaz: I suggest you google Bose-Nelson for more information.
– TonyK
Sep 3 at 11:21
1
@TonyK I don't think this is the proper way to reply! I don't understand either - maybe a couple of hints would be more useful than asking us to do a research on google. Btw I did already and didn't find any clear reference, so that someone can understand! Thanking you in advance.
– Jason
Sep 3 at 13:03
1
@TonyK: So in practical terms, who do we weight against whom, and how do we proceed basis each result?
– Creton Laplace
Sep 3 at 13:06
@CretonLaplace: the answer gives that. You could think of them all being in line and the first step is to weigh the first two and put them back with the lighter first. Then you weigh the fourth and fifth people and put them back in order. In the third step you weigh the middle person against the one who is now last and so on.
– Ross Millikan
Sep 3 at 14:44
1
1
TonyK thank you for your reply. Can you possibly explain in a simpler way? I didn't quite understand your method and, most importantly, why this gives the minimum number of weighings.
– Chen Aavaz
Sep 3 at 8:01
TonyK thank you for your reply. Can you possibly explain in a simpler way? I didn't quite understand your method and, most importantly, why this gives the minimum number of weighings.
– Chen Aavaz
Sep 3 at 8:01
@ChenAavaz: I suggest you google Bose-Nelson for more information.
– TonyK
Sep 3 at 11:21
@ChenAavaz: I suggest you google Bose-Nelson for more information.
– TonyK
Sep 3 at 11:21
1
1
@TonyK I don't think this is the proper way to reply! I don't understand either - maybe a couple of hints would be more useful than asking us to do a research on google. Btw I did already and didn't find any clear reference, so that someone can understand! Thanking you in advance.
– Jason
Sep 3 at 13:03
@TonyK I don't think this is the proper way to reply! I don't understand either - maybe a couple of hints would be more useful than asking us to do a research on google. Btw I did already and didn't find any clear reference, so that someone can understand! Thanking you in advance.
– Jason
Sep 3 at 13:03
1
1
@TonyK: So in practical terms, who do we weight against whom, and how do we proceed basis each result?
– Creton Laplace
Sep 3 at 13:06
@TonyK: So in practical terms, who do we weight against whom, and how do we proceed basis each result?
– Creton Laplace
Sep 3 at 13:06
@CretonLaplace: the answer gives that. You could think of them all being in line and the first step is to weigh the first two and put them back with the lighter first. Then you weigh the fourth and fifth people and put them back in order. In the third step you weigh the middle person against the one who is now last and so on.
– Ross Millikan
Sep 3 at 14:44
@CretonLaplace: the answer gives that. You could think of them all being in line and the first step is to weigh the first two and put them back with the lighter first. Then you weigh the fourth and fifth people and put them back in order. In the third step you weigh the middle person against the one who is now last and so on.
– Ross Millikan
Sep 3 at 14:44
 |Â
show 1 more comment
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2902577%2friver-crossing-with-boat%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
What you're looking for is a sorting algorithm.
– Arthur
Sep 2 at 10:40
Donald Knuth, "The Art of Computer Programming, Vol. 3, Sorting and Searching", section 5.3.1, shows that the minimum number of comparisons is 7. He attributes the method to H. B. Demuth, Ph.D. thesis, Stanford University, Oct. 1956.
– awkward
Sep 2 at 12:42
Since we often have real river crossing problems here I suggest a different title.
– Christian Blatter
Sep 2 at 15:50
@awkward: I am a bit confused. The document you suggest ("The Art of Computer Programming, Vol. 3, Sorting and Searching"), gives a solution in 7 weighings, whereas TonyK solution needs 9. Which one is correct?
– Preechapak Tekasuk
Sep 3 at 18:05
@PreechapakTekasuk If Knuth says he can do it in 7 comparisons, I am inclined to believe him. $7 < 9$.
– awkward
Sep 3 at 18:35