Rudolf Ortvay problem solving contest

width of transition i dont have a clear idea!

hmmm...no idea...not done probability yet..
neone else trying???

actually this involves P&C more than probability

i got the ans for m(n) part but this width of transition isnt clear to me

this 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)²ⁿ ways

so for atleast 1 solution ans seems to be n! X (n-1 C m-1)²ⁿ

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)²ⁿ/(r!)ⁿ ]

now, total ways of arrangement =( nCm)²ⁿ [each boy,girl can choose m frm n)

so probabiltiyP() = G(n,m)/ (nCm)²ⁿ

now for it to be 1/2

m(n) shud be chosen such that G(n,m)= (nCm)²ⁿ /2

now when n→∞ , in P( ), the terms containing r>1 can be neglected (its obvious why? )

so P() =n![n-1Cm-1 / nCm ]²ⁿ = 1/2

ie
1/2 = n!(m/n)²ⁿ

(m²/n)ⁿ = 1/2.(n!/nⁿ)

=1/(2.eⁿ) [try derivin usin limits as integration ]

m²/n=1/e.2^1/n

so

m(n) = √n/e.2^1/n ≈ √(n - ln2) /e