Fix $n$. We claim that all $m \le n + 1$ works. Construction Call a $k$-filled block consisting of $k$ reds followed by $n-k$ blues. Then take a $n$-filled block, then an $n-1$ filled block, all the way to an $n+1-m$ filled block. Now, fix the $m$ blocks and rotate these blocks one by one. Call the history of a block the $n+1$ number of reds it has under a rotation. If the history of blocks always have distinct numbers, we win. Let's characterize these blocks. Claim: For an $a$-filled block where $a \ne n+1-m$, the history has $a$ occurences of $a$ followed by $n+1-a$ occurences of $a-1$. Proof. Look at it. $\blacksquare$ Claim: When $a = n+1-m$, the history has $a+1$ occurences of $a$ followed by $a+1, a+2, \dots, n$. Proof. The math works out because we have $a+1 + (n-a) = n+1$ elements in this history. $\blacksquare$ Create a table with all the histories in a row. Then we can check that each number in $n+1-m, \dots, n$ appears once in each table, with the $a = n+1-m$ handling when it is "missing" from the other histories. This gives us our construction. Here's the history table for $n = 4, m = 4$. \begin{tabular}{ccccc} 4 & 4 & 4 & 4 & 3 \\ \hline 3 & 3 & 3 & 2 & 2 \\ \hline 2 & 2 & 1 & 1 & 1 \\ \hline 1 & 1 & 2 & 3 & 4 \\ \end{tabular} Necessity Note that by pigeonhole, since there are $m$ blocks and at most $n+1$ values for the number of reds, it follows that $m \le n+1$.

edit: sniped ok

@Aaryabhatta1 can you send your linearity of expectation masterpiece

$n \ge m-1$ easy to show w/ pigeonhole that if $n < m-1$ there are no solutions i just made a valid construction, proved it, and went to p2 and spent 4 hours on it :skull:

Answer same as previous posts. Except I used modulus for construction (mod n).

Dude I need the confidence to just go: TheHazard wrote: Proof. Look at it. $\blacksquare$

avisioner wrote: Dude I need the confidence to just go: TheHazard wrote: Proof. Look at it. $\blacksquare$ i mean its literally obvious xdd

if i'd solved this in the first five minutes like i should have then my bash on p5 would have been successful and my 000 would have been a 770

so i immediately got the bound $m\le n+1$ cuz its obvious. then i tried to construct small cases and somehow convinced myself $(m,n) =(3,2)$ failed so i got confused and did some random stuff to get a wrong answer :skull:.

Proving that the construction worked was so annoying

I don't think this has been posted but here's a sketch of my in-contest solution which I think is easier to prove than above? Induct, show that $(m,n-1)$ implies $(m,n)$ by taking an $(m,n-1)$ construction and inserting red beads at every $n$th position. It remains to prove $(m,m-1)$. The construction is to concatenate $m$ blocks, where the $i+1$th block has $m-1-i$ blue beads followed by $i$ red beads. To see that this works, track the number of red beads when you continually ``shift" all the blocks over by one. EDIT: Got $7$ points for this

