There are 100 seats assigned to 100 passengers, but each person randomly sits on any empty seat he/she chooses.
What is the probability that at least one person is now sitting in his/her assigned seat.
(Instead of 100, one can choose a smaller number, say 3 or 4 to see if there is any pattern)
If we define Q(n) as probability of no one getting their allotted seat, then the required probability is
[1 - Q(n)]
Q(1) = 0
Q(2) = 1/2
Q(n) = ((n-1)*(n-3)*(n-5)..*1)/n!
which can be expressed recursively as Q(n) = [Q(n-2)*(n-1)]/[n*(n-1)] = Q(n-2)/n
Q(n)'s numerator is the number of ways you can arrange people on seats so that everyone gets the wrong seat. every time some one picks a wrong seat, another person is going to be sitting on a wrong seat no matter what, so you can keep that guy aside, and do this problem again for the remaining n-2 people and the n-2 seats alloted to those people. This is not really a proof of correctness, just handwaving. And the probability that at least one person gets allotted seat seems rather high, which is not intuitive, which could mean the solution is wrong, of course.