The original formulation asks only for the largest value for which the task is not possible.

The answer is $\boxed{n^2-n-1}$ for all integers $n\geq 3$. Claim: All integers $\geq n^2-n$ is $n$-colorful for all $n\geq 3$. Proof. For the sake of laziness, let $X,Y$ denote $1,2,\dots,n$ and $1,1,2,\dots,n$, respectively. Note that $$XX\dots XYY\dots Y$$where there are $k$ $X$’s and $l$ $Y$’s clearly work. Thus, positive integers in the form $nk+(n+1)l$ are $n$-colorful. By Chicken Mcnugget Theorem, all number $\geq n\cdot (n+1) - n - (n+1)+1= n^2-n$ can be expressd as $nk+(n+1)l$ for some integers $k,l\geq 0$. Hence, the claim is proved. Claim: $n^2-n-1$ is not $n$-colorful for all $n\geq 3$. Proof. Assume the contrary. There must exists a color $C_i$ such that there are at most $\left\lfloor\frac{n^2-n-1}{n}\right\rfloor=n-2$ marbles with color $C_i$ in the circle. Without loss of generality, let that color be $C_1$. Consider if we color as the following. $$C_1\mid C_1^1,C_2^1,\dots,C_{n+1}^1\mid C_1^2,C_2^2,\dots,C_{n+1}^2\mid \cdots\mid C_1^{n-2},C_2^{n-2},\dots,C_{n+1}^{n-2}$$where $C_i^j\in\{C_1,C_2,\dots,C_n\}$. Note that $C_1\in\{C_1^i,C_2^i,\dots,C_{n+1}^i\}$ for all positive integers $i\leq n-2$ since any $n+1$ consecutive marbles must contain every colors. Thus there are at least $1+(n-2)=n-1$ marbles with color $C_1$, a contradiction.

Great pigeonhole exercises never get old! There is a colour, e.g. blue, such that among the $m$ marbles in the circle there are at most $\left\lfloor \frac{m}{n} \right\rfloor$ in number which are all blue. The blue marbles divide the circle into at most $\left\lfloor \frac{m}{n} \right\rfloor$ groups and each group has non-blue marbles; the overall number of these is at least $m - \left\lfloor \frac{m}{n} \right\rfloor$. Hence by the Pigeonhole principle there is a group with at least $$\left\lceil \frac{m - \left\lfloor \frac{m}{n} \right\rfloor}{\left\lfloor\frac{m}{n} \right\rfloor} \right\rceil $$marbles. If the latter is at least $n+1$ we would obtain a collection of $n+1$ consecutive marbles not containing all colours (since blue is missing) and this would lead to a contradiction. The latter holds for $m=n^2-n-1$ as $\left\lceil \frac{n^2-n-1 - \left\lfloor \frac{n^2-n-1}{n} \right\rfloor}{\left\lfloor\frac{n^2-n-1}{n} \right\rfloor} \right\rceil = \left\lceil \frac{n^2-n-1 - (n-2)}{n-2}\right\rceil = \left\lceil n + \frac{1}{n-2} \right\rceil = n+1$. It remains to provide a construction for any $m\geq n^2 - n$. Denote the colours by $1$, $2$, $\ldots$, $n$. By the Frobenius Coin Problem there are non-negative integers $a$ and $b$ such that $an + b(n+1) = m$. Putting consecutively $a$ groups of the form $1$, $2$, $3$, $\ldots$, $n$ and then $b$ groups of the form $1$, $1$, $2$, $3$, $\ldots$, $n$ satisfies the requirements. (If you wish to avoid relying on Frobenius, then take explicitly $a = -m+\left\lfloor \frac{m}{n}\right\rfloor(n+1)$ and $b=m-\left\lfloor \frac{m}{n}\right\rfloor n$ which are non-negative since $\frac{m}{n+1} \leq \left\lfloor \frac{m}{n}\right\rfloor \leq \frac{m}{n}$ due to $\left\lfloor \frac{m}{n} \right\rfloor \geq \frac{m-n+1}{n} \geq \frac{m}{n+1}$ for $m\geq n^2-1$, also $\frac{n^2-n}{n+1} < n-1 = \frac{n^2-n}{n}$, while for $m = n^2 - k$, $2\leq k \leq n-1$ we have $\left\lfloor \frac{m}{n} \right\rfloor = n - 1 = \frac{n^2-1}{n+1} > \frac{m}{n}$.)

The answer is $n^2 - n - 1$ Proof that $m = n^2 - n - 1$ is not colourful: FTSOC, assume it is colourful. By PHP, there exists a colour $C_k$ with $\leq \left \lfloor \frac{n^2 - n - 1}{n} \right \rfloor = n - 2$ marbles. Consider the number of marbles between every two consecutive marbles with the colour $C_k$. It must be $\leq n$, otherwise we can find $n+1$ consecutive marbles without $C_k$. However, the number of marbles then becomes $\leq n-2 + (n-2)n = n^2 - n - 2 < n^2 - n - 1$. Contradiction, so $n^2 - n - 1$ is not colourful. Proof that $m > n^2 - n - 1$ is colourful: We will provide a configuration for each $m$. Let $m \equiv k \mod n$ where $0 \leq k < n$. Place $m$ marbles on a circle. We start from any marble and colour it $C_1, C_2, \dots, C_n$ clockwise periodically until there are $k \cdot n + k = k(n+1)$ marbles remaining. Then continue by colouring the marbles $C_1, C_2, \dots, C_n, C_n$ periodically until all the marbles are coloured. This is guaranteed to be colourful because it is easy to see that the number of marbles between two consecutive marbles of the same colour is at most $n$.

