Clarification of a point from discussion today

[Kevin Lin]

Today in class there was some confusion about the following problem:

Suppose we have a set of k^2 problems, and we wish to pick exactly k of them. What is the probability that the ith problem gets picked?

Here's one way to analyze this problem:

First of all, there are (k^2 choose k) possible ways to choose a subset of k problems from the set of k^2 problems. Each of these has an equal probability of happening.

To compute the probability that the ith problem gets picked, we just need to figure out how many of these k-problem subsets contain the ith problem. If we are required to choose the ith problem, then that means that we must choose k-1 problems from the remaining k^2-1 problems. Therefore there are (k^2-1 choose k-1) ways of choosing a k-problem subset containing the ith problem.

Thus, the probability that the ith problem gets picked is (k^2-1 choose k-1)/(k^2 choose k).

As we saw in class earlier, for any n and k, we have k * (n choose k) = n * (n-1 choose k-1), or in other words, we have (n-1 choose k-1) / (n choose k) = k / n.

Therefore we have (k^2-1 choose k-1)/(k^2 choose k) = k/k^2 = 1/k.

This solution seems a bit complicated to me; perhaps there's an easier way to arrive at the answer 1/k. Let me know if you guys think of something.

Kevin