Painting Beads on Necklace

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

amuthup

779 posts

amuthup

#1 h Jul 12, 2022, 12:24 PM • 1 Y

Y by Mango247

Let $n\ge 3$ be a fixed integer. There are $m\ge n+1$ beads on a circular necklace. You wish to paint the beads using $n$ colors, such that among any $n+1$ consecutive beads every color appears at least once. Find the largest value of $m$ for which this task is $\emph{not}$ possible.

Carl Schildkraut, USA

This post has been edited 2 times. Last edited by amuthup, Jul 15, 2022, 4:06 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Assassino9931

1220 posts

Assassino9931

#2 h Jul 12, 2022, 12:30 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Quidditch

815 posts

Quidditch

#3 h Jul 12, 2022, 12:33 PM

Y by

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.

This post has been edited 8 times. Last edited by Quidditch, Mar 18, 2023, 3:13 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Assassino9931

1220 posts

Assassino9931

#4 h Jul 12, 2022, 12:36 PM • 4 Y

Y by PRMOisTheHardestExam, Sandro175, cubres, MS_asdfgzxcvb

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}$ .)

This post has been edited 2 times. Last edited by Assassino9931, Dec 6, 2022, 9:54 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Anzoteh

124 posts

Anzoteh

#5 h Jul 12, 2022, 12:39 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

adj0109

17 posts

adj0109

#6 h Jul 12, 2022, 1:03 PM • 1 Y

Y by sabkx

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Orestis_Lignos

555 posts

Orestis_Lignos

#7 h Jul 12, 2022, 1:10 PM • 2 Y

Y by ike.chen, trying_to_solve_br

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DottedCaculator

7326 posts

DottedCaculator

#8 h Jul 12, 2022, 1:14 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

isaacmeng

113 posts

isaacmeng

#9 h Jul 12, 2022, 1:18 PM • 3 Y

Y by Mango247, Mango247, Mango247

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

This post has been edited 4 times. Last edited by isaacmeng, Jul 13, 2022, 9:16 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

VicKmath7

1386 posts

VicKmath7

#10 h Jul 13, 2022, 7:12 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MarkBcc168

1594 posts

MarkBcc168

#11 h Jul 14, 2022, 9:19 AM • 1 Y

Y by Ritwin

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.

This post has been edited 2 times. Last edited by MarkBcc168, Jul 14, 2022, 9:19 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CyclicISLscelesTrapezoid

372 posts

CyclicISLscelesTrapezoid

#12 h Jul 16, 2022, 3:31 AM • 1 Y

Y by mijail

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

This post has been edited 1 time. Last edited by CyclicISLscelesTrapezoid, Nov 12, 2023, 5:06 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1691 posts

awesomeming327.

#13 h Jul 22, 2022, 1:03 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Shayan-TayefehIR

104 posts

Shayan-TayefehIR

#14 h Jul 26, 2022, 3:37 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ike.chen

1162 posts

ike.chen

#15 h Jul 28, 2022, 8:39 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7586 posts

asdf334

#34 h Dec 21, 2023, 3:43 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2513 posts

joshualiu315

#35 h Dec 22, 2023, 9:00 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dolphinday

1318 posts

dolphinday

#36 h Jan 6, 2024, 6:05 PM

Y by

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

This post has been edited 1 time. Last edited by dolphinday, Jan 10, 2024, 12:03 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Shreyasharma

667 posts

Shreyasharma

#37 h Jan 16, 2024, 2:28 AM • 2 Y

Y by mathboy100, GeoKing

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$

This post has been edited 1 time. Last edited by Shreyasharma, Jan 16, 2024, 2:33 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

793 posts

shendrew7

#38 h Feb 7, 2024, 5:05 AM • 1 Y

Y by GeoKing

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7586 posts

asdf334

#39 h Apr 28, 2024, 2:00 AM • 1 Y

Y by GeoKing

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SHZhang

109 posts

SHZhang

#41 h Aug 15, 2024, 4:47 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GeoKing

515 posts

GeoKing

#42 h Aug 15, 2024, 10:45 PM

Y by

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.

This post has been edited 1 time. Last edited by GeoKing, Aug 15, 2024, 10:48 PM
Reason: ..

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bebebe

985 posts

bebebe

#43 h Aug 23, 2024, 1:47 AM • 1 Y

Y by GeoKing

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

569 posts

cursed_tangent1434

#44 h Dec 22, 2024, 10:06 AM

Y by

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}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7586 posts

asdf334

#45 h Dec 23, 2024, 4:34 PM

Y by

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.

This post has been edited 1 time. Last edited by asdf334, Dec 23, 2024, 4:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

525 posts

Maximilian113

#46 h Jan 29, 2025, 10:20 PM

Y by

We claim that the answer is $n^2-n-1.$

