The answer is n Proof: Base case: n=2 We have two colours and four balls There at least two balls in a box and at least two balls have a common colour. Take,the same colour balls in the same boxes. Therefore,we can do this move for n moves. n=3 We have three colours and six balls. By repeating the same process,we can have n It continues It is proved by induction over n>=2.

My (almost) solution is: for $n=2m, N=3m$; and for $n=2m+1, N=3m+1$ (a.k.a. $N=\lfloor \frac{3n}{2} \rfloor$). Consider a graph where each vertex is a color, and two vertices have edge iff there is a box with these two color balls. As each vertex has degree 1 or 2, the graph can be partitioned into several cycles (and some lone vertices). Lemma: For a cycle of length $k$, $k+1$ moves are necessary and sufficient to arrange the balls of these colors. I'm not sure about the proof; I can brute force for the cases $k=2$ and $k=3$. For $k \geq 4$, I think we can generalize the moving algorithm analogously, but I can't find a way to rigorously prove it though. However, if this lemma is true, then we automatically get the upper bound. For the lower bound, for $n=2m$, consider the case where the graph has $m$ cycles of length 2. For $n=2m+1$, consider the case where the graph has $m-1$ cycles of length 2 and one cycle of length 3.

carefully wrote: My (almost) solution is: for $n=2m, N=3m$; and for $n=2m+1, N=3m+1$ (a.k.a. $N=\lfloor \frac{3n}{2} \rfloor$). Consider a graph where each vertex is a color, and two vertices have edge iff there is a box with these two color balls. As each vertex has degree 1 or 2, the graph can be partitioned into several cycles (and some lone vertices). Lemma: For a cycle of length $k$, $k+1$ moves are necessary and sufficient to arrange the balls of these colors. I'm not sure about the proof; I can brute force for the cases $k=2$ and $k=3$. For $k \geq 4$, I think we can generalize the moving algorithm analogously, but I can't find a way to rigorously prove it though. However, if this lemma is true, then we automatically get the upper bound. For the lower bound, for $n=2m$, consider the case where the graph has $m$ cycles of length 2. For $n=2m+1$, consider the case where the graph has $m-1$ cycles of length 2 and one cycle of length 3. I think your lemma is wrong. You can check with k=6, it may need more moves in some cases

The answer is $\left\lfloor\frac{3n}2\right\rfloor$. Bound: Take two colours, say $a,b$, and consider the two boxes $\dbinom a b$ $\dbinom b a$. It takes one move to move a ball to a different box, and then two more moves to complete the boxes (i.e. have the same colours). If $n$ is even, repeating this with different colours gives the desired value. If $n$ is odd, repeat this until there are $3$ colours left, then have the boxes $\dbinom a b$ $\dbinom b c$ $\dbinom c a$. It takes at least 4 moves to complete this (one to move one away and at least three to complete each box). This gives the desired value. Construction: We first proceed by strong induction. The cases $n=1,2$ are trivial. Suppose that for all $k<n$, it is possible to do the task in at most $\left\lfloor\frac{3k}2\right\rfloor$ moves. Now consider a graph with boxes as vertices. We connect two boxes if they share a colour. This graph consists of disjoint cycles. If the graph has more than 1 cycle, we use the induction hypothesis by resolving each of these separately. This gives us the bound. We are left to deal with the case when the graph is one big cycle. Arrange the boxes in a circle such that adjacent boxes have the same colour. So our boxes look like: $\dbinom 1 2\dbinom 2 3\cdots\dbinom n 1$ where the contents of each box are arranged in some order. We refer to switching the order of balls in a box as a "swap". We wish to make now a series of swaps so that each ball on top has a different colour. It's clear that this is possible. We may do this in at most $\left\lfloor\frac n2\right\rfloor$ moves, since otherwise by swapping every box (and undoing all swaps that we did in the process) we end up with the desired configuration. Now we undo the last move, which leaves us with exactly two balls on top, and also exactly two balls on bottom. (If we had not made any moves, it is easy to see that the final state can be reached in $n+1$ moves.) Now remove the two balls of the same colour on top and put them in the empty box, then delete it. Then there is a bottom ball which has the same colour as its adjacent top ball, so we put the top ball in that box, and then delete that box. This process repeats itself $n-2$ times, until we are left with the two balls with the same colour which were at the bottom. We put one in the same box as the other and we are done. The above process took $n+1$ moves, so the total number of moves is at most $\left\lfloor\frac n2\right\rfloor-1+n+1=\left\lfloor\frac{3n}2\right\rfloor$.