Maths Olympiad Prep

Library / /82 of 115

Combinatorics Difficulty 7.5 National olympiad, round 2 Find the answer

Let mm and nn be positive integers. A circular necklace contains mnmn beads, each either red or blue. It turned out that no matter how the necklace was cut into mm blocks of nn consecutive beads, each block had a distinct number of red beads. Determine, with proof, all possible values of the ordered pair (m,n)(m, n).

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Given a circular necklace with mn mn beads, each being either red or blue, we need to determine all the possible values of the ordered pair (m,n)(m, n) such that when the necklace is cut into m m blocks of n n consecutive beads, each block has a distinct number of red beads.

### Analysis

1. Understanding the Problem:
We have a necklace with mn mn beads. We are tasked with cutting this necklace into m m segments, each containing n n consecutive beads. Each segment must have a distinct count of red beads. Since the necklace is circular, after the first m1 m-1 segments are defined, the remaining beads automatically determine the last segment.

2. Constraints:
- Each of the m m segments must have a unique count of red beads.
- The total number of blocks is m m , so the number of unique counts of red beads in these segments is also m m .

3. Maximizing Unique Segment Counts:
- The possible range for the number of red beads in a segment is from 0 to n n .
- For mn+1 m \leq n + 1 , it is possible to give each segment a unique number of red beads in this range.
- If m>n+1 m > n + 1 , we cannot find enough distinct numbers of red bead distributions within segments since we only have n+1 n + 1 possible distinct numbers (0 through n n ).

### Conclusion

Let's summarize our findings:
- Each segment can have between 0 and n n red beads.
- To ensure each configuration is unique, m m cannot exceed n+1 n + 1 .
- Hence, all possible ordered pairs (m,n)(m, n) that satisfy the conditions are such that mn+1 m \leq n + 1 .

Therefore, the solution is such that:
(m,n) is valid if mn+1. (m, n) \text{ is valid if } m \leq n + 1.

Thus, the final condition for the ordered pair is:
(m,n) such that mn+1 \boxed{(m, n) \text{ such that } m \leq n + 1}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.