We first show the bound, ie every necklace with more than $n^2-n-1$ beads works. Notice that we can append $a$ blocks of $\{1, 2, 3, \cdots, n \}$ and $b$ $\{ 1, 2, 3, \cdots, n, 1 \}$ together to form a valid necklace of $an+b(n+1)$ beads. By the Chicken McNugget Theorem, it follows that $n(n+1)-n-(n+1) = n^2-n-1$ is the largest number not expressible by a sum of the two lengths. Thus the bound is proven.

Now, we show that $n^2-n-1$ beads fails. Observe that we can partition this into $n-2$ contiguous blocks of $n+1$ beads, therefore each bead must appear at least $n-2$ times. However, if there is a bead that appears exactly $n-2$ times, we have $n^2-2n+1$ other beads not of that color. There are $n-2$ "gaps" between beads of this specific type, therefore by the pigeonhole principle there is some gap that is at least $\left \lceil \frac{n^2-2n+1}{n-2} \right \rceil = n+1$ in size, which is a clear contradiction. Therefore, each bead appears at least $n-1$ times. But this is impossible as then we need at least $n^2-n > n^2-n-1$ beads, so $n^2-n-1$ beads fails.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Warideeb

59 posts

Warideeb

#47 h Feb 20, 2025, 4:46 AM

Y by

Wow first time solving a combi with mcnugget theorem

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

hgomamogh

39 posts

hgomamogh

#48 h Mar 12, 2025, 3:28 AM

Y by

Let $m$ be a positive integer such that $m$ can be written as $x(n) + y(n + 1)$ for positive integers $x$ and $y$ . Then, we claim that $m$ satisfies the problem statement. For the construction, color the first bead $C_1$ , the second bead $C_2$ , and so on until coloring the $n$ th bead $C_n$ . Repeat this $x - 1$ more times. Then, color the $xn+1$ th bead $C_1$ , the $xn+2$ th bead $C_2$ , and so on until $xn+n$ . Here, color the $xn + n + 1$ th bead $C_n$ too. Repeat this $y - 1$ times. It is easy to check that this procedure works. The largest possible $m$ for which $m$ cannot be expressed as $xn + y(n + 1)$ is $n^2 - n - 1$ by the Chicken Mcnugget Theorem, so anything not satisfying the problem statement must be less than or equal to that.

We now claim that the answer is $n^2 - n - 1$ . Observe that among the $n$ colors, one of them (WLOG call this $C_1$ ) must have at most $n - 2$ beads. These at most $n - 2$ beads partition our necklace into at most $n - 2$ arcs, and these arcs have total length $n^2 - n - 1$ . Hence, it follows that the average length of these arcs is at least $(n^2 - n - 1)/(n - 2) > n + 1$ . Hence, there exists an arc with length at least $n + 2$ . Now, take the interior of this arc, which consists of at least $n + 1$ consecutive beads without $C_1$ , and we are done!

This post has been edited 1 time. Last edited by hgomamogh, Mar 12, 2025, 3:30 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

maromex

142 posts

maromex

#49 h Apr 2, 2025, 2:06 AM

Y by

We claim $m = n^2 - n - 1$ is the largest value of $m$ that achieves impossiblity.

First, we show that the task cannot be completed if $m = n^2 - n - 1$ . There are $n$ colors. Notice that $m = n(n-1) - 1$ , so by Pigeonhole Principle, there must be a color, call this color $C$ , that appears in the necklace at most $n-2$ times. Notice that $m = (n-2)(n+1) + 1$ , so by Pigeonhole Principle, there must exist $n+1$ consecutive beads that are not color $C$ , thus failing the task.

Second, we show that the task can be completed if $m > n^2 - n - 1$ . This is equivalent to $m \ge n^2 - n$ . Let $q, r$ be nonnegative integers such that $r \le n-1$ and $m = qn + r$ ; that is, when $m$ is divided by $n$ , the quotient is $q$ with remainder $r$ . Observe that $\frac{m}{n} \ge n - 1$ . This shows that $q \ge n-1 \ge r$ ; the takeaway here is that $q \ge r$ . Let $C_1, C_2, C_3, \ldots C_n$ be the $n$ colors to choose from. Choose an arbitrary bead of the necklace to be position $0$ ; all positions will be taken $\pmod m$ . Color the bead at position $i(n+1) + k$ the color $C_k$ for all $0 \le i \le r-1$ for all $1 \le k \le n$ . Also, color the bead at position $r(n+1) + k + in$ the color $C_k$ for all $0 \le i \le q-r$ for all $1 \le k \le n$ . If we set $i = q - r$ here, the position is $qn + r + k$ , which equals $m + k$ , which, $\pmod m$ , is the same as position $k$ . We have already colored position $k$ the color $C_k$ , so this works out. By construction, this necklace has the property that, for any bead colored $C_k$ at position $p$ , the next bead colored $C_k$ is either at position $p+n+1$ or position $p+n$ . Thus, any $n+1$ consecutive beads must have the color $C_k$ appear at least once, completing the task.

Z K Y