MathDB

8

Part of 2012 Korea Junior Math Olympiad

Problems(1)

n students picking n cards with numbers 1-n, probanility to have same no

Source: KJMO 2012 p8

5/4/2019
Let there be nn students, numbered 11 through nn. Let there be nn cards with numbers 11 through nn written on them. Each student picks a card from the stack, and two students are called a pair if they pick each other's number. Let the probability that there are no pairs be pnp_n. Prove that pn−pn−1=0p_n - p_{n-1}=0 if nn is odd, and prove that pn−pn−1=1(−2)kk1−kp_n - p_{n-1}= \frac{1}{(-2)^kk^{1-k}} if n=2kn = 2k.
probabilitycombinatorics