Let's meet up

[BMAD]

Consider an N x N grid. Denote one corner as point A, and the opposite corner as point B. George is walking from A to B, and Lennie is walking from B to A. All paths are equally likely, as long as they follow the grid and never move away from the destination. (Hence George's path can never move down or left, and Lennie's path can never move up or right.)

What is the probability that George and Lennie collide?

If George runs and thus moves three times faster than Lennie, what is the probability of collision?

[dgreening]

I do not have an answer yet, but I did some calculations that might help get this started.

For George [same applies for Lennie (in opposite directions)]:

· He must make a total of N-1 "Up" moves

· He must make a total of N-1 "Right" moves

· His total number of moves is 2N-2

· The number of combinations of moves to go from A to B is based on a binary permutation that looks like this

combinations = (2N-2)!/[(N-1)!*(N-1)!]

For:

N = 3 [3x3 a matrix] there are 6 combinations [0011, 0101, 0110, 1001, 1010, and 1100]

N = 4 there are 20 combinations

N = 5 there are 70 combinations

N = 6 there are 252 combinations

N = 7 there are 924 combinations

N = 8 there are 3432 combinations

N = 9 there are 12870 combinations

N = 10 there are 48620 combinations

Since neither man can backtrack, the collision has to occur at the halfwaFor George [same applies for Lennie (in opposite directions)]:

· He must make a total of N-1 "Up" moves

· He must make a total of N-1 "Right" moves

· His total number of moves is 2N-2

· The number of combinations of moves to go from A to B is based on a binary permutation that looks like this

combinations = (2N-2)!/[(N-1)!*(N-1)!]

For:

N = 3 [3x3 a matrix] there are 6 combinations [0011, 0101, 0110, 1001, 1010, and 1100]

N = 4 there are 20 combinations

N = 5 there are 70 combinations

N = 6 there are 252 combinations

N = 7 there are 924 combinations

N = 8 there are 3432 combinations

N = 9 there are 12870 combinations

N = 10 there are 48620 combinations

Since neither can back track the collision [if it occurs] must be at around half way along each man's path.

With a little experimentation [on much smaller grids], it looks like "collisions" seem to only occur in cells drawn along a diagonal from the other 2 corners of the square [not A or B]

They definitely collide when each man takes a path that is "kind of symmetrical" such as:

• Whenever George moves "UP", Lennie moves "Left" [as seen by an observer from above]; and
• Whenever George moves "Right", Lennie moves "Down"

There are certainly many variations that will bring each man to the same spot in the same number of moves

What I am unsure of is, how to calculate this for large numbers.

Edited November 5, 2013 by dgreening

[mmiguel]

At each move, each player has two choices (George can go up or can go right, Lennie can go down or can go left).

Consider an alternative formulation where each player has two spots, and they may choose to pile a rock in either spot to form two piles.

Each player has 2*N rocks, and a pile can only be N high.

What is the probability that George's pile is the (n-minus) mirror of Lennies?

i.e. if Lennie has one pile with x stones, and the other with y stones, what is the probability that George's corresponding piles are n-x and n-y respectively?

When this is true, this corresponds to a collision in the original problem.

In such a case, there are exactly 2*n stones altogether, and this is the only number of total stones in which a collision may occur.

Assuming both sides reach their destinations eventually, the total number of stones will go from 0 to 4*n eventually.

Therefore in all cases, the two players will cross that magical intersection of all states with 2*n total stones.

By symmetry, each must be equally likely, since we are given nothing in the problem to favor one such state over another.

Thus the answer is the number of states with 2*n stones where there is an collision divided by the total number of states with 2*n stones.

The collision states can be enumerated like:

(0,n,n,0)

(1,n-1,n-1,1)

(2,n-2,n-2,2)

...

...

(n-2,2,2,n-2)

(n-1,1,1,n-1)

(n,0,0,n)

Each is uniquely indexed by the first number in the tuple, which goes from 0 to n.