We will prove that $n^2-n-1$ is not $n-$colourful, but all $t \geq n^2-n$ are. Part 1: $n^2-n-1$ is not $n-$colourful. Consider a random colour, and suppose it appears $i$ times. There exist therefore at most $i$ gaps created between the appearances of that colour, and each gap can be of length at most $n$, by the given condition. Thus, $n^2-n-1 \leq i+in$ implying that $i \geq n-1$. Since we have $n$ colours, we have $\geq n(n-1) =n^2-n$ marbles, absurd. Part 2: All $t \geq n^2-n$ are $n-$colourful. Write $t$ as $an+b$ with $0 \leq b\leq n-1$. Claim: $a \geq b$. Proof: Suppose otherwise, then $a \leq b-1$ and so $n^2-n \leq t=an+b \leq (b-1)n+b=(n-2)n+n-1=n^2-n-1$, a contradiction $\blacksquare$ Denote the colour $C_i$ by $i$. By the claim we may take $a-b$ copies of $1,2,\ldots,n$, followed by $b$ copies of $1,1,2,\ldots,n$. We have $(a-b)n+b(n+1)=an+b=t$ marbles in total, and the problem condition is clearly satisfied. Combining parts 1 and 2, we have solved the problem.

Let $m=an+b$ with $0\leq b\leq n-1$. We claim that the task is impossible if and only if $a<b$. If $a\geq b$, then $m=b(n+1)+(a-b)n$, so we can put the sequence $1$, $2$, $\ldots$, $n$ a total of $a-b$ times, follows by $1$, $2$, $\ldots$, $n$, $1$ a total of $b$ times. Any $n+1$ consecutive beads contain two parts of the sequence $1$, $2$, $\ldots$, $n$ that have all of the colors. Now, suppose that $a<b$. If the $i$th color appears $a_i$ times and $a_1\geq a_2\geq\ldots\geq a_n$, then $\sum_{i=1}^n(a_i-a)=b$. Therefore, if $\sum_{i=1}^b(a_i-a)<b$, then $a_b-a\leq0$, so $\sum_{i=1}^n(a_i-a)<b$, which is impossible. Therefore, $\sum_{i=1}^ba_i\geq ab+b$. The expected number of beads with color $1$, $2$, $\ldots$, $b$ in any $n+1$ consecutive beads is $(ab+b)\frac{n+1}m$. If the task is possible, then $(ab+b)\frac{n+1}m\leq b+1$ since each color appears at least once. However, this is equivalent to $(ab+b)(n+1)\leq(b+1)(an+b)$, or $abn+ab+bn+b\leq abn+an+b^2+b$, which simplifies to $(b-a)(b-n)\geq0$. Since $a<b$ and $b<n$, we have $(b-a)(b-n)<0$, contradiction. Therefore, the task is impossible if and only if $a<b$, so the number largest value of $m$ for which the task is not possible is $m=(n-2)n+(n-1)=\boxed{n^2-n-1}$.

ISL 2021 C2. Let $n\in\mathbb Z_{\ge 3}$. An integer $m\ge n+1$ is called $n$-colorful if, given infinitely many marbles in each of $n$ colors $C_1, \dots, C_n$, it is possible to place $m$ of them around a circle so that in any group of $n+1$ consecutive marbles there is at least one marble of color $C_i$ for each $i=1, \dots, n$. Prove that there are only finitely many positive integers which are not $n$-colorful. Determine the largest among them. Solution. We firstly show that $m=n^2-n-1$ is not colorful. Assume on the contrary that $n^2-n-1$ is $n$-colorful. Indeed, by Pigeonhole Principle, there exists $1\le k\le n$ such that $C_k$ appears at most $n-2$ times in the circle. Let $C_k$ be in the $a_1^{\text{th}}, \dots, a_l^{\text{th}}$, where $l\le n-2$. Obviously, $a_2-a_1, a_3-a_2, \dots, a_l-a_{l-1}, a_1+(n^2-n-1)-a_l\le n+1$. However, \begin{align*}n^2-n-1&=\sum_{k=1}^{l-1}(a_{k+1}-a_k)+(a_1+(n^2-n-1)-a_l)\\&\le l(n+1)\\&\le (n-2)(n+1)\\&=n^2-n-2\\&<n^2-n-1,\end{align*}which gives a contradiction. Next, we show that if $m\ge n^2-n$, then $m$ is $n$-colorful. Indeed, let $m=an+b$, where $a\ge n-1$, $0\le b<n$. We can take \[\underbrace{1, 2, \dots, n-1, 1, n, 1, 2, \dots, n-1, 2, n, \dots, 1, 2, \dots, n-1, b, n}_{b(n+1)}, \underbrace{1, 2, \dots, n, \dots, 1, 2, \dots, n}_{(a-b)n},\]where $k$ represents $C_k$, concatenating the first and the last forms a circle. Therefore, there are only finitely many positive integers which are not $n$-colorful, and the largest among them is $n^2-n-1$.

