ボールの色が \(k\) 種類あるとします。\(k = 1\) なら、現れるペアの数は常に \(0\) で、\(k = 2\) なら、常に \(1\) です。以下、\(k \ge 3\) とします。

ボールをソートしてしまえば、容易にペアの数を \(k\) にできます。また、答えが \(k - 1\) 以上であることも容易にわかります。\(k\) 種類の色を頂点とするグラフを考え、二つの色について、それらの色の二つの隣接するボールが存在するときにそれら二色を結ぶと、このグラフは連結でなければならず、よって辺が \(k - 1\) 本以上あるからです。問題は、ちょうど \(k - 1\) 本で済むのはいつか、です。

辺がちょうど \(k - 1\) 本の場合、それらは木をなします。色に \(1\) から \(k\) までの番号をつけ、またそれらの番号に対応する色のボールの個数を \(A_1, A_2, \ldots, A_k\) とします。ボールの配置は、この木における閉じたウォークとみなせます。このウォークは、頂点 \(1\) から出発し、すべての頂点を訪れ、頂点 \(1\) に戻り、その過程で頂点 \(i\) を \(A_i\) 回以下訪れます（「ちょうど」でなく「以下」なのは、同じ頂点に留まってもよいからです）。

このようなウォークはどれも頂点 \(i\) を \(deg(i)\) 回以上訪れること（\(deg(i)\) は木における頂点 \(i\) の次数を表します）と、各 \(i\) について頂点 \(i\) をちょうど \(deg(i)\) 回訪れるようなウォークが存在すること（深さ優先探索から得られます）が容易にわかります。よって、問題は、頂点 \(i\) の次数が \(A_i\) 以下であるような木を作れというものになります。

すると、\(n = A_1 + A_2 + \ldots + A_k < 2k-2\) なら、答えが \(k\) であることが明らかです。そうでなければ、上記の木は必ず存在するため、答えは \(k-1\) です。実際、和が \(2k-2\) であるような任意の正整数 \(B_1, B_2, \ldots, B_k\) について、次数が \(B_1, B_2, \ldots, B_k\) であるような \(k\) 個の頂点の木が存在します。この木は、例えば次のようにして帰納的に構築できます。\(B_i = 1, B_j > 1\) であるような頂点 \(i, j\) を任意にとり、頂点 \(i\) 以外のすべての頂点について対応する木を構成します。ここで、頂点 \(j\) 以外の頂点の次数はそのままで、頂点 \(j\) のみ次数を \(B_j-1\) とします。そして、辺 \((i, j)\) を追加します。