Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Several Questions about Combinatrics and Probability Questions

  1. Oct 12, 2013 #1
    1) Suppose that the streets of a city are laid out in a grid with streets running north–south and east–west. Consider the following scheme for patrolling an area of 16 blocks by 16 blocks. An officer commences walking at the intersection in the center of the area. At the corner of each block the officer randomly elects to go north, south, east, or west. What is the probability that the officer will
    a. reach the boundary of the patrol area after walking the first 8 blocks?
    b. return to the starting point after walking exactly 4 blocks?

    2) How many k-digit ternary sequences (sequences of 0s, 1s, and 2s) have the total number of 0s and 1s as even number of 0s and 1 even?

    3) Find a recurrence relation for the number of regions n lines divide the plane into. Assume all lines are straight, no lines are parallel and no three lines intersect in the same point. For example: A single line divides the plane into two regions.

    How to solve these questions?
     
  2. jcsd
  3. Oct 13, 2013 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Start with looking for possible routes/sequences/... that satisfy the condition (like "reaching the boundary after 8 steps"). Then try to find a general description for all of them, and calculate the probabilities of all of them (a tree diagram can help).

    If you need a formula for n steps, look at 1, 2, 3, 4 steps to get a feeling for the problem.
     
  4. Oct 13, 2013 #3
    Is 1a (1/4)^8 * 4
    And 1b (1/4)^4 * 20

    For 3)
    I have a1 = 2, a2 = 4, a3= 5 or 7, a4=6,8 or 9
    I could not find any relationship between them.
     
  5. Oct 13, 2013 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    1a and 1b are right.

    Why or? There is a single number for each number of lines.
    That does not look right.

    I don't understand what " have the total number of 0s and 1s as even number of 0s and 1 even" means in the problem statement of (2).
     
  6. Oct 13, 2013 #5
    For a3 and a4, it depend in how you divides the planes. Then I got a different number of regions. Try it divide it and you might see what I am talking about
     
  7. Oct 13, 2013 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Did you make sure that your sketch is large enough to see all line intersections?

    I know how the image looks like and there is a single answer. If you get multiple options, can you show what you did? There has to be some error in the sketch.
     
  8. Oct 13, 2013 #7
    Thank you for your comment on the size of the sketch. I realized my mistake is it a1= 2, a2=4,a3=7, a4=11,a5=16 so an=an-1 + n?
     
  9. Oct 13, 2013 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Right.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Several Questions about Combinatrics and Probability Questions
Loading...