[bonanova]

Imagine an oversize chessboard.

Let the borders of the squares be pathways.

So there are nine [not 8] N-S and nine E-W paths, making 81 intersections [4 corners, 28 Ts and 49 4-ways].

I'm standing on the SW corner; you're standing on the NE corner.

We start walking toward each other's corner.

I walk only in a N or E direction; you walk only in a S or W direction.

Assume we start at the same time and walk at equal speeds. What is the probability we will meet?

OK, that was easy. Suppose I walk 3 times faster than you. Now what's the probability that we will meet?

Remember, we walk on the EDGES of the 8x8 squares, not ON them.

[Yoruichi-san]

Seems like...

Since they have to move each "turn", then they will always be an equal amount of line segments away from their respective starting point and therefore can only meet at those points which are equal # of line segments from both starting points. They each need to take a total of 16 moves to get to the end point, so if they meet, they must meet when each has taken 8 moves. There are 9 points which are 8 line segments from both corner; these form a diagonal going from SE to NW. The probability of meeting then is the probability of both ppl being at the same point after 8 moves, and due to the symmetry of the problem, the probability for each point is equal for both ppl.

Each move, each person has two choices, for bonanova, North or East, so for n moves there are a total of 2^n options. The probability of each point then is the probability of taking the number of North and the number of East moves that it would take to get to that point. I.e., for the point that is 3 N and 5 E from bonanova's starting point, the probability is 8Cr3/2^8=8Cr5/2^8. I square each of these and take the sum, and if my math was correct, the answer is: (6435/32768)=.196381

Edit: Working on the other part...seems to follow from the first part...but I could be wrong...

Edited December 14, 2008 by Yoruichi-san

[Yoruichi-san]

Okay...for the second part...

Since together they move effectively 4 segments each turn, they'll need to meet in 4 turns, bonanova will have taken 12 moves and the other person will have taken 4. There are 5 spots a distance 4 moves away from the other person, again in a diagonal, and I figure out the probability of each in a similar fashion to above. Then I calculate the probability of each of these spots for bonanova by calculating the non-edge spots first, which require a specific # of N moves and E moves out of the 12 total moves, i.e. 5N and 7E is 12Cr5/2^12=12Cr7/2^12. Taking into account the fact that once bonanova reaches an opposing edge, he no longer has a choice of how to move, then the remainder when the probability of these spots is subtracted from 1 should be the sum of the probability of the two points that are on edges, and due to symmetry, each point accounts for half this probability. So, multiplying the probability that bonanova will be at a particular point with the probability the other person will also be on that spot, the answer, again if my math is correct, is: 3367/16384=.205505

Edit: Clarification

Edited December 14, 2008 by Yoruichi-san

[Prime]

I calculated same as Y-s probability for the first case, and different one for the second case.

Case1.

Like Y-s noted Bonanova and I meet on the NW-SE diagonal having made the same number of steps. Total number of all possible paths is 2⁸*2⁸=2¹⁶.

