HMMT 二月 2017 · 团队赛 · 第 9 题
HMMT February 2017 — Team Round — Problem 9
题目详情
英文原题
- [ 65 ] Let n be a positive odd integer greater than 2, and consider a regular n -gon G in the plane centered
′
at the origin. Let a subpolygon G be a polygon with at least 3 vertices whose vertex set is a subset of
′ ′
that of G . Say G is well-centered if its centroid is the origin. Also, say G is decomposable if its vertexset can be written as the disjoint union of regular polygons with at least 3 vertices. Show that allwell-centered subpolygons are decomposable if and only if n has at most two distinct prime divisors.
解析
英文解析
- [ 65 ] Let n be a positive odd integer greater than 2, and consider a regular n -gon G in the plane centered
′
at the origin. Let a subpolygon G be a polygon with at least 3 vertices whose vertex set is a subset of
′ ′
that of G . Say G is well-centered if its centroid is the origin. Also, say G is decomposable if its vertexset can be written as the disjoint union of regular polygons with at least 3 vertices. Show that allwell-centered subpolygons are decomposable if and only if n has at most two distinct prime divisors.
Proposed by: Yang Liu
∏
⇒ , i.e. n has ≥ 3 prime divisors: Let n = p . Note it suffices to only consider regular p -gons.ieixnjni
Label the vertices of the n -gon 0 , 1 , . . . , n − 1 . Let S = { : 0 ≤ x ≤ p − 1 } , and let S = S + for
1 jp p
1 3
( p − 1) nxn 3
0 ≤ j ≤ p − 2 . ( S + a = { s + a : s ∈ S } . ) Then let S = { : 0 ≤ x ≤ p − 1 } + . Finally,
3 p − 1 2
p p 3
2 3
′xnlet S = { : 0 ≤ x ≤ p − 1 } . Then I claimp 3
( )3
p − 1
⊔3
′
S \ Sii =0
is well-centered but not decomposable. Well-centered follows from the construction: I only added andnsubtracted off regular polygons. To show that its decomposable, consider . Clearly this is in the set,
1 pn n n
′
but isn’t in S . I claim that isn’t in any more regular p -gons. For i ≥ 4, this means that + isip p p
1 1 iin some set. But this is a contradiction, as we can easily check that all points we added in are multiplesof p , while isn’t.inei
′ 3 eip
For i = 1, note that 0 was removed by S . For i = 2, note that the only multiples of p that are in
( p − 1) n 3
n 1 n nsome S are 0 , , . . . , . In particular, + isn’t in any S . So it suffices to consider the casej jp p p p
1 1 1 2
( p − 1) nn 3
i = 3, but it is easy to show that + isn’t in any S . So we’re done.
p pi
1 3
⇐ , i.e. n has ≤ 2 prime divisors: This part seems to require knowledge of cyclotomic polynomials.
a a b
These will easily give a solution in the case n = p . Now, instead turn to the case n = p q . The nextlemma is the key ingredient to the solution.
Lemma : Every well-centered subpolygon can be gotten by adding in and subtracting off regularpolygons.
Note that this is weaker than the problem claim, as the problem claims that adding in polygons isenough.
pqnn
( x − 1)( x − 1)
Proof. It is easy to verify that φ ( x ) = n n . Therefore, it suffices to check that there existnp q
( x − 1)( x − 1)
integer polynomials c ( x ) , d ( x ) such thatnn n npqx − 1 x − 1 ( x − 1)( x − 1)
· c ( x ) + · d ( x ) = .
n n n np q p qx − 1 x − 1 ( x − 1)( x − 1)
Rearranging means that we wantn n nq p pq
( x − 1) · c ( x ) + ( x − 1) · d ( x ) = x − 1 .
sn tn n
But now, since gcd( n/p, n/q ) = n/pq , there exist positive integers s, t such that − = . Nowq p pqsn sn nq q pqx − 1 x − xchoose c ( x ) = , d ( x ) = to finish.
n nq px − 1 x − 1
Now we can finish combinatorially. Say we need subtraction, and at some point we subtract off a p -gon.
All the points in the p -gon must have been added at some point. If any of them was added from ap -gon, we could just cancel both p -gons. If they all came from a q -gon, then the sum of those p q -gonswould be a pq -gon, which could have been instead written as the sum of q p -gons. So we don’t needsubtraction either way. This completes the proof.