The answer is $m=n^2-n-1$. Firstly, there is a color used at most $n-2$ times due to PHP. The remaining stones are $(n-1)^2$ which are distributed into $n-2$ arcs at most, so some arc has length at least $n+1$ (again due to PHP) and doesn't have that color, absurd. Secondly, let $m=nk+r$ for $k\geq n-1, r\leq n-1$. Put $k-r$ times block $(1,2,...,n)$ and $r$ times $(1,1,2,...,n)$.

Here is a more straightforward proof for $n^2-n-1$. Consider all $n^2-n-1$ blocks of $n+1$ consecutive beads. Assign a type of each block the color that appears twice. Let $x_i$ denote the number of beads of type $i$. Observe that each bead appear in $n+1$ blocks, so by double-counting the number of times the bead of color $i$ appear, we have that \begin{align*} \#\{\text{bead of color }i\} &= \frac{(x_1+x_2+\dots + x_n) + x_i}{n+1} \\ &= \frac{n^2-n-1+x_i}{n+1} \\ &= \frac{x_i-n}{n+1} + n-1, \end{align*}implying that $n+1\mid x_i-n$, so $x_i \geq n$ for all $i$. However, this means that $x_1+x_2+\dots + x_n \geq n^2$, a contradiction.

The answer is $n^2-n-1$. Number the colors from $1$ to $n$. If $m \ge n^2-n$, then by Chicken McNugget, we can find nonnegative integers $a$ and $b$ such that $an+b(n+1)=m$. Then, we can combine $a$ strings of beads with colors $1,2,\ldots,n$ and $b$ strings of beads with colors $1,1,2,\ldots,n$. Clearly, any $n+1$ consecutive beads include $n$ of distinct colors. If $m=n^2-n-1$, then there must be a color that is used at most $n-2$ times by pigeonhole. Call that color $k$. There are at most $n$ beads between any two consecutive beads colored $k$, otherwise we can choose $n+1$ consecutive beads between the two beads colored $k$. Thus, there are at most $n-2$ beads colored $k$ and $n(n-2)$ not colored $k$, so there are at most $n^2-n-2$ beads, a contradiction. Remark: Using this method, we can prove that $m$ works if and only if $m$ can be written as $an+b(n+1)$ for nonnegative integers $a$ and $b$.

Note that by Chicken McNugget Theorem, when $m\ge n(n-1)$ we can represent $m$ as a linear combination of $n,n+1$ so we can put the $m$ beads as a string of colors $(1,2,\dots,n)$ and $(1,1,2,\dots,n)$ which works. $~$ If $m\le n^2-n-1$, note that there will be a color, WLOG let it be color $1$ such that there are at least $m-\left\lfloor \tfrac{m}{n} \right\rfloor$ beads not of this color. These beads are separated by at most $\left\lfloor \tfrac{m}{m} \right\rfloor$ beads of color $1$ and we claim that there exists some gap of size at least $n+1.$ $~$ It suffices to prove \[\frac{m}{\left\lfloor \tfrac{m}{n} \right\rfloor}>n+1\]which is true when $m=n^2-n-1$ so that is the maximum.

Also Iran 3rd combinatorics exam p3 . I wonder why they put this kind of easy one as a 3 !!!

The answer is $m = n^2 - n - 1$. If $m = n^2 - n - 1$, then the PHP implies there is some color $S$ such that $k \le n - 2$ beads are painted with $S$. If $k = 1$, then the total number of beads on the necklace is at most $n + 1$, which is absurd for $n \ge 3$. Now, we consider $k \ge 2$. We say the ordered pair $(B_i, B_j)$ of two $S$ colored beads is a neighbor if there are no other $S$ colored beads between the two beads when we travel clockwise from $B_i$ to $B_j$. Clearly, if there are $k \ge 2$ beads colored in $S$, then there are exactly $k$ neighbors. Moreover, because of the given condition, we know no more than $n$ non-$S$ colored beads can be between any two neighboring beads when we travel clockwise from the first to the second. Thus, the total number of beads on the necklaces is at most $$(n - 2) + (n-2) \cdot n = n^2 - n - 2$$which is absurd. It follows that no satisfactory necklace exists for $m = n^2 - n - 1$. Now, we provide a construction for all $m \ge n(n - 1)$. Let our $n$ colors be $\{1, 2, \ldots, n\}$ and $L$ denote a group of $n$ consecutive beads colored with $1, 2, \ldots, n$ in clockwise order. If $m = t \cdot n + r$ where $0 \le r < n$, then coloring our $m$ beads $$L, 1, L, 2, L, \ldots, L, r, \underbrace{L, L, \ldots, L}_{t-r\rm\ \text{times}}$$in clockwise order works since $t \ge n - 1 \ge r$. $\blacksquare$ To Clarify: If $k = 2$, then we have two $S$ colored beads named $B_1$ and $B_2$. As a result, $(B_1, B_2)$ and $(B_2, B_1)$ are both neighbors.

