Several Questions about Combinatrics and Probability Questions

[Askhwhelp]

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?

 

[mfb]

How to solve these questions?

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.

 

[Askhwhelp]

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.

 

[mfb]

1a and 1b are right.

a3= 5 or 7

Why or? There is a single number for each number of lines.

a4=6,8 or 9

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

 

[Askhwhelp]

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

 

[mfb]

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

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.

 

[Askhwhelp]

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.

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?

 

[mfb]

Right.