The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » Math Topics » discretemath

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: a gift exchange
Replies: 6   Last Post: Aug 10, 2013 11:20 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Vladimir Zajic

Posts: 319
Registered: 12/3/04
Re: a gift exchange
Posted: Nov 26, 2004 2:28 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.

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 - 1-st level
(n-1) braches from each 1-st level node - 2-nd level
(n-2) braches from each 2-nd level node - 3-rd level
2 branches from each (n-2)-nd level node - (n-1)-st level
1 branch from each (n-1)-st level node - n-th 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 k-th 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 n-th 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 +-


Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.