Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: a gift exchange
Posted:
Nov 26, 2004 2:28 AM


On Wed, 24 Nov 2004 22:13:53 0500 (EST), Jerry Grossman wrote: >This is all very nice but invalid for solving our problem. The >permutations in the situation given are NOT equally likely. >jerry
Yes, you are right, I missed the fact that the acceptable permutations are not equally likely. The only solution I found is the brute force approach, i.e., to construct a tree with
n braches from the root  1st level (n1) braches from each 1st level node  2nd level (n2) braches from each 2nd level node  3rd level . . . 2 branches from each (n2)nd level node  (n1)st level 1 branch from each (n1)st level node  nth level
Each node or leaf is assigned a number from 1 to n, the condition being that an acceptable number does not appear in its path from the root and the node does not have a brother with the same number. Each node on the kth level (k < n) is assigned the probability:
0, if its number is equal to k, 1/(n  k), if its number is not equal to k, but it has a brother with the number k, 1/(n  k + 1), if its number is not equal k and it does not have a brother with the number k.
Each leaf on the nth level is assigned a probability equal to the product of probabilities in its path from the root. (If a zero probability appears anywhere in its path, the leaf is assigned probability 0.)
The probabilities of all leaves must add up to 1. The desired probability is equal to the sum of probabilities of the leaves with the number n.
n = 3: P(3) = 1/4 n = 4: P(4) = 5/36 n = 5: P(5) = 19/144
For a larger n, I would have to do some programming. In any case, a simmulation with random numbers for n = 3, 4, 5 was in agreement with the above probabilities and for n = 10, I got about P(10) ~ 0.075 + 0.01.
Vladimir