We claim the answer is all $m,n$ with $m\le n + 1$. First we may label each with a $0$ if it is blue and a $1$ if it is red. Let $a_1, a_2, \ldots, a_{mn} $ be the labels of each bead starting from any fixed bead and going clockwise (as in the beads corresponding to $a_1, a_2, \ldots a_{mn}$ form the circle going clockwise in that order). The problem condition is equivalent to the values \[ \sum_{k=i}^{i + n - 1} a_k, \sum_{k = i + n} ^{i + (2n- 1) } a_k , \sum_{k = i + 2n }^{i + (3n-1) } a_k, \ldots, \sum_{k = i + (m-1)n } ^{i + (mn - 1) } \]all being distinct, where indices are being taken modulo $mn$ and $i$ is an integer in $[1,mn]$ (since the number of red beads in a set is just the sum of its labels). Claim: $m\le n + 1$. Proof: Suppose $m > n + 1$. Then any block of $n$ consecutive beads has a sum in the interval $[0,n]$. However, if there were exactly $m$ blocks with $m > n + 1$, then by Pigeonhole, at least two of them would have the same sum of labels as there are only $n + 1$ integers in $[0,n]$. Hence $(m,n)$ fails if $m > n + 1$. $\square$ Now we give a construction for $m \le n +1 $. For each nonnegative integer $x < m$, let \[ a_{xn + 1} = a_{xn + 2} = \cdots = a_{xn + (n-x) } =0 \]and \[ a_{xn + (n-x) + 1} = a_{xn + (n-x) + 2} = \cdots = a_{(x+1) n } = 1\] In particular \begin{align*} a_1 = a_2 = \cdots = a_n =0 \\ a_{n+1} = a_{n+2} = \cdots = a_{2n - 1} = 0 \\ a_{2n} = 1, a_{2n + 1} = a_{2n+ 2} = \cdots = a_{3n - 2} = 0 \\ a_{3n - 1} = a_{3n} = 1\\ \cdots \\ \end{align*} Now we compute \[ f(q,i) = \sum_{k = qn + i} ^{(q+1) n + i - 1} a_k \] Case 1: $i \le n - q$ Then since $i - 1 \le n - (q + 1)$, \[ \sum_{k=(q + 1) n + 1}^{(q+1) n + i - 1} = 0 \](vacuously true for $i =1$). Also, since $i \le n - q$, \[ \sum_{k = qn + i}^{(q+1)n} a_k = \sum_{k = qn + (n-q) + 1} ^{(q+1) n } a_k = q\], hence $f(q,i) = q$. Case 2: $n - i < q < m - 1$ (if possible). We have \[ \sum_{k = (q+1) n + 1} ^{(q+1) n + (i - 1) } a_ k = \sum_{k = (q+1) n + (n - (q + 1)) + 1} ^{(q+1) n + (i - 1) } a_k = 1 + (i-1) + (q-n) = i + q - n \]Then since $i > n - q$ (and $i \le n$) \[ \sum_{k = qn + i}^{q(n+1)} a_k = ((q+1) n - (qn + i) ) + 1 = n - i + 1\]Hence \[ \sum_{k = qn + i} ^{(q+1) n + (i- 1) } = q + i - n - 1 + (n - i + 1) + 1 = q + 1 \] Case 3: $q = m - 1$ (only if $n - i < m - 1 $): Then \[ \sum_{k=(q+1) n }^{(q+1) n + (i -1) } a_k = 0 \text{ and } \sum_{k = qn + i } ^{(q+1) n} a_k = ((q+1) n - (qn + i) + 1) = n - i + 1\] Hence if $n - i \ge m-1$, then $f(q,i) = q$ for all $q$, and if $n - i < m - 1$, $f(q,i) = q$ for all $q < n - i$ and $q + 1$ if $n - 1 < q < m-1$ and $n - i + 1$ if $q = m-1$. Hence $f(q,i)$ is distinct over $ 0\le q \le m-1$, so this construction works.