I don't see this proof for showing $m=n^2-n-1$ fails, does it have any flaw? We begin in a similar fashion, by PHP there exists a colour $c$ with $\le n-2$ beads, now noting that $n^2-n-1 = (n+1)(n-2) + 1$ isolate one of the beads which is coloured $c$ and partition the remaining $(n+1)(n-2)$ beads into consecutive blocks of size $n+1$, there are $\le n-3$ beads of colour $c$ and there are $n-2$ blocks so some block does not contain $c$ which is a contradiction.

MrOreoJuice wrote: I don't see this proof for showing $m=n^2-n-1$ fails, does it have any flaw? We begin in a similar fashion, by PHP there exists a colour $c$ with $\le n-2$ beads, now noting that $n^2-n-1 = (n+1)(n-2) + 1$ isolate one of the beads which is coloured $c$ and partition the remaining $(n+1)(n-2)$ beads into consecutive blocks of size $n+1$, there are $\le n-3$ beads of colour $c$ and there are $n-2$ blocks so some block does not contain $c$ which is a contradiction. Your idea works just fine .

We claim the answer is $m=n^2-n-1$. To prove this number doesn't work, take the color $c$ that occurs the least amount of times, says $s$ times. By PhP, this occurs at most $s \le \left \lfloor \frac{n^2-n-1}{n} \right \rfloor = n-2$ times. Consider the gaps in between each of the beads with color $c$. We have that $(a_1+1)+(a_2+1)+(a_3+1) + \cdots + (a_s+1) = n^2-n-1$. As $s \le n-2$, there is an $i$ such that $a_i + 1 \ge \left \lceil \frac{n^2-n-1}{n-2} \right \rceil = n+2$, so $a_i \ge n+1$. Taking those $n+1$ beads we have color $c$ never occurs, so we have proven $n^2-n-1$ doesn't work. If $m \ge n^2-n$, note that by the Chicken McNugget Theorem, $m=a(n+1)+bn$ for some nonnegative integers $(a,b)$. Let the colors be $C_1, C_2, \dots , C_n$. Let $X=C_1C_2C_3 \dots C_nC_1$ and $Y=C_1C_2C_3 \dots C_n$. It can easily be seen that $XX \dots X YY \dots Y$ works where there is $a$ $X$'s and $b$ $Y$'s so we are done.

We use definitions from original statement. Claim. Number $a$ is not $n-\text{colourful}$ iff $a\in [kn+k+1;(k+1)n-1]\text{ } (\diamondsuit )$ for some $k\in \mathbb{Z}^+.$ Proof. If $(\diamondsuit )$ holds, then by Pigeonhole principle there are at most $k$ marbles of some color $A$ and we can ensure that there exist group of $n+1$ consecutive marbles, no one of color $A.$ For only if part it's suffice to prove that for every $k\in \mathbb{Z}^+$ integer number $a\in [kn;k(n+1)]$ is $n-\text{colourful}.$ Indeed, color marbles counterclockwise with colors $n,1,2,...,n,1,2,...,n,1,2...n,...1,2,...$ Easy to check that this painting satisfies. Note that there are no numbers in $(\diamondsuit )$ for $k>n-2$ and one number $n^2-n-1$ for $k=n-2,$ which is the answer.

Answer from imo-offical

The answer is $\frac{(n-1)(n-2)}2$ numbers, and thus $n^2-n-1$ is maximal. In general, I claim that $m = nq+r$ works if and only if $r \leq q$, which yields the desired count. Denote by $a_i$ a bead colored $i$. If $r \leq q$, then consider the string of beads given by $q$ repetitions of $a_1a_2 \cdots a_n$. Between each of $r \leq q$ repetitions of $a_1a_2$, insert another instance of $a_1$. This necklace obviously satisfies the given conditions. On the other hand, if $r > q$, it suffices to show that there is a color $i$ such that there exist two beads of color $i$ a distance more than $n+1$ beads apart with no similarly colored beads between them. By Pigeonhole, there exists a bead that appears at most $q$ times. On the other hand, as the total distance traversed between all consecutive pairs of beads is $nq+r > (n+1)q$, there exists two beads that are more than $n+1$ apart, as needed.

We claim that the answer is all numbers, $a$, such that for the numbers $b$ and $c$ with $0 \leq c \leq n-1$, and $a = bn +c$, we have $c > b$. This gives that the maximal is $\boxed{n^2-n-1}$. $\textbf{Case 1: The answer works}$ Consider a specific color $x$. We place $x$ at a specific point. The maximum number of beads we can add before adding another $x$ is $n$. Including that $x$ we would add $n+1$. We can see that we will have $b+1$ beads of that color in total. This is obviously the minimum possible number of beads of that color. Since we have $n$ colors we have a minimum of $bn+n$ beads. $\textbf{Case 2: All others do not work}$ Start with the configuration of $bn$ such that for any $n$ consecutive beads we have every color. We insert a bead of any color directly before a certain color. Since we have that $b \geq c$ we can obviously that that certain color will repeat at least $c$ times. $\blacksquare$

