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


John
Posts:
54
Registered:
12/6/04


Re: a gift exchange
Posted:
Dec 14, 2004 9:07 PM


I can understand building a tree up to n=5, but beyond that I am lost. Can you please email me
On 26 Nov 04 02:28:48 0500 (EST), Vladimir wrote: >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



