Let \(k\) denote the number of distinct colors among the balls. If \(k = 1\), you will always get \(0\) such pairs; if \(k = 2\), you will always get \(1\) such pair. Now suppose \(k \ge 3\).

It’s easy to get precisely \(k\) such pairs by just sorting the balls. It’s also easy to see that the answer is at least \(k-1\): if we consider a graph on these \(k\) colors, where we connect two colors if there are two adjacent balls of these colors, the graph has to be connected, so the number of edges is at least \(k-1\). The question is: when can it be exactly \(k-1\)?

If we get precisely \(k-1\) such edges, then these edges form a tree. Let the colors be numbered from \(1\) to \(k\), and let the numbers of balls with corresponding colors be \(A_1, A_2, \ldots, A_k\). Our ball arrangement can be seen as a closed walk on this tree: starting from node \(1\), visiting every node, and coming back, so that node \(i\) is visited at most \(A_i\) times (at most instead of exactly because we also allow to stay on the same node).

It’s easy to see that in any such walk, node \(i\) will be visited at least \(deg(i)\) times (where \(deg(i)\) denotes the degree of node \(i\) in this tree), and that a walk where node \(i\) is visited precisely \(deg(i)\) times for each \(i\) exists (you can get it from depth-first-search). So, the question becomes about constructing a tree in which the degree of node \(i\) is at most \(A_i\).

It’s clear then that if \(n = A_1 + A_2 + \ldots + A_k < 2k-2\), then the answer is \(k\). Otherwise, the answer is \(k-1\), as such a tree will always exist. In fact, for any positive integers \(B_1, B_2, \ldots, B_k\) with sum \(2k-2\) there exists a tree on \(k\) nodes with degrees \(B_1, B_2, \ldots, B_k\). You can build it, for example, inductively, by taking any two nodes \(i, j\) with \(B_i = 1, B_j > 1\), constructing the corresponding tree for all nodes except for \(i\), in which all nodes except \(j\) have the same degree, and \(j\) has degree \(B_j-1\), and then adding an edge \((i, j)\).