October 2026
The quantity \(P(4,1)\) is the probability that there is no pair among the first sock removed and there is a pair among the first two socks removed. There can never be a pair among one sock, so \(P(4,1)\) is simply the probability that the second sock matches the first. After drawing one sock, there will be seven socks remaining and exactly one of them matches the first. Therefore, \(P(4,1)=\dfrac{1}{7}\).
The quantity \(P(4,2)\) is the probability that the first two socks are different and the third sock matches one of the first two. The probability that the first two socks are different is the probability that the second sock does not match the first sock, which is \(\dfrac{6}{7}\). If the first two socks drawn are different, then there will be six socks remaining, two of which match one of the first two. Therefore, \(P(4,2)=\dfrac{6}{7}\times\dfrac{2}{6}=\dfrac{2}{7}\).
In a similar way, we compute \(P(4,3)\) by first computing the probability that the first three socks are different. This is the probability that the first two socks are different times the probability that the third sock is different from both of the first two. From before, the probability that the first two socks are different is \(\dfrac{6}{7}\). Since two socks of the remaining six would match at least one of the first two (different) socks, the probability that the first three socks are different is \(\dfrac{6}{7}\times\dfrac{4}{6}=\dfrac{4}{7}\). After three distinct socks are drawn, there are five remaining, and three of them will make a pair. Therefore, \(P(4,3)=\dfrac{4}{7}\times\dfrac{3}{5}=\dfrac{12}{35}\).
Suppose the first four socks that were removed are all different. Then the fifth sock must match one of these first four since there are only four pairs in total. Therefore, \(P(4,4)\) is equal to the probability that the first four socks are different. Following similar reasoning to that in the previous few cases, \[P(4,4)=\frac{6}{7}\times\frac{4}{6}\times\frac{2}{5}=\frac{8}{35}.\]
Among any five of the eight socks, there must be a pair since there are only four pairs overall. Therefore, the probability that the first five, six, or seven socks are all different is equal to zero, which means \(P(4,5)=P(4,6)=P(4,7)=0\). Note that this reasoning generalizes. That is, \(P(n,k)=0\) when \(n<k<2n\).
Since a pair must eventually be found, the sum of the probabilities \(P(4,1)\) through \(P(4,7)\) should be \(1\). Indeed, \[\begin{align*} & \phantom{=} P(4,1)+P(4,2)+P(4,3)+P(4,4)+P(4,5)+P(4,6)+P(4,7) \\ &= \frac{1}{7}+\frac{2}{7}+\frac{12}{35}+\frac{8}{35}+0+0+0 \\ &= \frac{5+10+12+8}{35} \\ &= \frac{35}{35} = 1\end{align*}\]
We will give two derivations of the same formula using two different kinds of reasoning.
Using similar reasoning to that in the solution to part (a), we first compute the probability that the first \(k\leq n\) socks removed from a basket of \(2n\) socks are all different. The probability that the first two socks are different is \(\dfrac{2n-2}{2n-1}\) because after the first sock is removed, there are \(2n-1\) socks remaining in the basket, one of which matches the first sock, so the other \(2n-2\) do not match the first sock.
After two different socks are removed, there are \(2n-2\) socks remaining in the basket, two of which will match one of the first two socks. Therefore, \((2n-2)-2=2n-4\) of the remaining socks will not match either of the first two socks. This means the probability that the first three socks are different is \[\frac{2n-2}{2n-1}\times\frac{2n-4}{2n-2}.\]
After three distinct socks are removed, there are \(2n-3\) socks remaining, three of which will make a pair. Hence, \((2n-3)-3=2n-6\) socks can be drawn so that the first four socks are different. Therefore, the probability that the first four socks are different is \[\frac{2n-2}{2n-1}\times\frac{2n-4}{2n-2}\times\frac{2n-6}{2n-3}.\]
Continuing in this way, the probability that the first \(k\) socks are different is \[\begin{align*} &\frac{2n-2}{2n-1}\times\frac{2n-4}{2n-2}\times\frac{2n-6}{2n-3}\times\cdots\times\frac{2n-2(k-2)}{2n-(k-2)}\times\frac{2n-2(k-1)}{2n-(k-1)} \\ =& \frac{(2n-2)(2n-4)(2n-6)\cdots(2n-2(k-2))(2n-2(k-1))}{(2n-1)(2n-2)(2n-3)\cdots(2n-(k-2))(2n-(k-1))}\end{align*}\] and after factoring a \(2\) out of each term in the numerator, this is equal to \[\frac{2^{k-1}(n-1)(n-2)(n-3)\cdots(n-k+2)(n-k+1)}{(2n-1)(2n-2)(2n-3)\cdots(2n-k+2)(2n-k+1)}.\] It may not be obvious how to interpret the formula above when \(k=1\), or even when \(k=2\). You may want to think about this now, but some explanation is given after the simplification that follows. In order to tidy up this expression, we will multiply by \(1\) in the forms \(\dfrac{(n-k)!}{(n-k)!}\), \(\dfrac{(2n-k)!}{(2n-k)!}\), and \(\dfrac{2n}{2n}\). This will allow us to "complete" some factorials: \[\begin{align*} &\phantom{=} \frac{2^{k-1}(n-1)(n-2)(n-3)\cdots(n-k+2)(n-k+1)}{(2n-1)(2n-2)(2n-3)\cdots(2n-k+2)(2n-k+1)} \\ &= \frac{2^{k-1}(n-1)(n-2)(n-3)\cdots(n-k+2)(n-k+1)}{(2n-1)(2n-2)(2n-3)\cdots(2n-k+2)(2n-k+1)}\times\frac{(n-k)!}{(n-k)!}\times\frac{(2n-k)!}{(2n-k)!}\times\frac{2n}{2n} \\ &=\frac{2^kn!(2n-k)!}{(2n)!(n-k)!}.\end{align*}\] Before moving on, note that when \(k=1\), the expression above simplifies to \[\frac{2^1n!(2n-1)!}{(2n)!(n-1)!}=\frac{2n(2n-1)!}{(2n)!}=\frac{(2n)!}{(2n)!}=1\] and when \(k=2\) it simplifies to \[\frac{2^2n!(2n-2)!}{(2n)!(n-2)!}=\frac{4(n)(n-1)}{2n(2n-1)}=\frac{2n-2}{2n-1}.\] For \(k=2\), this agrees with the probability computed earlier. For \(k=1\), there can never be a pair among one sock, so the probability that there is no pair among the first sock should indeed be 1.
After the first \(k\) different socks are drawn, there are \(2n-k\) socks remaining and \(k\) of them can be drawn to make a pair with one of the first \(k\). Therefore, we have \[P(n,k)=\frac{2^kn!(2n-k)!}{(2n)!(n-k)!}\times\frac{k}{2n-k}=\frac{k2^kn!(2n-k-1)!}{(2n)!(n-k)!}.\]
In the derivation above, we directly computed the probability that the first pair was found when the \((k+1)\)th sock was drawn. In the second derivation, the approach will be to count the total number of ways in which all \(2n\) socks can be drawn (without stopping at a pair), then count the number of ways in which all \(2n\) socks can be drawn so that the first pair occurs when the \((k+1)\)th sock is drawn. The probability \(P(n,k)\) is the ratio of the result of these two counts.
The second derivation of the formula assumes an understanding of binomial coefficients.
For the total number of ways to draw the socks, first observe that there are \((2n)!\) ways to order the \(2n\) socks. Since the two socks in each pair are indistinguishable, this over counts by a factor of \(2\) for each of the \(n\) pairs. Therefore, the number of ways to draw the \(2n\) socks is \(\dfrac{(2n)!}{2^n}\).
We now count the number of ways that the socks can be drawn so that the first pair occurs when the \((k+1)\)st sock is drawn. There are \(n\) choices for the colour of the first pair, and \(k\) choices for where the first of these socks was drawn (the second sock in this pair is the \((k+1)\)st sock drawn). The other \(k-1\) socks drawn among the first \(k\) must be different from each other and different from the first pair. Thus, there are \(\binom{n-1}{k-1}\) possible choices for the colours of the other \(k-1\) socks, and \((k-1)!\) orders in which they can be drawn. Thus, if the first pair is made when the \((k+1)\)st sock is drawn, then there are \[n\times k\times\binom{n-1}{k-1}\times(k-1)!\] ways in which the first \(k+1\) socks can be drawn.
Of the remaining \(2n-k-1\) socks to be drawn, there are \(n-k\) pairs. Similar to the earlier count, this means there are \(\dfrac{(2n-k-1)!}{2^{n-k}}\) ways to draw the remaining socks. Therefore, there are \[\begin{align*} n\times k\times\binom{n-1}{k-1}\times(k-1)!\times\frac{(2n-k-1)!}{2^{n-k}} &= \frac{nk(n-1)!(k-1)!(2n-k-1)!}{(k-1)!(n-k)!2^{n-k}} \\ &= \frac{k2^{k-n}n!(2n-k-1)!}{(n-k)!}\end{align*}\] ways to draw the \(2n\) socks so that the first pair occurs when the \((k+1)\)th sock is drawn. Dividing this by \(\dfrac{(2n)!}{2^n}\) and simplifying, we have \[P(n,k)=\frac{k2^kn!(2n-k-1)!}{(2n)!(n-k)!}.\]
Before solving either (i) or (ii), we will analyze the quantity \(\dfrac{P(n,k+1)}{P(n,k)}\), being careful to assume that \(k\leq n\) so that the denominator is not \(0\). Also note that in both parts we have that \(n>T_1=1\). Notice that for any integer \(m>1\), we have that \(\dfrac{m!}{(m-1)!}=m\) and \(\dfrac{(m-1)!}{m!}=\dfrac{1}{m}\). Using the formula from (b) for \(P(n,k+1)\) and \(P(n,k)\), we have that \[\begin{align*} \frac{P(n,k+1)}{P(n,k)} &= \frac{(k+1)2^{k+1}n!(2n-k-2)!}{(2n)!(n-k-1)!}\times\frac{(2n)!(n-k)!}{k2^kn!(2n-k-1)!} \\ &= \frac{2(k+1)}{k}\times\frac{n-k}{2n-k-1}\end{align*}\] Since we are interested in comparing the sizes of \(P(n,k+1)\) and \(P(n,k)\), it will be useful to determine when their ratio is greater than, less than, or equal to \(1\). To do this, we will expand the numerator and denominator and rearrange the ratio to take the form \(1+x\) and examine when the quantity \(x\) is greater than, less than, or equal to \(0\). \[\begin{align*} \frac{P(n,k+1)}{P(n,k)} &= \frac{2kn-2k^2+2n-2k}{2kn-k^2-k} \\ &= \frac{2kn-k^2-k+(2n-k^2-k)}{2kn-k^2-k} \\ &= \frac{2kn-k^2-k}{2kn-k^2-k}+\frac{2n-k^2-k}{2kn-k^2-k} \\ &= 1+\frac{2n-k^2-k}{2kn-k^2-k}.\end{align*}\] Recall that \(1\leq k\leq n\), and since \(n>1\), we have that \(k+1<2n\), so \(2n-k-1>0\) and hence \(2nk-k^2-k>0\). This means the denominator in the above expression is positive, so the sign of \(\dfrac{2n-k^2-k}{2kn-k^2-k}\) (and whether or not it is \(0\)) is completely determined by its numerator. Three pieces of information can now be extracted from the expression above, still subject to the restrictions \(n>1\) and \(1\leq k\leq n\):
\(P(n,k+1)<P(n,k)\) if and only if \(2n-k^2-k<0\).
\(P(n,k+1)>P(n,k)\) if and only if \(2n-k^2-k>0\).
\(P(n,k+1)=P(n,k)\) if and only if \(2n-k^2-k=0\).
Notice that the equation \(2n-k^2-k=0\) is equivalent to \(n=\dfrac{k(k+1)}{2}\), which means \(P(n,k+1)=P(n,k)\) if and only if \(n\) is the \(k\)th triangular number. Finally, we examine what happens when \(k=n\). In this situation, \(2n-k^2-k=0\) is the same as \(n-n^2=0\) which implies \(n=0\) or \(n=1\). Similarly, the inequality \(2n-k^2-k>0\) is the same as \(n-n^2>0\), which means \(n\) is strictly between \(0\) and \(1\). We are assuming that \(n>1\), so neither of these situations can occur. Therefore, if \(k=n\), we must have \(2n-k^2-k<0\) which makes sense since \(P(n,n+1)=0\) but \(P(n,n) > 0\).
Suppose \(n=T_i=\dfrac{i(i+1)}{2}\), the \(i\)th triangular number. From above, we have that \(P(n,i)=P(n,i+1)\). Furthermore, since the list \(T_1,T_2,T_3,\dots\) of triangular numbers is increasing (each is obtained from the previous by adding a positive number), there is no positive integer \(j\neq i\) for which \(n=T_j\) as well. Therefore, \(P(n,k+1)=P(n,k)\) if and only if \(k=i\).
Notice that the quantity \(2n-k^2-k\) is decreasing as \(k\) increases. This means it must be positive until \(k=i\), at which point it equals \(0\), and after which it must be negative. Using the earlier discussion, this means the list \[P(n,1),P(n,2),\dots,P(n,i),P(n,i+1),\dots,P(n,n)\] is increasing until \(P(n,i)\) and decreasing from \(P(n,i+1)\). We have observed that \(P(n,i)=P(n,i+1)\), so \(P(n,k)\) is largest when \(k\) takes the two values \(k=i\) and \(k=i+1\).
We now assume for some integer \(i\) that \(T_i<n<T_{i+1}\). Since \(n\) is not a triangular number, we know that there is no \(k\leq n\) for which \(P(n,k)=P(n,k+1)\). Rearranging the first two conditions in the bulleted list above, we have that \(P(n,k)<P(n,k+1)\) for any \(k\) satisfying \(\dfrac{k(k+1)}{2}<n\) and \(P(n,k)>P(n,k+1)\) for any \(k\) satisfying \(\dfrac{k(k+1)}{2}>n\). This means the probabilities \(P(n,k)\) strictly increase while \(k\) satisfies \(\dfrac{k(k+1)}{2}<n\) and decrease thereafter. By our assumption, \(i\) is the largest integer with the property that \(n>\dfrac{i(i+1)}{2}=T_i\). This means that among all positive integers \(k\leq n\), \(P(n,k)\) is largest when \(k=i+1\).
To answer the question, we need to show that \[i+1=\left\lfloor\frac{1+\sqrt{1+8n}}{2}\right\rfloor.\] We are assuming that \(T_i<n<T_{i+1}\), which means \[\frac{i(i+1)}{2}<n<\frac{(i+1)(i+2)}{2}.\] The left inequality rearranges to \(i^2+i-2n<0\). The roots of \(i^2+i-2n\) are \[i=\frac{-1\pm\sqrt{1+8n}}{2}.\] and so for the inequality \(i^2+i-2n<0\) to be satisfied, we need to have \(i\) less than the larger of these roots. We conclude that \[i<\frac{-1+\sqrt{1+8n}}{2}.\] The other inequality rearranges to \(0<i^2+3i+2-2n\). The polynomial on the right has roots \[i=\frac{-3\pm\sqrt{3^2-4(2-2n)}}{2}=\frac{-3\pm\sqrt{1+8n}}{2}.\] For the inequality \(0<i^2+3i+2-2n\) to be satisfied, \(i\) must be either smaller than the smaller root, or larger than the larger root. The smaller of these two roots is negative, so since we also require that \(i>0\), we have that \[\frac{-3+\sqrt{1+8n}}{2}<i.\] Using that this quantity is exactly one less than \(\dfrac{-1+\sqrt{1+8n}}{2}\), we now have that the integer \(i\) satisfies \[\frac{-1+\sqrt{1+8n}}{2}-1<i<\frac{-1+\sqrt{1+8n}}{2}.\] Thus, we have that the integer \(i\) is between two quantities differing by exactly \(1\). As long as the bounding quantities are not integers, this means \(i\) must be the largest integer that is less than or equal to \(\dfrac{-1+\sqrt{1+8n}}{2}\). In other words, as long as \(\dfrac{-1+\sqrt{1+8n}}{2}\) is not an integer, we will have \[i=\left\lfloor\frac{-1+\sqrt{1+8n}}{2}\right\rfloor.\] To finish the proof, suppose there is an integer \(m\) such that \(m=\dfrac{-1+\sqrt{1+8n}}{2}\). Rearranging leads to \((2m+1)^2=1+8n\) or \(4m^2+4m+1=1+8n\). Solving for \(n\) gives \[n=\frac{4m^2+4m}{8}=\frac{m^2+m}{2}=\frac{m(m+1)}{2}\] which would mean that \(n\) is a triangular number. We are assuming this is not the case, so \(\dfrac{-1+\sqrt{1+8n}}{2}\) is not an integer. Therefore, \[i+1=\left\lfloor\frac{-1+\sqrt{1+8n}}{2}\right\rfloor+1=\left\lfloor\frac{1+\sqrt{1+8n}}{2}\right\rfloor\]
We will begin by computing the peaks for a few small positive integers. To add to the work from part (c), we note that \(P(1,1)=1\), and so \(n=1\) has a unique peak of \(1\). We will use that when \(n=T_i\) for some integer \(i>1\), there are two peaks for \(n\) and they occur at \(k=i\) and \(k=i+1\), as well as the fact that when \(n\) is not a triangular number, there is a unique peak for \(n\) and it occurs at \[k=\left\lfloor\frac{1+\sqrt{1+8n}}{2}\right\rfloor.\] Keeping in mind that the first few triangular numbers are \(1\), \(3\), \(6\), \(10\), \(15\), and \(21\), we have
| \(\boldsymbol{n}\) | Peaks for \(\boldsymbol{n}\) |
|---|---|
| \(1\) | \(1\) |
| \(2\) | \(2\) |
| \(3\) | \(2\), \(3\) |
| \(4\) | \(3\) |
| \(5\) | \(3\) |
| \(6\) | \(3\), \(4\) |
| \(7\) | \(4\) |
| \(8\) | \(4\) |
| \(\boldsymbol{n}\) | Peaks for \(\boldsymbol{n}\) |
|---|---|
| \(9\) | \(4\) |
| \(10\) | \(4\), \(5\) |
| \(11\) | \(5\) |
| \(12\) | \(5\) |
| \(13\) | \(5\) |
| \(14\) | \(5\) |
| \(15\) | \(5\), \(6\) |
| \(16\) | \(6\) |
| \(\boldsymbol{n}\) | Peaks for \(\boldsymbol{n}\) |
|---|---|
| \(17\) | \(6\) |
| \(18\) | \(6\) |
| \(19\) | \(6\) |
| \(20\) | \(6\) |
| \(21\) | \(6\), \(7\) |
| \(22\) | \(7\) |
| \(23\) | \(7\) |
| \(24\) | \(7\) |
You may notice that a rather tidy pattern has started to emerge. It appears that with the exceptions of \(k=1\) and \(k=2\), the integer \(k\) occurs as a peak \(k+1\) times, and it occurs as a peak for the numbers between \(T_{k-1}\) and \(T_k\) inclusive. Therefore, we expect \(k=2025\) to occur \(2026\) times as a peak.
First, suppose \(k=2025\) occurs as a peak for some triangular number \(n\). From earlier work, this means \(n=2\,051\,325=T_{2025}\) or \(n=2\,049\,300=T_{2024}\). This gives two integers \(n\) for which \(2025\) is a peak. Otherwise, for \(2025\) to be a peak for \(n\), we must have \[2025=\left\lfloor\frac{1+\sqrt{1+8n}}{2}\right\rfloor\] which means \[2025\leq\frac{1+\sqrt{1+8n}}{2}<2026.\] This can be rearranged to get \(4049\leq\sqrt{1+8n}<4051\) which can be further rearranged to get \(2\,049\,300\leq n < 2\,051\,325\). Combining this with the other two numbers for which \(2025\) is a peak, the integers \(n\) for which \(2025\) is a peak are exactly those that satisfy \[2\,049\,300\leq n\leq 2\,051\,325.\] This is a total of \(2\,051\,325-2\,049\,299=2026\) integers.