Answer. The answer is for all pairs \((m,n)\) satisfying \(m \leq n+1\). Necessity. Neccesity directly follows from the pigeonhole principle as there can only be \(n+1\) different numbers of red beads in \(n\) consecutive beads, namely all integers from 0 to \(n\) (included). Construction. We first consider the construction for the case \(m = n+1\). Partition the necklace in any \(m\) blocks of \(n\) consecutive beads like in the solution. Colour all \(n\) beads in any block \(b_n\) red. Now, colour the \(n-1\) leftmost beads in the block \(b_{n-1}\) to the right red, colour the \(n-2\) leftmost beads in the next block \(b_{n-2}\) to the right red, and so on. We are left with a block \(b_0\) with only blue beads, which is to the left of the block \(b_n\). Call the original partition \(p_0\). Proof that Construction works. We now let the partition \(p_k\) (\(0 \leq k < n\)) denote the partition where the first \(k\) beads in any block in \(p_0\) now belong to the block to the left. Note that the number of red beads in block \(b_i\) (\(0 < i \leq n\)) is \(i\) if \(k < i\), and \(i-1\) otherwise, while the number of red beads in block \(b_0\) is \(k\). Consequently, increasing \(k\) by 1 causes the number of red beads to switch between \(b_k\) and \(b_0\). This means that the number of red beads is distinct for each block, so the construction works. Final Step. We can now use induction to proof that higher \(n\) also work. Assume that \(n\) works. Now add a blue bead at the right of each block. This increases \(n\) by 1, but leaves the condition of distinct red bead count untouched. This completes the proof. \(\square\)