We claim $m \leq n(n-1)-1$. We first construct a solution for $m > n(n-1)-1$. Number the colors $1$ through $n$ and denote $A$ by the coloring $123\ldots n$. Consider the case $m = n(n-1) + (n-1)$. Then the coloring \[ C = 1A \ nA \ nA \ nA \ldots nA \]with $n-2$ `$nA$'s works. For $m = n(n-1) + k$ where $0 < k < n$, simply remove any $n-1-k$ `$n$'s from $C$. If $k=0$ remove the `$1$' as well. This means every number between $n(n-1)$ and $n(n-1) + n-1$ inclusive is achievable. Now note that we can always add as many $A$s as we want to the back of $C$, which increase the number of beads by $n$. This implies every $m \geq n(n-1)$ is attainable. We now show $m = n(n-1) - 1$ fails. Let $a$ be the color that appears the least times, then by Pigeonhole Principle $a$ appears at most $\lfloor\frac{m}{n}\rfloor$ times. The gap between two consecutive beads of color $a$ cannot be $> n$. Hence there can only be at most \[ \underbrace{n \lfloor\frac mn\rfloor}_{\text{from the gap}} + \underbrace{\lfloor\frac mn\rfloor}_{\text{beads of color $a$}} = (n+1) \lfloor\frac mn\rfloor \]beads. But when $m = n(n-1) - 1$, \[ (n+1) \lfloor\frac mn\rfloor = (n+1) \lfloor n-1-\frac{1}{n} \rfloor = (n+1) (n-2) < m, \]a contradiction. Hence $m = n(n-1) - 1$ fails and we are done.

The answer is $n^2 - n - 1$. Number the colours from $1$ to $n$.We say that a bead $r$ is $k$-saturated if one can start from some bead of colour $k$, go no more than $n$ (possibly zero) steps clockwise, and reach $r$. The required task is equivalent to making every bead saturated by every colour. We first prove that the task is not possible if $m = n^2 - n - 1$. By the Pigeonhole Principle, there is a colour $k$ for which at most $\left\lfloor \frac{n^2 - n - 1}{n} \right\rfloor = n - 2$ beads are of colour $k$. But then at most $(n-2)(n+1)$ beads are $k$-saturated. Since $(n-2)(n+1) < n^2 - n - 1$, there exists some bead which is not $k$-saturated so the task is not possible. Now we prove that the task is possible if $m \geq n^2 - n$. Since $\gcd(n, n+1) = 1$ and $m > n^2 - n - 1 = n(n+1) - n - (n+1)$, by the Chicken McNugget Theorem there exists nonnegative integers $a, b$ such that $an + b(n+1) = m$. For a string of beads $C$ with bead colours $(1, 2, ..., n)$ and $D$ with bead colours $(1, 2, ..., n, n)$, construct the necklace by connecting $a$ copies of $C$ followed by $b$ copies of $D$ in clockwise order. It is easy to see that each bead is saturated by every colour. (The $j$-th bead of a string is $k$-saturated by the $k$-th bead from the same string if $j \geq k$, and from the previous string if $j < k$. )

The answer is $n^2 - n - 1$. Proof that everything bigger works: Denote the colors by $A_1, A_2, \dots, A_n$. Prefabricate several strings $A_1 A_2 \dots A_n$ (length $n$) and several strings $A_1 A_1 A_2 \dots A_n$ (length $n+1$). Due to the Chicken McNugget theorem, we will be able to construct necklaces of length $n^2 -n$ and greater using just these two strings. If we do so, clearly, no string of $n+1$ beads on such a necklace will contain three $A_1$'s; even more clearly, no string will contain three $A_2$'s, $\dots, A_n$'s. So, this construction is valid. Proof that $n^2 - n -1$ beads doesn't work: If we have $n^2 - n -1$ beads, each color will appear an average of $\frac{n^2 - n-1}{n} = n-1 - \epsilon$ times, so some color will appear no more than $n-2$ times. Let $a$ be the number of times this color appears, so $a \leq n- 2$. Then, if we pick a random consecutive string of $n+1$ beads, this color will appear an average of \[a \cdot \frac{n+1}{n^2 - n - 1} \leq \frac{(n-2)(n+1)}{n^2 - n -1} = \frac{n^2 - n -2}{n^2 - n - 1} < 1\]times, so we can pick some string of $n+1$ beads where this color doesn't appear.

I hope this is OK.... Claim: if $m\ge n(n-1)$ we can always color the beads. Proof: Clearly for $m\equiv 0 \pmod{n}$ we can achive that by alternating the colors so let $m\equiv k \pmod{n}$. Consider the following construction : $$\underbrace{1,2,3\cdots n,\bullet,1,2,3\cdots n,\bullet,\cdots\cdots\cdots,\bullet,1,2,3\cdots n,\bullet,1,2,3\cdots n,\bullet}_{m \text{ (there are k black dots)}} $$Note that since $m\ge n(n-1)$ $k$ can go up to $n-1$ Claim: We can't color $n(n-1)-1$ beads. Proof: From pigeonhole principle there exists a color that has been used at most $\left\lfloor\frac{n^2-n-1}{n}\right\rfloor=n-2$ times. And since every bead covers at most $n$ other beads we get $(n+1)(n-2)=n^2-n-2 < n(n-1)-1$ hence a contradiction

