Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

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
 

Photo
- - - - -

Let's meet up


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

Spoiler for I see the probability for equal speed as
Go to the full post


  • Please log in to reply
20 replies to this topic

#1 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1658 posts
  • Gender:Female

Posted 04 November 2013 - 06:36 PM

grid_collision.jpg

 

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?

  • 0

#2 dgreening

dgreening

    Junior Member

  • Members
  • PipPip
  • 63 posts
  • Gender:Male
  • Location:Maryland [DC area]

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.

  • 0

#3 mmiguel

mmiguel

    Advanced Member

  • Members
  • PipPipPip
  • 134 posts
  • Gender:Not Telling

Posted 06 November 2013 - 01:53 AM

Spoiler for Equal speed case

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

  • 0

#4 mmiguel

mmiguel

    Advanced Member

  • Members
  • PipPipPip
  • 134 posts
  • Gender:Not Telling

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.

  • 0

#5 mmiguel

mmiguel

    Advanced Member

  • Members
  • PipPipPip
  • 134 posts
  • Gender:Not Telling

Posted 06 November 2013 - 02:21 AM

Spoiler for that's why

  • 0

#6 mmiguel

mmiguel

    Advanced Member

  • Members
  • PipPipPip
  • 134 posts
  • Gender:Not Telling

Posted 06 November 2013 - 02:32 AM

Spoiler for oh yeah

  • 0

#7 harey

harey

    Junior Member

  • Members
  • PipPip
  • 80 posts
  • Gender:Male

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.


  • 0

#8 dgreening

dgreening

    Junior Member

  • Members
  • PipPip
  • 63 posts
  • Gender:Male
  • Location:Maryland [DC area]

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.


  • 0

#9 Prime

Prime

    Senior Member

  • Members
  • PipPipPipPip
  • 872 posts
  • Gender:Male
  • Location:Illinois, US

Posted 07 November 2013 - 08:48 AM   Best Answer

Spoiler for I see the probability for equal speed as

  • 0

Past prime, actually.


#10 dgreening

dgreening

    Junior Member

  • Members
  • PipPip
  • 63 posts
  • Gender:Male
  • Location:Maryland [DC area]

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




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users