Best Answer Prime, 07 November 2013 - 08:48 AM

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account. As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends. Of course, you can also enjoy our collection of amazing optical illusions and cool math games. If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top. If you have a website, we would appreciate a little link to BrainDen. Thanks and enjoy the Den :-) |

Guest Message by DevFuse

Started by BMAD, Nov 04 2013 06:36 PM

Best Answer Prime, 07 November 2013 - 08:48 AM

Spoiler for I see the probability for equal speed as

Go to the full post
20 replies to this topic

Posted 04 November 2013 - 06:36 PM

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?

Posted 05 November 2013 - 09:59 PM

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

Spoiler for

**Edited by dgreening, 05 November 2013 - 09:59 PM.**

Posted 06 November 2013 - 01:53 AM

Spoiler for Equal speed case

**Edited by mmiguel, 06 November 2013 - 01:55 AM.**

Posted 06 November 2013 - 02:08 AM

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

Spoiler for 3x speed case

**Edited by mmiguel, 06 November 2013 - 02:16 AM.**

Posted 06 November 2013 - 02:21 AM

Spoiler for that's why

Posted 06 November 2013 - 02:32 AM

Spoiler for oh yeah

Posted 06 November 2013 - 06:37 PM

Spoiler for Equal speed case

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.

Posted 06 November 2013 - 09:57 PM

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.**

Posted 07 November 2013 - 08:48 AM Best Answer

Spoiler for I see the probability for equal speed as

Past prime, actually.

Posted 12 November 2013 - 07:41 PM

Spoiler for I see the probability for equal speed as

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

Spoiler for

**Nicely done!**

0 members, 0 guests, 0 anonymous users