The answer is $\frac{n^2}{2} - \frac{3n}{2}+1$ total values of $m$ that aren't possible, with maximum value of $n^2-n-1$. Specifically, I claim it is possible iff $m$ can be written in the form $an+b$ with $b<n$, $b\leq a$. The first direction of this is true by cycling all colors around $a$ times and then doubling the same color $b$ times to get a valid necklace. Now suppose $b>a.$ By pigeonhole, there must be a rare color, only appearing at most $a$ times. Now, select one bead of the rare color. As $m=an+b>a(n+1)$, we can divide the rest of the necklace not containing the selected bead into $a$ sections of $n+1$ beads possibly with remainder but that won't matter. Each of these sections must have a bead of rare color, but there are $a$ such sections giving a total of $\geq a+1$ beads of said rare color, contradiction.

The answer is $\boxed{n^2-n-1}$. Construction. If $m>n^2-n-1$, then it can be expressed as $an+b(n+1)$ for some nonnegative integers $a$ and $b$. Then it suffices to stitch together $a$ chains of $1,2,3,\dots,n$ and $b$ chains of $1,2,3,\dots,n,1$. Proof. Suppose that $n^2-n-1$ is possible. Then consider any substring of length $n+1$. It must have exactly one duplicate, so say it is $AxBxC$ where $A,B,C$ are strings and $x$ is one number. Then after this, the string must go $AxBxCA$, and $BxCA$ is a rainbow string of length $n$. Now assume WLOG that the numbers start from this rainbow string. Let them be $a_1,a_2,\dots,a_{n^2-n-1}$. Then assume WLOG that $a_1=1,a_2=2,\dots,a_n=n$. Then between $a_{n+1}$ and $a_{n+2}$(inclusive, I will only specify this once but I will always mean inclusive) there must be a $1$, between $a_{n+3}$ and $a_{2n+3}$ there must be a $1$, between $a_{2n+4}$ and $a_{3n+4}$ there must be a $1$, etc until between $a_{n^2-2n-1}$ and $a_{n^2-n-1}$ there must be a $1$. Thus there must be at least $n-1$ $1$s in the string. For similar reasons(the only difference should be that there must be a $2$ between $a_{n^2-2n}$ and $a_{n^2-n-1}$ because the string wraps around), there must be $n-1$ of every digit in the string, so there must be at least $n^2-n$ digits in the string, contradiction. $\blacksquare$

Very easy problem, solved from OTIS equality handout The answer is $\frac{(n-1)(n-2)}{2}$ total values of $m$ that aren't possible, with maximum value of $n^2-n-1$. It's only possible iff $m$ can be written in the form $an+b:b<n,b\leq a$. The first direction of this is true by cycling all colors around $a$ times and then doubling the same color $b$ times to get a valid necklace. Now suppose $b>a.$ By pigeonhole, there must be a color c appears at most $a$ times. Now, we'll show that there is some length >n+1 between two consecutive colors of c beads, from which it would follow that taking n+1 of those misses the color c; in particular, for b=2 we have 1 value, all the way until b=. Indeed, FTSOC not then they only span at most $(n+1)a=an+a<an+b$, contradiction! i copied grantstar construction wording cuz i didnt know how to phrase it and forgot to change it oops ill just say, Cycle over all colors with some $b\le a$ empty spaces in between each cycle; that is, 1,2,...,n _ 1,2,...,n ..., which works by placing any color we want in the blank (since we only need to place b extra beads but we have a empty spaces)

When $m=n^2-n-1$, the task is not possible. Form $n-1$ blocks of $n+1$ consecutive beads, which proves each color appears with frequency at least $n-1$. Hence there are at least $n^2-n$ beads, contradiction. When $m>n^2-n-1$, we can write $m=cn+d(n+1)$ for nonnegative integers $c$ and $d$ by Chicken McNugget Theorem. Split beads into blocks of $n$ and $n+1$ accordingly, and paint blocks either \[\{1,\dots,n\}\]or \[\{1,\dots,n,1\}.\]For any two minimally close same-colored beads, there are at most two beads of color $1$ separating them. Each of the other $n-2$ colors appears at most once. Hence the gap is at most $n<n+1$ beads, which clearly solves.

We claim the maximum is $\boxed{n^2-n-1}$. First, we show that it is impossible to achieve a valid formation of $n^2-n-1$ beads and after that, we will prove for all $m \ge n^2-n$, it is possible to complete the task. Call the colors $C_1, C_2, \dots, C_n$. For $n^2-n-1$ beads, because of the Pigeonhole Principle, we know there must be at most $n-2$ of a certain $C_i$. Without loss of generality, assume that this is $C_1$. Notice that between every bead of color $C_1$, there must be at most $n$ beads. However, this means that there are at most \[n(n-2)+(n-2)=n^2-n-2\] beads, a contradiction. We will create two strings of beads with color arrangements $C_1C_2 \dots C_n$ and $C_1C_1C_2 \dots C_n$. By the Chicken McNugget Theorem, it is possible to create any string of length $m > N=n^2-n-1$ using just the two given strings, and it is easy to see that all strings of $n+1$ beads have at least one of every color. Thus, our proof is complete.

