# Canoes

talzamir
Posers and Puzzles 28 Sep '11 11:14
1. talzamir
Art, not a Toil
28 Sep '11 11:14
A tribe lives in a village that has a river running through the middle. To cross the river the use canoes. Whenever a person comes to the river - the chances for a person arriving is the same for each side of the river - if there is a canoe on the side she arrives from, she'll simply paddle across. Otherwise she'll holler, and someone from the otherwise paddles across and fetches her.

How likely is it that the person coming to the river needs to holler if the tribe has

a. one canoe
b. two canoes
c. three canoes?
2. wolfgang59
Mr. Wolf
30 Sep '11 08:21
Originally posted by talzamir
A tribe lives in a village that has a river running through the middle. To cross the river the use canoes. Whenever a person comes to the river - the chances for a person arriving is the same for each side of the river - if there is a canoe on the side she arrives from, she'll simply paddle across. Otherwise she'll holler, and someone from the otherwise pad ...[text shortened]... to the river needs to holler if the tribe has

a. one canoe
b. two canoes
c. three canoes?
No proof (yet) ... just a hunch

a. 50%
b. 50%
c. 50%

ðŸ˜€
3. talzamir
Art, not a Toil
30 Sep '11 19:441 edit
Right for case a of course - but if b and c were true, it would be pointless to acquire more canoes. ðŸ˜›
4. forkedknight
Defend the Universe
30 Sep '11 19:494 edits
Originally posted by talzamir
Right for case a of course - but if b and c were true, it would be pointless to acquire more canoes. ðŸ˜›
Assuming a canoe will have an equal chance of being on either side of the river due to chance of person coming to either side of river being the same.

The assumption is that the commute time is 0 (*edit* or that a person does not need to hollar if they see someone paddling across toward them).

p(n) = (1/2)^n

A: 50%
B: 25%
C: 12.5%

*edit* this also assumes the number of people wanting to cross the river is sparse (i.e. lines of people waiting to cross don't form)
5. talzamir
Art, not a Toil
30 Sep '11 22:531 edit
SOLUTION

Two canoes.
There are three possible states for the canoes to be in. Both on shore A, one on each, and both on shore B. Let the probabilities of each be p(AA), p(AB) and (BB), respectively.

When many villagers have crossed the river, there is some probability for the canoes to be in each of those three states. When many plus one villagers have come and gone, the probabilities are the same.

if p(AA), p(AB) and p(BB) are the situation after n people, the situation after n+1 people are:

p(AA) = ½p(AA) + ½p(AB)
p(AB) = ½p(AA) + ½p(BB)
p(BB) = ½p(BB) + ½p(AB)

For example, for both canoes to be on shore A after the n+1st villager they needed to be either on shore A already or on separate shores, and then the n+1st villager crossed from B to A. Solving that given p(AA) = p(AB) = p(BB) = 1/3. So, a person need to holler with a chance of one in three, not one in four.

With three canoes, the states are AAA, AAB, ABB and BBB. Making a similar system of equations gives p(AAA) = p(AAB) = p(ABB) = p(BBB) so the likelihood of needing to holler is one in four.

This is an example of the Markov chain.