Recently, while reading, I came across a problem in Problem Solving Strategies: Crossing the River with Dogs by Ken Johnson and Ted Herr that I was not entirely sure how to solve. Alas, I have come here to see if my intuition is correct/see if there is an easier way to solve the problem.
The problem:
Aji has an argument with his daughter. She says, "You do the same thing every day." Aji does go fishing every day but contends that every day is different because he does things in a different order each day.
Before he leaves shore in his row boat, he gets fresh bait, checks the weather, and adjusts his seat cushion.
Out in the water, he eats his fruit, puts meat on his sandwich, drinks his apple juice, and eats his sandwich.
Back at shore, after tying his boat to the dock, he takes the fishing pole in his right hand and the ice chest in his left hand.
Then he finally heads back home to have the same argument with his daughter. For how many days could Aji do things in a different order before he has to repeat the order of some prior day? Is there any easy way he could double the number of days in his cycle?
Preword: I feel it is worth noting that order does matter in certain situations here. For example, he cannot eat his sandwich before he puts the meat on it. Moreover, he cannot leave before packing up his fishing pole and the ice chest.
I first let the things Aji must do before leaving shore be $Event A$.
The total number of ways in which he can do those three things is equal to $3!$ because he can do any of the three things first, either of two remaining things next, and the final thing, which could be anything, last.
I then let $Event B$ be the things he does out in the water.
Here, order matters in certain situations for this problem (as stated earlier). So, I divided these events into mini or sub-events that are mutually exclusive.
1) Aji eats his sandwich last.
That means he can do the other three things in any order, which equals $3! = 6$ ways.2) Aji eats his sandwich second to last.
Thus, the meat has to be put on the sandwich first or second.Number of things that can be done first: $3$
Possible number of things that can be done second: $2$
Possible number of things he can do last: $1$
Number of ways B2 can be done: $3 \times 2 = 6$
3) Aji eats his sandwich second.
This must mean that he put the meat on first.Possible things that can be done second to last: $2$
Possible things that can be done last: $1$
Number of ways B3 can be done: $2 \times 1 = 2$.
So, total number of ways B can be done: $6+6+2 = 14$
C)
Finally, I let event $C$ represent the things Aji can do after getting back to the shore.
Aji can either grab the fishing pole first or second. So, there are two ways.
Total number of ways C can be done: $2$
So, A can be done $6$ ways, B $14$ ways,and C $2$ ways.
Thus, the number of ways all of this can be done together is $n(A) \times n(B) \times n(C) = 6 \times 14 \times 2 = 168$ ways.
So, Aji could do things in a different order for $168$ days before having to repeat the order of some prior day. For the second part, you could simply intro a thing in event $A$ or $C$, which could be done first or last (i.e. Aji could put his shoes on as the first thing he does after returning to shore, or the last thing.)
Is this the right way to go at this problem? Is there perhaps an easier solution?
Thanks.
Best Answer
I agree with you on Event A; I'm not so sure about event C. And I disagree with your Event B.
For Event B: consider the case where Aji eats his sandwich second to last. You claim that there are six ways of doing this; I think there are only 4 ways: the meat must be put into the sandwich either first or second; then you have two choices of what else to do before eating the sandwich; the last thing you do is now forced. Explicitly (with m=putting meat, f=eating fruit, j=drinking juice, and s=eating sandwich) the only four things he can do are mfsj, mjsf, fmsj, and jmsf. I don't see six things.
Where is your counting error? It is true that you have three choices for the first position, but you don't have two choices for the second thing. You only have two choices for the second thing if the first things you did was putting the meat in; if you chose anything else for your first thing to do, then the second thing to do must be putting the meat in the sandwich, so you don't really have 2 choices for the second thing regardless of the third. Instead, you would have to break it up into cases: you have 2 ways of doing it if the meat happens first; and 2 ways if the meat happens second.
Here's a simpler way of doing Event B:
Since Aji must put meat in the sandwich before eating it, we know that, whethever order he does things, "put meat" goes before "eat sandwich". There are things that can happen before he puts meat in the sandwich, things that can happen after he puts meat in the sandwich but before he eats it, and things that can happen after he eats his sandwich.
So, relative to the putting-meat-and-eating-his-sandwich, there are three temporal locations for "eat his fruit" to go into:
Once we chronologically locate the fruit relative to the sandwich-eating process, what about the juice? There are now four temporal locations for the juice: any of the two temporal locations not used by the fruit; and the same temporal location as the fruit, but either before the fruit, or after the fruit. For instance, if the fruit was eaten between putting the meat and eating the sandwich, then the juice can be had before putting the meat, or after the meat but before the fruit; or after the fruit but before the sandwich; or after the sandwich.
This gives $3\times 4 = 12$ different ways of doing Event B.
As for Event C: note that the problem states that he picks up the fishing rod and the icebox after tying the vote. That means that the first thing Aji does is tie the boat. Then he can either grab the fishing rod or the icebox (two things). Then he grabs whatever is left, then he heads home. It seems to me that there are only two ways of performing event C, not six.
Added: Event C has recently been edited to give 2 ways, in which case I agree.
Your method for the second part of the question works (it doesn't have to be in Event A or C; it could be something in Event B as well). Or you can add a thing that can either be done or not, e.g., "wear or not wear a cap."