We claim that the minimum value of $m$ is $n^2 - n$. First, we will show that $m < n^2 - n$ is impossible. By Pigeonhole, we have $\frac{n^2 - n - 1}{n} < n - 2$, so there exists at least one color that shows up at most $n - 2$ times. $\newline$ Then, it follows that the total number of beads must be $ \leq (n - 2)(n + 1) = n^2 - n - 2 < n^2 - n - 1$, contradiction. $\newline$ We will now prove that $m \geq n^2 - n$ is achievable. Let $m = nq + r$. Then construct a bracelet with $n$ groups of n beads of different color, that are all arranged in the same way. For example, $RGBRGBRGB$ where the letters represent different colors. We can see that this satisfies the conditions as taking $n$ beads in a row results in each color appearing once, which is more sharp than taking $n + 1$ beads. $\newline$ Then place $r$ extra beads in between groups of beads, for example: $RGB B RGB R RGB B$ This clearly satisfies the conditions, as instead of $n$ consecutive beads we take $n + 1$ consecutive beads, but the extra beads make it equivalent to taking $n$ consecutive beads, so we are done. So, our answer is $n^2 - n - 1$.

Solved with mathboy100. The answer is $m = \boxed{n^2 - n - 1}$. Claim: $m = n^2 - n - 1$ fails. Proof. By pigeonhole we find that some color appears at most $\left\lfloor \frac{n^2 - n - 1}{n} \right\rfloor = n-2$ times, say $\ell$. Then note there are exactly $n^2 - n - 1$ distinct strings of $n + 1$ consecutive beads. In each of these, one specific bead of color $\ell$ appears in exactly $n + 1$ such strings. Thus at most $(n-2)(n+1) = n^2 -n - 2$ strings contain a bead of color $\ell$. However then there is at least one string of colors not containing a bead of color $\ell$ and we are done. $\square$ Construction: Now to show that all $m > n^2 - n - 1$. Say we have colors $c_1$, $c_2$, $\dots$, $c_n$. Then consider placing the beads upon the necklace in continuous groups of the form $\{c_1, c_2, \dots, c_n\}$ and $\{c_1, c_1, c_2, \dots, c_n\}$. Then by Chicken McNugget we may find a valid linear combination of $n$ and $n + 1$ summing to $m$. It is easy to see that this works as then between any two beads of the same color there are at most $n$ beads. Thus we are done. $\square$

Suppose $m = qn+r$, where $0 \leq r \leq n-1$, and let our colors be $1,2,3\ldots,n$. Note that we can provide a construction for many values of $m$ by using $q$ blocks of $[\underline{1}~\underline{2} \ldots \underline{n}]$, and adding a color $k$ adjacent to another color $k$ in the $k$th block, where $k \leq r$. This construction only works when $q \ge r$, as we cannot add two additional colors to a single block, so we now show it is necessary. By Pigeonhole, there must exist at least one color which appears at most $q$ times. By Linearity of Expectation, if \[(n+1) \cdot \frac{q}{qn+r} < 1 \iff qn+q < qn+r \iff q<r,\] it is impossible for each block of $n+1$ beads to contain this particular color. Hence the maximal value of $m$ which fails is \[n(n-2) + (n-1) = \boxed{n^2-n-1}. \quad \blacksquare\]

The answer is $n^2-n-1$. This value of $m$ fails as each color must appear at least $\frac{n^2-n-1}{n+1}$ times or equivalently $n-1$ times, requiring at least $n^2-n$ beads. Anything larger than be represented in blocks of $n$ and $n+1$; for blocks of $n$ color $\{1,\dots,n\}$ and for blocks of $n+1$ color $\{1,\dots,n+1\}$. $\blacksquare$

The answer is $m = n^2 - n - 1$. The task is not possible with this $m$: By pigeonhole, for any coloring of the necklace, there is a color $c$ that appears at most $n-2$ times. Therefore there are at least $n^2 - 2n + 1$ beads of colors other than $c$, divided into at most $n-2$ consecutive blocks. By pigeonhole at least one such block has size at least $n+1$, so we can find $n+1$ consecutive beads that do not contain the color $c$. The task is possible with larger $m$: Let $0 \le k < n$ be such that $m \equiv k \pmod{n}$. Then we can pick $k$ disjoint contiguous segments of size $n$ of the necklace, since $m \ge (n-1)n$. Let $S$ be the set of beads that are the first beads of some segment, so $|S| = k$. Assign an arbitrary color to all beads in $S$, and for the remaining beads (the number of them is a multiple of $n$), cycle from color $1$ to color $n$ in order. Any consecutive block of $n+1$ beads can contain at most one bead in $S$; the at least $n$ beads remaining will contain all $n$ colors.

Sol:- We first prove that the task is impossible for $m=n^2-n-1$. Let the colors be $c_1,c_2,..,c_n$. Clearly there exists a color $c_i : i \in \{1,...,n\}$ which is used atmost $n-2$ times since otherwise all colors would be used atleast $n-1$ times and $n(n-1)=n^2-n>n^2-n-1$ (exceeding total number of beads thus not possible).Let's say this color $c_i$ is used $a$ ($a \leq n-2$) times then by PHP there exists two beads consecutively colored with $c_i$ having atleast $\bigg \lceil{\frac{n^2-n-1-a}{a}} \bigg \rceil \geq \bigg \lceil{\frac{n^2-2n+1}{n-2}} \bigg \rceil =n+1$ beads of color different from $c_i$ between them. Thus the task is impossible for $m=n^2-n-1$. Now we give working construction for $m\geq n^2-n$. Express $m=ns+r$ where $r$ is its remainder when divided by $n$. Then we color $s+1$ beads with $c_i \forall i \in \{1,...,r\}$ and $s$ beads with $c_k \forall k \in \{r+1,...,n\}$. Firstly arrange the $ns$ beads in the necklace by concatenating the string of beads $c_1c_2...c_n$ $s$ times . Then for the remaning $r$ beads add the $c_i$ colored bead adjacent to the $c_i$ colored bead of the $i$'th "$c_1c_2...c_n$" string $\forall i \in \{1,..,r\}$. Note that any consecutive $n+1$ beads contains atmost $1$ repeated color in above construction and hence covers all $n$ colors. We are done.

