2023 CMO(CHINA) Problems/Problem 3
Problem
Given a prime number , let . For any , define:
For a non-empty subset of , define:
A subset of is called a "good subset" if and for any subset of with , it holds that . Find the largest positive integer such that there exist pairwise distinct good subsets of satisfying
Solution 1
Given a prime not less than 5 , define the directed distance between two points as , taking the smallest non-negative remainder. For any non-empty proper subset of , define
We call a non-empty proper subset a "good set" if and only if (where the \# symbol denotes the number of elements). Find the largest positive integer such that there exists a chain of good sets
Related Problems/Lemma 1: Given positive integers and , let be integers summing to . Find the necessary and sufficient condition for to attain its minimum possible value. Proof of Lemma 1: Since there are only finitely many ways to choose , there must be a minimum value. The assertion is: For the minimum value, for any . Otherwise, suppose . Then we can replace and with and , respectively, reducing the objective function, which contradicts minimality. Thus, the assertion holds, and the minimum is achieved when there are numbers equal to and numbers equal to , where and come from the division with remainder:
Lemma 2: For any and any real number , the set consisting of the following elements is a good set: (The notation denotes the floor function; indices taken modulo ). Furthermore, if the values of all are taken modulo to the smallest positive remainder, the conclusion still holds for any real number .
Proof of Lemma 2: For integers , we have , which is at least and at most . Note that (using that is prime), meaning there are at most two adjacent values. For a set with , we have interpreted modulo . It is easy to verify that . According to Lemma 1 , the minimum possible value of is achieved when (sufficient but not necessarily necessary in general). Thus, under the constraint of fixed element numbers, these minimize , proving Lemma 2.
Lemma 3: Continuing from Lemma 2's notation, if is a good set with , then the multiset and both satisfy the necessary and sufficient condition from Lemma 1. Proof of Lemma 3: A good set must satisfy thus all and by Lemma 1 (necessary and sufficient condition for minimizing the sum of squares), they are equal as multisets.
Lemma 4: The complement of a good set is also a good set.
Proof of Lemma 4: which only depends on \#A, not the specific elements. Thus, the minimality of is equivalent to the minimality of when fixing the number of elements, making both good sets.
Returning to the original problem: First, in the case of non-Mersenne primes (i.e., ), construct a chain of good sets of length . Choose any and denote taking the smallest positive remainder. According to Lemma 2, for each given , the above forms a good set denoted as . Construct a chain of good sets of length (choosing the same ):
Their containment is quite obvious: in fact, . The key is how to connect the good set of elements to the good set of elements. In fact, let taking the smallest positive remainder). It is easy to verify . Obviously, is also a good set, so is also a good set with elements and contains . We only need to let to complete the construction of the chain of good sets of length . For Mersenne primes (i.e., ), we need to construct a chain of good sets of length . Choose any , and according to Lemma 2 , the good set of elements is denoted as as . Let . Note that the intervals between elements of are 1 and all 2 , so and contains one less element. We alternately split the elements of into two parts: which are disjoint and both good sets (Lemma 2), with one part contained in (corresponding to or ). Define them as and let and then let which are all good sets by Lemma 4, thus constructing a chain of good sets of length .
Now prove the optimality of . We attempt to estimate the gap: if , and are both good sets with and , we will prove . We use contradiction. Suppose . Consider the interval composition of elements of (in the ring), assuming they are some number and some number . Since the number of new points in (i.e., ) is fewer than in , they cannot exist between each pair of elements in , so the interval composition of elements in must include or . If the interval composition of includes , then splitting the interval in will result in an interval less than , contradicting being a good set (Lemma 1). Thus, the interval composition of elements in can only be and (note ). But splitting an interval of in results in intervals still within and , so , contradiction.
If , and are both good sets with and but , similarly to the above reasoning, we infer: the interval composition of elements in must be 4 or 3 , and the interval composition of elements in must be 3 or 2 . The elements of must all divide the intervals of length 4 in .
We further assert that (or ) does not contain two adjacent intervals of length 3. Otherwise, the "sum of lengths of two adjacent segments" in will simultaneously include 4, 5, and 6, contradicting the characterization of good sets by Lemma 3.
We further assert: the number of intervals of length 3 in (or ) must be 1 . Otherwise, let the number of intervals of length 3 be , and the number of intervals of length 4 between any two elements in be positive integers (they split into twice as many intervals of length 2 in ), satisfying
Clearly, these are not all equal (since is prime). Let , consider the "sum of lengths of adjacent segments" in , which can span over intervals of length 2 and extend by one interval of length 3 on each side (note that some ), resulting in a total length of . But since not all are equal, at least one , so there exists adjacent intervals of length 2 in , with a total length of . This contradicts the characterization of good sets by Lemma 3.
That is, "in most cases", if , and are both good sets with \#A and \#B=b, then . The only exceptional case is , and .
Within the range of element numbers not exceeding , the number of elements in each in the chain of good sets is
When is a non-Mersenne prime, at most one number can appear in each of these sets; for Mersenne primes, the last set may contain at most 2 , while the others can contain only 1. This upper chain has a length of .
By Lemma 4, within the range of element numbers exceeding , the upper limit of the length of the chain of good sets is also , proving the overall upper limit.
~xiaohuangya|szm
See Also
2023 CMO(CHINA) (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All CMO(CHINA) Problems and Solutions |