Solution from Twitch Solves ISL: The answer is $m \leq n+1$ only. Proof the task requires $m \le n+1$. Each of the $m$ blocks has a red bead count between $0$ and $n$, each of which appears at most once, so $m \le n+1$ is needed. Construction when $m=n+1$. For concreteness, here is the construction for $n=4$, which obviously generalizes. The beads are listed in reading order as an array with $n+1$ rows and $n$ columns. Four of the blue beads have been labeled $B_1$, \dots, $B_n$ to make them easier to track as they move. \[ T_0 = \begin{bmatrix} {\color{red}R} & {\color{red}R} & {\color{red}R} & {\color{red}R} \\ {\color{red}R} & {\color{red}R} & {\color{red}R} & {\color{blue}B_1} \\ {\color{red}R} & {\color{red}R} & {\color{blue}B} & {\color{blue}B_2} \\ {\color{red}R} & {\color{blue}B} & {\color{blue}B} & {\color{blue}B_3} \\ {\color{blue}B} & {\color{blue}B} & {\color{blue}B} & {\color{blue}B_4} \end{bmatrix}. \]To prove this construction works, it suffices to consider the $n$ cuts $T_0$, $T_1$, $T_2$, \dots, $T_{n-1}$ made where $T_i$ differs from $T_{i-1}$ by having the cuts one bead later also have the property each row has a distinct red count: \[ T_1 = \begin{bmatrix} {\color{red}R} & {\color{red}R} & {\color{red}R} & {\color{red}R} \\ {\color{red}R} & {\color{red}R} & {\color{blue}B_1} & {\color{red}R} \\ {\color{red}R} & {\color{blue}B} & {\color{blue}B_2} & {\color{red}R} \\ {\color{blue}B} & {\color{blue}B} & {\color{blue}B_3} & {\color{blue}B} \\ {\color{blue}B} & {\color{blue}B} & {\color{blue}B_4} & {\color{red}R} \\ \end{bmatrix} \quad T_2 = \begin{bmatrix} {\color{red}R} & {\color{red}R} & {\color{red}R} & {\color{red}R} \\ {\color{red}R} & {\color{blue}B_1} & {\color{red}R} & {\color{red}R} \\ {\color{blue}B} & {\color{blue}B_2} & {\color{red}R} & {\color{blue}B} \\ {\color{blue}B} & {\color{blue}B_3} & {\color{blue}B} & {\color{blue}B} \\ {\color{blue}B} & {\color{blue}B_4} & {\color{red}R} & {\color{red}R} \end{bmatrix} \quad T_3 = \begin{bmatrix} {\color{red}R} & {\color{red}R} & {\color{red}R} & {\color{red}R} \\ {\color{blue}B_1} & {\color{red}R} & {\color{red}R} & {\color{blue}B} \\ {\color{blue}B_2} & {\color{red}R} & {\color{blue}B} & {\color{blue}B} \\ {\color{blue}B_3} & {\color{blue}B} & {\color{blue}B} & {\color{blue}B} \\ {\color{blue}B_4} & {\color{red}R} & {\color{red}R} & {\color{red}R} \end{bmatrix}. \]We can construct a table showing for each $1 \le k \le n+1$ the number of red beads which are in the $(k+1)$st row of $T_i$ from the bottom: \[ \begin{array}{c|cccc} k & T_0 & T_1 & T_2 & T_3 \\ \hline k=4 & 4 & 4 & 4 & 4 \\ k=3 & 3 & 3 & 3 & 2 \\ k=2 & 2 & 2 & 1 & 1 \\ k=1 & 1 & 0 & 0 & 0 \\ k=0 & 0 & 1 & 2 & 3 \end{array}. \]This suggests following explicit formula for the entry of the $(i,k)$th cell which can then be checked straightforwardly: \[ \#(\text{red cells in }k\text{th row of } T_i) = \begin{cases} k & k > i \\ k-1 & i \ge k > 0 \\ i & k = 0. \end{cases} \]And one can see for each $i$, the counts are all distinct (they are $(i, 0, 1, \dots, k-1, k+1, \dots, k)$ from bottom to top). This completes the construction. Construction when $m < n+1$. Fix $m$. Take the construction for $(m,m-1)$ and add $n+1-m$ cyan beads to the start of each row; for example, if $n = 7$ and $m = 5$ then the new construction is \[ T = \begin{bmatrix} {\color{cyan}C} & {\color{cyan}C}& {\color{cyan}C} & {\color{red}R} & {\color{red}R} & {\color{red}R} & {\color{red}R} \\ {\color{cyan}C} & {\color{cyan}C}& {\color{cyan}C} & {\color{red}R} & {\color{red}R} & {\color{red}R} & {\color{blue}B_1} \\ {\color{cyan}C} & {\color{cyan}C}& {\color{cyan}C} & {\color{red}R} & {\color{red}R} & {\color{blue}B} & {\color{blue}B_2} \\ {\color{cyan}C} & {\color{cyan}C}& {\color{cyan}C} & {\color{red}R} & {\color{blue}B} & {\color{blue}B} & {\color{blue}B_3} \\ {\color{cyan}C} & {\color{cyan}C}& {\color{cyan}C} & {\color{blue}B} & {\color{blue}B} & {\color{blue}B} & {\color{blue}B_4} \end{bmatrix}. \]This construction still works for the same reason (the cyan beads do nothing for the first $n+1-m$ shifts, then one reduces to the previous case). If we treat cyan as a shade of blue, this finishes the problem.

Note we must have $m \leq n + 1$ due to pigeonhole. Now consider the following construction. If $m = 2$ just place a single red bead anywhere on the necklace. Otherwise consider the construction, \begin{align*} \sum_{i = 0}^{m - 1} \underbrace{R \dots R}_{n - i \text{ beads}}\underbrace{B \dots B}_{i \text{ beads}} \end{align*}where addition denotes appending the strings, and the necklace loops back on itself in a clockwise manner. To see this works begin by partitioning the necklace in the parts shown above. Namely let block $b$ be $b$ consecutive red beads, and $i - b$ blue beads following it. Then if we rotate our blocks by $k$ clockwise block $i$ has, \begin{align*} (\# \text{ red beads in block } b) = \begin{cases} b & k < b\\ b - (k - b + 1) & b \leq k < n \end{cases} \end{align*}Now note if the number of beads in block $i$ and $j$ are equal then we have three cases to check, Both $i, j < k$ and hence $i = j$ which is a contradiction. Without loss of generality $i \geq k$ and $j < k$ which forces $i - (k - i + 1) = j$ which simplifies to $2i = j + k + 1$. However as $i \geq k$ this forces $k - 1 \leq j$ a contradiction. Both $i, j > k$ which forces $i - (k - i + 1) = j - (k - j) + 1$ which forces $i = j$. Thus the construction works and we're done.

Just for reference, this is USAMO 2024, problem 4.

I thought we had a thread already..