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..