For convenience, let a 'bead list' be any $n+1$ consecutive beads in the necklace. We know, by the pigeonhole principal, that some bead appears at most $\lfloor \frac{m}{n} \rfloor$ times. Let such a bead be $B,$ and have color $C_1.$ We know that in the $m-1$ remaining beads, every bead list contains at least one bead of color $C_1.$ Also, there are at most $\lfloor \frac{m-1}{n+1} \rfloor$ disjoint bead lists in these $m-1$ bead, each of which must contain a $C_1$ bead. Thus, we in total require at least $$\lfloor \frac{m-1}{n+1} \rfloor + 1$$of $C_1$ beads (but exactly this amount of $C_1$ beads will suffice). This gives the inequality (required beads is at most $m$) $$n(\lfloor \frac{m-1}{n+1} \rfloor + 1) \le m.$$In other words, $$m=n+1,$$$$2n, 2n+1, 2n+2,$$$$3n, 3n+1, 3n+2, 3n+3,$$$$\dots,$$$$kn, kn+1, kn+2, \dots, kn+k,$$$$\dots.$$From the first to second row of solutions, there are $n-2$ values for $m$ that do not work. From the second to third row, there are $n-3$ that do not work, and so on. Summing up the not working solutions, we get $$n-2 + n-3 + \dots + 1 = \boxed{\frac{(n-1)(n-2)}{2}}.$$

Let $m=nk+l$ where $0\leq l <n$ . We claim that it is possible to place $m$ bead as required if and only if $l\leq k$. First, consider when $l>k$. Notice that there clearly exists a color (say $C_1$) with at most $k$ beads of that color (if not there will be atleast $nk+n>nk+l=m$). If the gap between any two consecutive of these $k$ beads is greater than $n$, then a block of $n+1$ beads can be obtained which does not contain $C_1$ color. Thus, if there are at most $n$ beads between any two beads of color $C_1$, this means that we can have at most $$n = \text{ Other beads } + C_1 \text{ beads } \leq nk + k$$Thus, $m \leq nk + k < nk + l=m$ for $l >k$. Thus, it is clearly impossible to place $m$ beads as required in this case. Now, we shal show that when $l\leq k$, it is always possible to place $m$ beads in the required fashion. Clearly it is possible for all $m=nk$. Simply place $k$ continuous blocks of $C_1,C_2,\dots, C_n$ around the circle. As each consecutive block of $n+1$ beads contains a block of $n$ beads and the minimum gap between two beads of the same colour if $n+1$ as per the arrangement, we are guaranteed that this works. Now, if $m=nk + l$ where $l\leq k$, Place $nk$ beads as before. Notice that we have an arrangement where any $n$ beads are $C_1, C_2, \dots, C_n$ consecutively. Now place one bead each from any color say $(C_2)$, after every $C_1$ (until $l$ new beads have been added - since $l\leq k$ this is clearly possible). Now, notice that each of these 'new' $C_2$ beads has a block of $C_1, C_2, \dots , C_n$ between it self and the next 'new' $C_2$ bead. Thus, any block of $n+1$ consecutive beads containing a 'new' $C_2$ bead has 1 bead of each color and an extra $C_2$ bead. This satisfies the requirement. Any block of $n+1$ beads not containing a 'new' $C_2$ bead obviously has $n$ different colors which was shown before. Thus, for $m=nk+l$ where $l\leq k$ this task is clearly possible. Thus, when $l=i<n$, $k\in \{1,\dots, i-1\}$. Thus, the number of impossible values is $$v = 0 + 1 + 2 + \dots + n-2 = \frac{(n-2)(n-1)}{2}$$

The answer is $n^2-n-1$. This is not possible; for any color, it must appear at least $n-1$ times. Otherwise, if the color appears $n-2$ times or less, we find $\frac{n-2}{n^2-n-1}<\frac{1}{n+1}$, implying that---on average---the size of the gap between consecutive colors is larger than $n$, so that some gap has size $n+1$ or more, a contradiction. Hence at least $n(n-1)=n^2-n$ beads are necessary, so that $n^2-n-1$ beads fails. The construction for $m\ge n^2-n$ beads is simple. First construct $kn$ beads with $k\ge n-1$ by chaining $k$ blocks of $\{1,\dots,n\}$. Then to construct $kn+\ell$ for $1\le \ell\le n-1$ simply take the first $\ell\le k$ blocks of $\{1,\dots,n\}$ and add a bead of color $1$ afterward. The original gaps between beads of the same colors were $n-1$---now, the gaps increase by at most $1$, yielding gaps of size $n$. This is still valid, and we are done. $\blacksquare$ My solution easily solves the question asking for the number of invalid numbers, using the same two arguments of fail-check by Pigeonhole-esque logic + the construction.