a) First, we'll prove that for a color $A_1$ from the $k$ colours, the amount of steps needed for moving all $n$ stones of color $A_1$ into one of the ends of the line, is completely independent from the amount of steps needed to arrange correctly the other $n(k-1)$ stones, this way we can use a recurrence and easily get $m$. Let us have a line with $n(k+1)$ stones, $n$ for each one of the $k+1$ colours. We are going to use two different ways of observing the order of the stones. $Order 1$ will be the normal line, the fifth stone will be fifth in $Order 1$, the third, third, etc. $Order 2_i$ will be the line without the color $A_i$, if there are three stones of color $A_1$ at the beginning of the line and then a stone of color $A_2$, the $A_2$ stone would be first in $Order 2_1$, but fourth in $Order 1$. Now that we have defined these two orders we can start proving what we need. Without loss of generality, we'll work with $Order 2_1$. Each step can: -Exchange two stones which aren't of color $A_1$, this step would alter $Order1$, but not $Order 2_1$ -Exchange one stone of color $A_1$ and another of other color, this step would alter $Order 2_1$, but not $Order 1$ -Exchange two stones of color $A_1$, but it would waste a step. Each step will affect either $Order1$ or $Order2_1$, but never both, or neither. This means that moving the $A_1$ stones to an end of the line (altering $Order1$) is independent from arranging the $k$ colours remaining to the correct arrangement (altering $Order 2_1$), and because there will always be a color that has to go in the last n positions, we can see what the amount of steps needed to arrange that color, implies for $m_{k+1}$. Let $m_i$ be the $m$ for $i$ colours and $n$ stones per color. Arranging correctly $Order 2_1$ is always possible with a quantity of $m_k$ steps, so we now have to find the quantity of steps needed to move all $n$ stones of color $A_1$ to an end of the line in $Order1$. The amount of steps needed for $n$ stones to move from one end of the line to the other end is of $n^2k$ steps ($nk$ steps for each of the $n$ stones). Every possible permutation of the $n$ stones in the $n(k+1)$ positions can be achieved while moving the stones to the other end, this means the amount of steps needed for the n stones to get to one end, plus the amount of steps needed to get the $n$ stones to the other end is $n^2k$. Because there are two ends, the amount of steps needed for the $n$ stones to get to all n positions on either end is at most $\frac{n^2k}{2}$. This means that for any line of $k+1$ colours and $n$ stones per color, and choosing any color at random, all $n$ stones of that color are able to get to an end with a maximum of $\frac{n^2k}{2}$ steps, and arranging the remaining k colours can be done with a maximum of $m_k$ steps. This means $m_{k+1}=m_k+\frac{n^2k}{2}$ steps can correctly arrange any possible line of $k+1$ colours and $n$ stones per colour. The recurrence $m_{k+1}=m_k+\frac{n^2k}{2}$ with $m_1=0$ gives $m_k=\frac{n^2k(k-1)}{4}$, so we are left to prove there exists a line which needs $\frac{n^2k(k-1)}{4}$ steps. We use now that $n$ is even: Let the line with $k$ colours and $n$ stones per color be the line that has $\frac{n}{2}$ stones of color $A_1$, then $\frac{n}{2}$ stones of color $A_2$, then $\frac{n}{2}$ stones of color $A_3$,..., then $\frac{n}{2}$ stones of color $A_{k-1}$, then $n$ stones of color $A_k$, then $\frac{n}{2}$ stones of color $A_{k-1}$,..., then $\frac{n}{2}$ stones of color $A_1$. Because of $Order1$, every color needs $\frac{n^2(k-1)}{2}$ steps to get to an end of the line, and then, the $Order2_i$ would be exactly the same line as before, but with $k-1$ colours, using this same argument $k-2$ times more we have that the amount of steps needed to correctly arrange the stones is $\frac{n^2(k-1)}{2}+\frac{n^2(k-2)}{2}+\frac{n^2(k-3)}{2}+...+\frac{n^2}{2}=\frac{n^2k(k-1)}{4}$ With this we now conclude $m_k=\frac{n^2k(k-1)}{4}$ steps can arrange correctly any possible line and it is the lower integer to satisfy this. b) Let $1$, $2$, and $3$ be the three colours. Let n=2q+1 We know that one color can be moved to one end with $\frac{2n^2}{2}=n^2$ steps. And then, arranging the remaining stones in $Order 2_i$ can always be achieved with $\lfloor\frac{n^2}{2}\rfloor=2q^2+2q$ steps. So this means we can always arrange correctly the stones with $n^2+2q(q+1)$ steps. Now, we'll use an example to prove $n^2+2q(q+1)$ is the lower value that satisfies this: Let the line of 3 colours and n stones per color be with n=2q+1: First, $q$ stones of color $1$, then $q-1$ stones of color $2$, then $q-1$ stones of color $3$, then a stone of color $2$, then two stones of color $3$, then a stone of color $1$, then two stones of color $2$, then $q$ stones of color $3$, then $q-1$ stones of color $2$, and then $q$ stones of color $1$. With this line, we calculate the amount of steps needed to get color $1$ to an end and then calculate the amount of steps needed to get color $2$ to an end in $Order 2_1$ and get $n^2+2q(q+1)$. Then we calculate the amount of steps needed if color $1$ doesn't go in an end, that is, if color $2$ goes in an end, and then the amount of steps needed to get color $1$ to an end in $Order 2_2$ and we get again that the amount of steps needed are $n^2+2q(q+1)$. So we conclude that with $n^2+2q(q+1)$ steps it's possible to arrange the line correctly, and that $n^2+2q(q+1)$ is the lower integer that satisfies this.