Hence there are n+1 collisoin states.

How many total 2*n states?

Assuming they travel at the same speed, each player must have the same number of stones i.e. n stones.

Well, George can divide his n stones however he pleases between the two piles: he has n independent binary decisions leading to 2^n possibilities.

Same with Lennie.

Lennie's binary decisions are independent with George's, so we have (2^n)*(2^n) = 2^(2n) possible 2*n stone states.

The answer is therefore (n+1)/(2^(2n))

Probabilities for n going from 0 to 20

0 : 1.0

1 : 0.5

2 : 0.1875

3 : 0.0625

4 : 0.01953125

5 : 0.005859375

6 : 0.001708984375

7 : 0.00048828125

8 : 0.000137329101562

9 : 3.81469726562e-05

10 : 1.04904174805e-05

11 : 2.86102294922e-06

12 : 7.7486038208e-07

13 : 2.08616256714e-07

14 : 5.58793544769e-08

15 : 1.49011611938e-08

16 : 3.95812094212e-09

17 : 1.04773789644e-09

18 : 2.76486389339e-10

19 : 7.27595761418e-11

20 : 1.90993887372e-11

Edited November 6, 2013 by mmiguel

[mmiguel]

i probably oversimplified this and don't have the right answer for the 3x case, but oh well - i'm tired

same idea, except that George has three times as many stones as Lennie.

It is still true that collisions occur only with 2*n stones, but now, George has 3/4*2*n= 3n/2 stones, whereas Lennie only has n/2 stones.

If n is odd, then there won't be any state with 2*n stones (assuming both make their move simultaneously, before we say the next state has begun).

For example, if n is 3, then there won't be a case where there are a total of 6 stones:

(G,L) will evolve like (3,1)=4stones, then (6,2)=8 stones, etc

If n is 4, though, we saw in the last example that we do reach 2*4=8 stones.

So if n is odd, the probability of collisions becomes zero... assuming collisions occur when they are sitting on the same spot in the same state, and not while transitioning between states...

The enumeration of collisions is:

(n/2,n,n/2,0)

(n/2+1,n-1,n/2-1,1)

...

(n-1,n/2+1,1,n/2-1)

(n,n/2,0,n/2)

Thus there are (n-n/2+1) = n/2+1 collision states (indexing off the first number).

Assuming George's three moves do not have to all be in the same direction, George has 3*n/2 independent binary decisions, whereas Lennie has n/2 independent binary decisions.

Thus the answer (given the assumptions above) is:

(n/2+1)/(2^(3n/2)*2^(n/2)) = (n/2+1)/(2^(2n))

The denominator is the same as before, but the numerator changes from n+1 to n/2+1

0 : 1.0

1 : 0.375

2 : 0.125

3 : 0.0390625

4 : 0.01171875

5 : 0.00341796875

6 : 0.0009765625

7 : 0.000274658203125

8 : 7.62939453125e-05

9 : 2.09808349609e-05

10 : 5.72204589844e-06

11 : 1.54972076416e-06

12 : 4.17232513428e-07

13 : 1.11758708954e-07

14 : 2.98023223877e-08

15 : 7.91624188423e-09

16 : 2.09547579288e-09

17 : 5.52972778678e-10

18 : 1.45519152284e-10

19 : 3.81987774745e-11

20 : 1.00044417195e-11

If transitioning results in an allowable collision, then let n be odd, and just plug it into the formula (like above).

Edited November 6, 2013 by mmiguel

[mmiguel]

i never imposed the limit that you can have at most n stones in a pile....

so it's not purely an unlimited number of binary decisions...

won't worry about fixing it now... off to sleep

[mmiguel]

also... my denominator's are ordered (i.e. left, up is different than up left), but the pile analogy is not - both cases are (1,1).

doh!

[harey]

What is the probability that George's pile is the (n-minus) mirror of Lennies?

They can follow other than mirror paths to meet at the same point.