When I walk to a potential meeting point, I make 8 steps. At any given intersection I can choose to move South. Each point on the diagonal may be represented by how many times (up to 8) I chose to move South. So, to the point on the diagonal, which is n squares South and 8 - n squares West, there are ₈C_n paths, that is 8!/(n!(8-n)!.

Thus to the NW point of the board there are ₈C₀=1 paths, for example. And my probability to end up there is 1/2⁸. Probability to meet at a particular point is my probability to get there time Bonanova's probability (which is the same). And the overall probability is the sum of probabilities of all potential meeting points: ((₈C₀)²+(₈C₁)²+(₈C₂)²+(₈C₃)²+(₈C₄)²+(₈C₅)²+(₈C₆)²+(₈C₇)²+(₈C₈)²)/2¹⁶ ~ 0.196381

Case2.

Moving 3 times slower, I can walk 4 square lengths, while Bonanova walks 12. So if you draw a 4x4 square from my starting point, we could meet on that diagonal. (Note, both Bonanova and I will necessarily end up on one of the points of that diagonal). For me the probability of each point n squares to the South is ₄C_n. For Bonanova, each point on that diagonal is from 8 to 4 square lengths to the North. He can take ₁₂C_n different paths to each of those points, where n is number of steps to the North.

The total number of paths for Bonanova is ₁₂C₈+₁₂C₇+₁₂C₆+₁₂C₅+₁₂C₄=3498. The total number of paths for me is 2⁴=16. The overall total paths: 3498*16=55968.

The sum for meeting possibilities for all points is: ₁₂C₈*₄C₀+₁₂C₇*₄C₁+₁₂C₆*₄C₂+₁₂C₅*₄C₃+₁₂C₄*₄C₄=12870.

And the probability of the meeting is 12879/55968 ~ 0.229953

Or am I missing a simpler solution?

Edited December 14, 2008 by Prime

[Guest]

Also 9 endpoints each with its own likelyhood.

2^8 (2 types of decisions to make, 8 times) but the likelyhood ranges from 1 to 70 times (corner to center).

You are 70 times more likely to land in the center if you take a random path than one of the corners.

( 8C4 / 2^8 )^2 + 2 * ( 8C3 / 2^8 )^2 + 2 * ( 8C2 / 2^8 )^2 + 2 * ( 8 / 2^8 )^2 + 2 * ( 1 / 2^8 )^2 = 0.196380615234375

I confirm results on case 1.

Edited December 15, 2008 by bonanova
add spoiler

[Guest]

Sorry I forgot to add the spoiler to the earlier answer.

5 possible endpoints and from either side the likelihood of ending up at each endpoint is at a ratio of 1 : 4 : 6 : 4 : 1.

And I don't even think we need to consider the faster moving person because he is not the "limiting reagent".

Faster moving guy may have more options of paths but he will also have more combinations to the same endpoints.

So, I think the ratios of combinations to permutations are still going to be 1 : 4 : 6 : 4 : 1.

2 * ( 1 / 2^4 )^2 + 2 * ( 4 / 2^4 )^2 + ( 6 / 2^4 )^2 = 0.2734375

Edited December 15, 2008 by Garrek99

[bonanova]

1. Count paths to the possible meeting points
   
2. Divide by total paths to get arrival probabilities for each traveler
   
3. Multiply arrival probabilities pairwise to get meeting probabilities at each point.
   
4. Add these to get overall meeting probability.
   

the 9 meeting points can be reached ₈C_{k [k=0-8]} = 1 8 28 56 70 56 28 8 1 ways - 256 in all - for either traveler.

Dividing by 256 gives their arrival probabilities of .004 .031 .109 .219 .273 .219 .109 .031 .004 [to 3 places]

Squaring these give the meeting probabilities as .000 .001 .012 .048 .075 .048 .012 .001 .000 [3 places]

Adding these gives the overall probability of meeting. as .196 [3 places]

Y-san, Prime and Garrek99 all got this.

there are five meeting points.

The slower traveler gets there in ₄C_{k [k=0-4]} = 1 4 6 4 1 ways, with probabilities of .063 .250 .375 .250 .063 [3 places].

The faster traveler takes 12 steps.

At least 8 of them involve choice; but if an edge is reached, the remaining steps are dictated.

At least 4 and no more than 8 steps are taken in each direction.

So the enumerable paths are, as Prime found, ₁₂C_{k [k=4-8]} = 495 792 924 792 495 - 3498 in all.

So the faster traveler's arrival probabilities are .142 .226 .264 .226 .142 [3 places].

Multiplying by the slower traveler's probabilities gives the meeting probabilities as .009 .057 .099 .057 .009 [3 places]

for a total probability of .230 [3 places]

Prime got it

Y-san gave the correct explanation apparently with a calculation error.

Garrek99 made the assumption the arrival probabilities were the same, leading to the result for a 5-path square and equal speeds.

the overall probability of meeting increases.

For speed ratios that make the meeting occur on rach of the 9 distinct diagonals,

starting with the main diagonal and moving to the corner itself, the probabilities increase as follows:

.196 .197 .201 .210 .230 .268 .341 .500 1.000 [when the slower traveler takes no steps at all].

I ran across this problem a while back, published with wrong answers.

I did the math a couple days ago and thought I'd share the fun.

[Guest]

Cool puzzle. THNX

I should have tried harder on case 2.

For Y-san: here is a nice calculator to keep you from making calculation errors.

You can enter a long string of calculations in one line and copy paste formulas and numbers and such.

http://www.dreamcalc.com/calculator_download.htm

I am not affiliated with the coder of that calculator I just thought it's really cool.