1what does m(N) mean?? and what is "width of th transition"??
Camp for Freshmen...
N boys studying physics and N girls studying liberal arts are sitting by the flickering
campfire. Just by them are N, strictly coed tents (for two people each). Egon Quark has to arrange the sleeping order.
It is known that on the average each person is willing to sleep in one tent with m members of the other sex - but
only Egon knows who with who. How should m(N) be chosen so that Egon would have a 50% chance to arrange
a sleeping order that is satisfying for everyone? Give the asymptotic behaviour of m(N) as N → ∞.
For N fixed, define the width of the transition “Egon flunks − Egon does not flunk†(f(N)). How does f(N)
behave as N → ∞?
-
UP 0 DOWN 0 0 9
9 Answers
9actually this involves P&C more than probability
i got the ans for m(n) part but this width of transition isnt clear to me
9this is a competition where they dont release solutions to Qs
i could find only the first part
for a particular m,
let compatible mean that a particular boy and girl both are willing to sleep with each other.Egon has to find n compatible pairs now
ways of 1 compatible pair
1st boy has n choices , 2 nd boy n-1 and so on
so total ways = n X n-1 X ...... = n!
now each boy and girl is free to choose m-1 other partners from n-1 options
ie( n-1 C m-1)2n ways
so for atleast 1 solution ans seems to be n! X (n-1 C m-1)2n
but here cases where 2 compatible pairs , 3 compatible pairs have been repeated .
So using sieve formula and using above arguments for all cases we can derive
total ways were sol feasible, G(n,m) =n! [ Σ -(1)r+1 (n-r C m-r)2n/(r!)n ]
now, total ways of arrangement =( nCm)2n [each boy,girl can choose m frm n)
so probabiltiyP() = G(n,m)/ (nCm)2n
now for it to be 1/2
m(n) shud be chosen such that G(n,m)= (nCm)2n /2
now when n→∞ , in P( ), the terms containing r>1 can be neglected (its obvious why? )
so P() =n![n-1Cm-1 / nCm ]2n = 1/2
ie
1/2 = n!(m/n)2n
(m2/n)n = 1/2.(n!/nn)
=1/(2.en) [try derivin usin limits as integration ]
m2/n=1/e.21/n
so
m(n) = √n/e.21/n ≈ √(n - ln2) /e
9m(n) obtained above luks asymptotic
i believe
G(n,m) can be simplified further , but unable to proceed