If they meet, they meet at the diagonal. The probability (for each one) to get to a particular point on the diagonal is:

Pascal's triangle/(2 power n).

I hope someone finds a formula for the product.

[dgreening]

Harey is absolutely correct.

I started playing with some small values of n to get some sense for the problem.

It turns out that the chances of hitting an particular square along that diagonal looks like "binary normal distribution" [i am sure there is a better description for this]

Of all the possible paths available. The only way to get to one of the corners of the diagonal row [for corners that are not A or B] and that is to choose all of one type of turn [up, up, up ..., up]. So if that route was chosen, the odds of colliding are very low.

Moving inward from the corners. the only ways to get to the next 2 spots is to use the same sequence as above, but replace an "up" with a "right".

and so on

Consider the 3x3 grid. There are 6 possible paths.

• 2 of them [1100 and 0011] will take you to the 2 diagonal corners
• 4 of the [1001, 1010, 0110, 0101] will take you to the center square
• so distribution [of ways to get to that spot] along the diagonal will be 1, 4, 1
• in this case there is a pretty good chance of colliding on the center spot

Now consider a 4x4. There are 20 combinations.

• The diagonal is now 4 squares long
• 2 of the [111000] and [000111] end up at the corners
• 9 sequences will end up at the "middle" square on the top left
• 9 sequences will end up at the "middle" square on the lower right
• Thus the distribution will be 1, 9, 9, 1
• In this case the 2 players could pass each other on the adjacent squares and the likelihood of collision would be much lower.
• I would guess that cases where N is an even number will have a lower probability than adjacent odd numbers.

[Prime]

In the example of 8x8 grid, and equal speeds George and Lennie must each make 7 steps before they can collide. The probability of collision would be as following:

((₇C₀)² + (₇C₁)² + (₇C₂)² + (₇C₃)² + (₇C₄)² + (₇C₅)² + (₇C₆)² + (₇C₇)²)/2¹⁴ ~ 0.21

Where ₇C₀ are all paths, where George moves only to the right and Lennie only down (just one path like that for each). The ₇C₁ represents the number of paths where George moves 1 step up and 6 steps to the right, which should be multiplied by the same number of paths for Lennie, where he moves 1 square to the left and 6 squares down. Etc..

2¹⁴ represents all possible combinations of 7-step paths between the two travelers.

[dgreening]

In the example of 8x8 grid, and equal speeds George and Lennie must each make 7 steps before they can collide. The probability of collision would be as following:

((₇C₀)² + (₇C₁)² + (₇C₂)² + (₇C₃)² + (₇C₄)² + (₇C₅)² + (₇C₆)² + (₇C₇)²)/2¹⁴ ~ 0.21

Where ₇C₀ are all paths, where George moves only to the right and Lennie only down (just one path like that for each). The ₇C₁ represents the number of paths where George moves 1 step up and 6 steps to the right, which should be multiplied by the same number of paths for Lennie, where he moves 1 square to the left and 6 squares down. Etc..

2¹⁴ represents all possible combinations of 7-step paths between the two travelers.

I think you are on the right track. I like your analysis.

I trying to come up with a nice way to calculate the number of possible paths that end up at a particular cell on the diagonal. [

₇C_x ]. I was calculating the number of paths from A to each point on the diagonal and then, as you did, square them [since George and Lennie have equal probabilities of reaching the same squares. I did not come up with your 2¹⁴ term - very elegant!

Nicely done!

[dgreening]

Thoughts on the 3x case

Since George is moving at 3 times the speed, the possible locations to meet will be a diagonal parallel to the diagonal where they meet but close to B. For this reason, there will be fewer possible points of collision and you would expect the probability to go up.

BUT! Since George moves 3 spaces for every space that Lennie moves, there is a good chance that George will run past Lennie in a single move.

I suspect that there are certain values of N where no collision is possible - but I haven't worked through the details.

Edited November 12, 2013 by dgreening

[Prime]

To solve an unequal speed case, I feel a need for some disambiguation of the OP.

1). Moving 3 times faster does not mean moving in 3-square straight segments at a time. George still can zigzag in 1-squre steps.

