Expert: Paul Klarreich - 5/11/2007

Question
QUESTION: Probability Theory

I'm having difficulty with these two problems:
1) A gardener plants 3 maple trees, four oak trees and five birch trees in a
row. He plants them in random order, each arrangment being equally likely.
Find the probability that no two birch trees are next to one another.  (I think I
have to use the balls and urns solution but I'm having difficulty in execution)

2)A random generator randomly generates the integers 1,2,...,9 with equal
probability. Find the probability that after n numbers are generated, the
product is a multiple of 10. (This is for Inclusion and Exlusion but the
problem here is I don't know how to group them)

ANSWER: Questioner:   Seth
Category:  Advanced Math
 
Subject:  Probability Questions
Question:  Probability Theory

I'm having difficulty with these two problems:
1) A gardener plants 3 maple trees, four oak trees and five birch trees in a row. He plants them in random order, each arrangment being equally likely.  Find the probability that no two birch trees are next to one another.  (I think I have to use the balls and urns solution but I'm having difficulty in execution)

2)A random generator randomly generates the integers 1,2,...,9 with equal probability. Find the probability that after n numbers are generated, the product is a multiple of 10. (This is for Inclusion and Exlusion but the problem here is I don't know how to group them)
........................................
Hi, Seth,

These are not easy, and I am not totally confident of these analyses, but most questioners are in a hurry, so here goes:

1) The trees:

Arrange the 5 birch trees in a (wide) row and put a box in between each pair of trees and one at each end.  That will be 6 boxes.

Let box 'n' contain the trees to the right of birch tree n, and  n = 0..5, although the birch trees are numbered only 1..5.

Each of the boxes  1..4 must be nonempty.  So for each of the 7 non-oaks, we have to choose a number from 0..5.  There are 6^7 possibilities for this.

Suppose that box 1 is indeed empty.  Then we have chosen 7 numbers that are from  0,2,3,4,5.  There are 5^7 ways to do this.

Same for boxes 2,3,4.  So the number of failures (two oaks together) is  4*5^7.  Then the number of successes is  6^7 - 4*5^7 and the probability is:

6^7 - 4*5^7
-----------
   6^7

= 1 - 4(5/6)^7
.............................
2) The random integers.

You will get a multiple of 10 if the set of numbers contains at least one 5 and at least one even integer.  You will NOT get a multiple of 10 if the numbers are taken:

A. only from odd integers.  There are 5 of these, and there are  5^n sequences possible.

B. from any integers without 5.  There are 8 of these -- 1,2,3,4,6,7,8,9 -- and there are 8^n sequences possible.

Now we want the union of those two sets.  They are not disjoint.  We have to subtract off their intersection.  That would be  sequences from odd integers not including 5:  There are 4 of these: 1,3,7,9, so there are 4^n such sequences.

The total number in that union is:  5^n + 8^n - 4^n

There are 9^n total sequences possible.  The probability of NOT getting a multiple of 10 is:
5^n + 8^n - 4^n
---------------
    9^n

and the probability of getting a multiple of 10 is  1 - that.

Check:  Try  n = 2:

5^2 + 8^2 - 4^2 = 25 + 64 - 16 = 73

73/81 don't have a multiple of 10.  So 8 do and they would be:

2,5
4,5
6,5
8,5
and their reverses.


---------- FOLLOW-UP ----------

QUESTION: Same for boxes 2,3,4.  So the number of failures (two oaks together)
is  4*5^7.  Then the number of successes is  6^7 - 4*5^7 and the probability
is:

6^7 - 4*5^7
-----------
   6^7

= 1 - 4(5/6)^7

Just a clarification...so the answer will be negative? 6^7 < 4*5^7

Answer
Hi, Seth,

You are indeed correct.  Perhaps I was in too much of a hurry to get you an answer and didn't check the arithmetic.

I see where my analysis of the 'tree' problem was flawed -- a 'failure' (meaning two birches together) could be a result of two or more zeroes in the middle boxes, and I did not allow for that.

I will think about it some more and see if I can send another followup.  Sorry for the carelessness and thank you for pointing it out.