Let m and n be positive integers. A circular necklace contains mn beads, each either red or blue. It turned out that no matter how the necklace was cut into m blocks of n consecutive beads, each block had a distinct number of red beads. Determine, with proof, all possible values of the ordered pair (m,n). Proposed by Rishabh Das
Problem
Source:
Tags:
21.03.2024 07:01
Fix n. We claim that all m≤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≠n+1−m, the history has a occurences of a followed by n+1−a occurences of a−1. Proof. Look at it. ◼ Claim: When a=n+1−m, the history has a+1 occurences of a followed by a+1,a+2,…,n. Proof. The math works out because we have a+1+(n−a)=n+1 elements in this history. ◼ Create a table with all the histories in a row. Then we can check that each number in n+1−m,…,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≤n+1.
21.03.2024 07:05
@Aaryabhatta1 can you send your linearity of expectation masterpiece
21.03.2024 07:21
n≥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:
21.03.2024 07:24
Answer same as previous posts. Except I used modulus for construction (mod n).
21.03.2024 07:34
Dude I need the confidence to just go: TheHazard wrote: Proof. Look at it. ◼
21.03.2024 07:40
avisioner wrote: Dude I need the confidence to just go: TheHazard wrote: Proof. Look at it. ◼ i mean its literally obvious xdd
21.03.2024 17:32
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
21.03.2024 17:47
so i immediately got the bound m≤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:.
21.03.2024 17:54
Proving that the construction worked was so annoying
22.03.2024 04:42
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 nth position. It remains to prove (m,m−1). The construction is to concatenate m blocks, where the i+1th 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
22.03.2024 05:12
We claim the answer is all m,n with m≤n+1. First we may label each with a 0 if it is blue and a 1 if it is red. Let a1,a2,…,amn be the labels of each bead starting from any fixed bead and going clockwise (as in the beads corresponding to a1,a2,…amn form the circle going clockwise in that order). The problem condition is equivalent to the values i+n−1∑k=iak,i+(2n−1)∑k=i+nak,i+(3n−1)∑k=i+2nak,…,i+(mn−1)∑k=i+(m−1)nall 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≤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. ◻ Now we give a construction for m≤n+1. For each nonnegative integer x<m, let axn+1=axn+2=⋯=axn+(n−x)=0and axn+(n−x)+1=axn+(n−x)+2=⋯=a(x+1)n=1 In particular a1=a2=⋯=an=0an+1=an+2=⋯=a2n−1=0a2n=1,a2n+1=a2n+2=⋯=a3n−2=0a3n−1=a3n=1⋯ Now we compute f(q,i)=(q+1)n+i−1∑k=qn+iak Case 1: i≤n−q Then since i−1≤n−(q+1), (q+1)n+i−1∑k=(q+1)n+1=0(vacuously true for i=1). Also, since i≤n−q, (q+1)n∑k=qn+iak=(q+1)n∑k=qn+(n−q)+1ak=q, hence f(q,i)=q. Case 2: n−i<q<m−1 (if possible). We have (q+1)n+(i−1)∑k=(q+1)n+1ak=(q+1)n+(i−1)∑k=(q+1)n+(n−(q+1))+1ak=1+(i−1)+(q−n)=i+q−nThen since i>n−q (and i≤n) q(n+1)∑k=qn+iak=((q+1)n−(qn+i))+1=n−i+1Hence (q+1)n+(i−1)∑k=qn+i=q+i−n−1+(n−i+1)+1=q+1 Case 3: q=m−1 (only if n−i<m−1): Then (q+1)n+(i−1)∑k=(q+1)nak=0 and (q+1)n∑k=qn+iak=((q+1)n−(qn+i)+1)=n−i+1 Hence if n−i≥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≤q≤m−1, so this construction works.
28.03.2024 20:58
Answer. The answer is for all pairs (m,n) satisfying m≤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 bn red. Now, colour the n−1 leftmost beads in the block bn−1 to the right red, colour the n−2 leftmost beads in the next block bn−2 to the right red, and so on. We are left with a block b0 with only blue beads, which is to the left of the block bn. Call the original partition p0. Proof that Construction works. We now let the partition pk (0≤k<n) denote the partition where the first k beads in any block in p0 now belong to the block to the left. Note that the number of red beads in block bi (0<i≤n) is i if k<i, and i−1 otherwise, while the number of red beads in block b0 is k. Consequently, increasing k by 1 causes the number of red beads to switch between bk and b0. 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. ◻
13.04.2024 06:06
Solution from Twitch Solves ISL: The answer is m≤n+1 only. Proof the task requires m≤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≤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 B1, \dots, Bn to make them easier to track as they move. T0=[RRRRRRRB1RRBB2RBBB3BBBB4].To prove this construction works, it suffices to consider the n cuts T0, T1, T2, \dots, Tn−1 made where Ti differs from Ti−1 by having the cuts one bead later also have the property each row has a distinct red count: T1=[RRRRRRB1RRBB2RBBB3BBBB4R]T2=[RRRRRB1RRBB2RBBB3BBBB4RR]T3=[RRRRB1RRBB2RBBB3BBBB4RRR].We can construct a table showing for each 1≤k≤n+1 the number of red beads which are in the (k+1)st row of Ti from the bottom: kT0T1T2T3k=44444k=33332k=22211k=11000k=00123.This suggests following explicit formula for the entry of the (i,k)th cell which can then be checked straightforwardly: #(red cells in kth row of Ti)={kk>ik−1i≥k>0ik=0.And one can see for each i, the counts are all distinct (they are (i,0,1,…,k−1,k+1,…,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=[CCCRRRRCCCRRRB1CCCRRBB2CCCRBBB3CCCBBBB4].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.
22.04.2024 20:47
22.04.2024 22:14
Note we must have m≤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, m−1∑i=0R…R⏟n−i beadsB…B⏟i beadswhere 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, (# red beads in block b)={bk<bb−(k−b+1)b≤k<nNow 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≥k and j<k which forces i−(k−i+1)=j which simplifies to 2i=j+k+1. However as i≥k this forces k−1≤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.
09.05.2024 15:41
Just for reference, this is USAMO 2024, problem 4.
09.05.2024 15:54
I thought we had a thread already..