2). Collision occurs whenever George and Lennie are found anywhere inside the same square at the same time.

While there may be a general formula for NxN grid and variable speed ratio, I’d rather demonstrate a solution using an example of 8x8 grid and George moving 3 times faster than Lennie. That should show a kind of algorithmic general solution.

Together George and Lennie must traverse 14 squares at the combined speed of 4 times that of Lennie’s before they collide. 14/4 = 3.5. Thus, at the time of a collision, Lennie will be stepping into his 4th square, which will be the 10th square for George.
In this scenario there is a total of L = 2⁴ = 16 possible paths for Lennie. However, not that simple for George. While making a total of 10 1-square steps, he is limited to just 7 in one direction. Thus George’s number of all possible 10-square paths is: G = ₁₀C₃ + ₁₀C₄ + ₁₀C₅ + ₁₀C₆ + ₁₀C₇ = 912.
The number of colliding paths is: C = ₄C₀*₁₀C₃ + ₄C₁*₁₀C₄ + ₄C₂*₁₀C₅ + ₄C₃*₁₀C₆ + ₄C₄*₁₀C₇ = 3432. Where ₄C₀*₁₀C₃ is the number of path combinations when Lennie moves straight down and George moves 7 squares to the right and 3 squares up, etc..
And the final probability is P = C/(L*G) ~ 0.2352.

[bonanova]

I suspect John Steinbeck and Robert Burns are lurking somewhere nearby.

Since OP refers to A and B as points rather than cells, I see George and Lenny traveling on the lines,

as if the lines are paths, and meeting, if they do, on any of the nine points on the major diagonal.

One can enumerate the number of paths to each point on the grid from the nearer of A and B.

The edge points all receive a 1, since they each terminate precisely one route.

Numbers on other points are then the sum of the two numbers immediately upstream.

This constructs Pascal's Triangle and places the binomial coefficients of increasing order on the diagonals.

In particular, the number of paths from A or B to the points on the major diagonal are:

1 8 28 56 70 56 28 8 and 1.

These numbers sum to 2⁸ = 256, as they should, since each path is a unique set of 8 binary decisions.

The probability of reaching a particular point on the major diagonal is the number on that point divided by 256.

The probability of meeting, as many have pointed out, is the sum of the squares of the individual probabilities. Thus,

p(meet) = (1+64+784+3136+4900+3136+784+64+1) / 256² = 12870 / 65536 ~ 0.1963...

If George and Lenny travel from cell to cell, then there are 7 decisions for each path, and in that case

p(meet) = ( 1 + 49+441+1225+1225+441+49+1) / 128² = 3387 / 16384 ~ 0.2067...

The problem variation has a speed ratio of 3:1.

Analysis now is impossible unless George and Lenny combined take 16 steps, on lines, -- 12 and 4 in this case.

Now the possible meeting locations are the points on the 4th diagonal from the slower runner's corner.

The probabilities of the slower person reaching these points are {1 4 6 4 1} / 16.

The probabilities of the faster person reaching these points is found by continuing Pascal's triangle to the 12th level.
Retaining only the five central values, these probabilities are seen to be {495 666 672 666 495} / 2994.

The pairwise products are 495 2664 4032 2664 495, and the meeting-probability denominator is 16 x 2994. Thus,

p(meet) = (495+2664+4032+2664+495) / 16 x 2994 = 10352 / 47904 ~ 0.216098...

Interestingly, this is only slightly higher than meeting at equal speed on the major diagonal.

Does George shoot Lenny only if they meet?

[Prime]

I suspect John Steinbeck and Robert Burns are lurking somewhere nearby.

Since OP refers to A and B as points rather than cells, I see George and Lenny traveling on the lines,

as if the lines are paths, and meeting, if they do, on any of the nine points on the major diagonal.

