# New Moon

#### absoluzation

As every new moon, the elves Yann and Max are appointed for a night walk and a subsequent puzzling night. Both elves live on the (almost infinitely) long and totally straight Christmas Street. Since they live two miles apart, they usually leave an hour before their appointed meeting time and walk one mile towards each other. After one hour, they meet in the middle of their houses (you wouldn't be faster on these little elf legs).

Today, they also leave their houses at exactly the same time. But, unfortunately, there has been a tropical storm (the climate change does not spare anyone), that has taken all the road signs and destroyed the information and telecommunications system.
Yann and Max can distinguish the two directions in which the road is heading; however, they do not know in which direction the other elf lives—the Christmas stress must have made them oblivious. Since it is a pitch-black night, they cannot use the sun's position for orientation. Furthermore, they cannot count on the North Star, as they already are quite near to the North Pole. Light and smoke signals are not a possibility either, since Yann and Max are not to disturb they neighbours on Christmas Street—in short, they cannot communicate with each other...

1. Each elf tosses a fair coin to determine in which direction to go for one mile. This procedure is repeated until the elves meet.
2. First, each elf tosses a fair coin to determine in which direction to go for one mile. If they do not meet, then each elf turns and goes on for one mile. This procedure is repeated until the elves meet.
3. First, each elf tosses a fair coin to determine in which direction to go for one mile. If they do not meet, then each elf turns and goes on for two miles. This procedure is repeated until the elves meet.

Since Yann and Max are bosom buddies, they can be absolutely sure to pick the same strategy. The question remaining is, how good each strategy is.
Let
a, b and c be the average time (measured in hours) until the two elves meet if they choose strategy A, B, and C, respectively.

Which of the following statements is true? Explain why.

1. a<b<c
2. a<c<b
3. a<b=c
4. b<a<c
5. b<c<a
6. b<a=c
7. c<a<b
8. c<b<a
9. c<a=b
10. a=b=c

Does anyone know how to solve this? Please help me I used probability tree diagrams and calculated the probability the elves would meet in 3 hours as an approximation. It isn't rigorous, but and a true proof would likely involve using limits and expected value rather than using estimates.
Drawing the trees was useful for me to visualize the problem, and I suggest you do the same.

I will simply refer to probability that an elf goes east or west, and assume "turns" to mean "turn around" 180 degrees.
Denoted Elf 1 starting westmost, Elf 2 starting eastmost. Example event "EW" means Elf 1 goes East and Elf 2 goes West.
Used three hours as an estimate for each strategy

For strategy 1,
P(meet in exactly 1 hour) = P(EW) = 1/4
P(meet in exactly 2 hour) = P(EE,EW) + P(WW,EW) = 2*(1/4)(1/4) = 1/8
P(meet in exactly 3 hour) = P(EE,EE,EW) + P(EE,WW,EW) + P(WW,EE,EW) + P(WW,WW,EW) = 4*(1/4)^3 = 4/64 = 1/16

P(meet less than 3 hours) = 28/64
We note that if there's event WE in this strategy, elves must go EW twice before going WE once (distance increases between them by 2mi)

For strategy 2, we note this strategy equalizes the WE event and the distance between the elves afterward remains 2mi.

P(meet in exactly 1 hour) = P(EW) = 1/4
P(meet in exactly 2 hour) = P(EE,EW) + P(WW,EW) + P(WE,EW) = 3*(1/4)(1/4) = 3/16
P(meet in exactly 3 hour) = P(EE,EE,EW) + P(EE,WW,EW) + P(EE, WE,EW) + ... (there are 9 nodes at this level) = 9*(1/4)^3 = 9/64

P(meet less than 3 hours) = 37/64

For strategy 3, we note that EW or WE involves the elves meeting. If the elves go in the same direction, the distance between them doesn't change, but they don't meet.

P(meet in exactly 1 hour) = P(EW) + P(WE) = 1/2
P(meet in exactly 2 hours) = P(EE,EW) + P(EE,WE) + P(WW,EW) + P(WW,WE) = 4*(1/4)(1/4) = 1/4
P(meet in exactly 3 hours) = 8*(1/4)^3 = 1/8

P(meet less than 3 hours) = 56/64