Find specific cases of $n$ that satisfy the following statement. Question: Let $k$ be a positive integer with $k \geq 2$. Two bags each contain $k$ balls, labelled with the positive integers from $1$ to $k$. Andre removes one ball from each bag. (In each bag, each ball is equally likely to be chosen.) Define $P(k)$ to be the probability that the product of the numbers on the two balls that he chooses is divisible by $k$. Then there exist infinitely many positive integers $n \geq 2$ such that $P(n) \leq \frac{2n - 1}{n^2}$. Find the sum of all such $n$ for $n \leq 20$.
My solution:
Claim: $n$ satisfies these constraints if and only if $n$ is prime.
Proof: If each bag has $n$ balls, we can write them as following below;
${1, 2, 3, 4, ..., n}$
${1, 2, 3, 4, ..., n}$
Let's try some of the first few numbers. If $n = 2$, then we can pair $1, 2$ or $2, 1$ or $2, 2$. So, there are $3$ ways to create successful pairs and $2^2$ total combinations. This means that the probability is $\frac{3}{4}$ which does fit the constraint because $\frac{2n - 1}{n^2} = \frac{3}{4}$. Great!
For $n = 3$, let's visualize this: The $2$ bags have balls numbered $(1, 2, 3)$ and $(1, 2, 3)$.
You can pair any of the numbers with $3$, so this creates $3$ successful pairs. Double this for each bag. But, you have to subtract one case; $(3, 3)$, because it gets overcounted. So, this gives $3(2) - 1 = 5$ successful pairs.   But this only works because $3$ is prime and it has no other factors except $1$ and itself.
So, for each prime number, there are $2n - 1$ ways to create successful pairs, and $n^2$ total ways to create any pair. This means for a prime number $n$, $P(n) = \frac{2n - 1}{n^2}$. This means every prime number works because $P(n) = \frac{2n - 1}{n^2}$.
However, what if $n$ is not a prime number? For example, let's try this for the number $4$. If we do the same counting as before, we get $7$ successful cases, but we miss the case $(2, 2)$.  So, in reality, there are $8$ succesful cases, which does not satisfy the constraints anymore. So, if $n$ is not a prime number, it has every case from a prime number but it has cases that we do not see from it's factors. To finish off this proof, since $P(n) = \frac{2n - 1}{n^2}$ when $n$ is a prime number, we would only need at least $1$ extra successful pair to make $P(n) > \frac{2n - 1}{n^2}$ when $n$ is not a prime number. This $1$ extra successful pair can be achieved by multiplying one of the other factors of a non-prime number other than $1$ or $n$ by itself. So, $P(n) > \frac{2n - 1}{n^2}$ when $n$ is not prime.
Hence, the answer to the original question is equal to the sum of all prime numbers less than or equal to $20$, which is $2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 = \boxed{77}$.
I am wondering how to make my proof more formal, so any help or suggestions about my proof would be very helpful. Thanks in advance!
 A: It seems like order does matter for this situation, because if it does not, then $P(n) < \frac{2n - 1}{n^{2}}$ for all $n$. Assuming that order matters, then what you did is correct. But, you can improve the reason why the number of valid pairs for $n$ prime is $2n - 1$ by stating that $(n,n)$ will be overcounted. This is because it is not enough that you just proved it using the case where $n = 3$.

By the way, some additional remarks about $P(n)$. Here is my semi-proof for what $P(n)$ is:
For every $n$, it is guaranteed that the pair $(n,i)$ for $1 \leqslant i \leqslant n$ will divide $n$. By counting, we have $n$ pairs and because order matters, we now have $2n$ pairs. However, $(n,n)$ is the same as $(n,n)$, hence we remove $1$ case from $2n$, giving $2n - 1$ pairs.
Now, if $n$ is prime, then it is relatively prime to every other number. This means that for all $i$ and $j$ from $1$ to $n - 1$, $n$ will not divide $ij$.
If $n$ is composite, we need to check every pair that yields $ij$ for $1 \leqslant i \leqslant n$ and $j = n$. This is because what we are looking for are pairs of the form $(a, \frac{ij}{a})$ that is not included in the list of pairs where $1 \leqslant a \leqslant ij$. We do this using the divisor function $\tau(n)$. Now, if $\left\lceil\frac{\tau(ij)}{2}\right\rceil > i$, then add $\left\lceil\tau(ij)\right\rceil - 2i$ pairs. We remove $2i$ pairs because  there are $2i$ pairs where $\frac{ij}{a}$ is greater than $n$ and $\frac{ij}{a}$ is not included in the bag. Otherwise, move to the next $i$.
Now, count the number of pairs then divide by $n^{2}$. This will be $P(n)$.
