October 2026
Suppose \(n\) is a positive integer and that you have \(n\) pairs of socks. Within each pair of socks, the two socks are the same colour. Every pair has a unique colour. After doing laundry, all of the \(2n\) socks are in a laundry basket. You begin to remove socks one at a time (always choosing randomly and never replacing the socks) until you find a pair. That is, you remove socks until you remove a sock that matches a sock that has already been removed.
For positive integers \(n\) and \(k\) with \(k<2n\), we define \(P(n,k)\) to be the probability that the first \(k\) socks removed are all different colours and there is a pair among the first \(k+1\) socks that are removed. That is, \(P(n,k)\) is the probability that the first pair is found upon removing the \((k+1)\)st sock.
Compute \(P(4,k)\) for each \(k\) from \(1\) through \(7\). Some of these probabilities should equal \(0\).
Find a general formula for \(P(n,k)\) when \(k\leq n\). It might be useful later if you can find a formula that only uses addition, subtraction, multiplication, division, exponentiation, as well as factorials and binomial coefficients. Notice that the question does not ask about \(P(n,k)\) for \(k>n\). You might want to think about what happens in this case.
For a positive integer \(i\), define \(T_i\) to be the sum of the first \(i\) positive integers. For example, \(T_1=1\), \(T_2=1+2=3\), and \(T_3=1+2+3=6\). The numbers \(T_1\), \(T_2\), \(T_3\), \(T_4\), and so on, are often called the triangular numbers. You may already know that \(T_i=\dfrac{i(i+1)}{2}\) for every positive integer \(i\). If not, think about why!
Suppose \(n=T_i\) for some \(i>1\). Show that the largest value of \(P(n,k)\) is achieved when \(k=i\) and when \(k=i+1\).
Suppose \(n\) is a positive integer that is not a triangular number. This means \(n\) is strictly between \(T_i\) and \(T_{i+1}\) for some \(i\). Show that the largest value of \(P(n,k)\) is achieved when \[k=\left\lfloor\frac{1+\sqrt{8n+1}}{2}\right\rfloor.\]
For a positive integer \(n\), we call \(k\) a peak for \(n\) if \(P(n,k)\geq P(n,\ell)\) for all integers \(1\leq\ell\leq n\). Part (c) suggests that there are two peaks for \(n\) when \(n>1\) is a triangular number and that there is a unique peak when \(n\) is not a triangular number. Find a positive integer \(k\) for which there are exactly \(2026\) positive integers \(n\) with the property that \(k\) is a peak for \(n\).