One can enumerate the number of paths to each point on the grid from the nearer of A and B.

The edge points all receive a 1, since they each terminate precisely one route.

Numbers on other points are then the sum of the two numbers immediately upstream.

This constructs Pascal's Triangle and places the binomial coefficients of increasing order on the diagonals.

In particular, the number of paths from A or B to the points on the major diagonal are:

1 8 28 56 70 56 28 8 and 1.

These numbers sum to 2⁸ = 256, as they should, since each path is a unique set of 8 binary decisions.

The probability of reaching a particular point on the major diagonal is the number on that point divided by 256.

The probability of meeting, as many have pointed out, is the sum of the squares of the individual probabilities. Thus,

p(meet) = (1+64+784+3136+4900+3136+784+64+1) / 256² = 12870 / 65536 ~ 0.1963...

If George and Lenny travel from cell to cell, then there are 7 decisions for each path, and in that case

p(meet) = ( 1 + 49+441+1225+1225+441+49+1) / 128² = 3387 / 16384 ~ 0.2067...

The problem variation has a speed ratio of 3:1.

Analysis now is impossible unless George and Lenny combined take 16 steps, on lines, -- 12 and 4 in this case.

Now the possible meeting locations are the points on the 4th diagonal from the slower runner's corner.

The probabilities of the slower person reaching these points are {1 4 6 4 1} / 16.

The probabilities of the faster person reaching these points is found by continuing Pascal's triangle to the 12th level.

Retaining only the five central values, these probabilities are seen to be {495 666 672 666 495} / 2994.

The pairwise products are 495 2664 4032 2664 495, and the meeting-probability denominator is 16 x 2994. Thus,

p(meet) = (495+2664+4032+2664+495) / 16 x 2994 = 10352 / 47904 ~ 0.216098...

Interestingly, this is only slightly higher than meeting at equal speed on the major diagonal.

Does George shoot Lenny only if they meet?

The corners of the board are dots. George and Lennie have square bottoms exactly equal in size to a board square. They move from one square to another by sliding in a straight line until the entire square is covered with their bottom. This way whenever they are moving into the same square, the collision is unavoidable.

I concentrate on paths, rather than individual squares or points on the board. Seems easier that way.

If George moves a total of 4 squares to the right and 3 squares up he is going to end up in the same square regardless of the order, in which he took those steps. The number of possible paths (different orders of steps) in this case is ₇C₃.

Notably, Pascal’s triangle consists of Combination formulas, which add up to the corresponding power of 2. E.g., the Pascal triangle line (1, 8, 28, 56, 70, 56, 28, 8, 1) actually is (₈C₀, ₈C₁, ₈C₂,...,₈C₈). And it adds up to the 2⁸.

[BMAD]

Does George shoot Lenny only if they meet?

depends on the quality of the gun.

[bonanova]

Does George shoot Lenny only if they meet?

depends on the quality of the gun.

Were the names not taken from "Of Mice and Men"?

[BMAD]

Yes. I saw the movie on cable recently. Read the book many years ago.

[BMAD]

I was referring to quality in the sense that they were poor and in the 1930's, and though i don't know my guns that well, assume that they may not have had the best access to a quality gun especially since they were broke.

[bonanova]

My son teaches HS English and suggested that I forced me to read the book.

I have indelible images of George and Lenny, ones that seeing the movie did not erase.

BTW, which grid were you inquiring about? The 8x8 moves, or 7x7 moves?

The 8x8-move case actually appeared here a while back, so I already had the solution.

I wasn't going to post it until I saw that no one else did.

[BMAD]

I actually wanted an N x N grid but since the picture specifically references a grid, i just let the group go with that.

[bonanova]

I actually wanted an N x N grid but since the picture specifically references a grid, i just let the group go with that.

I think the first part has been suggested for any N.

But inserting the 3:1 condition is difficult when N is odd.

Perhaps a general solution exists for a 2p x 2p grid.

I'll think about that one.