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 |