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 vertex set can be written as the disjoint union of regular polygons with at least 3 vertices. Show that all well-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 vertex set can be written as the disjoint union of regular polygons with at least 3 vertices. Show that all well-centered subpolygons are decomposable if and only if n has at most two distinct prime divisors. Proposed by: Yang Liu ∏ e i ⇒ , i.e. n has ≥ 3 prime divisors: Let n = p . Note it suffices to only consider regular p -gons. i i jn xn Label the vertices of the n -gon 0 , 1 , . . . , n − 1 . Let S = { : 0 ≤ x ≤ p − 1 } , and let S = S + for 1 j p p 1 3 ( p − 1) n xn 3 0 ≤ j ≤ p − 2 . ( S + a = { s + a : s ∈ S } . ) Then let S = { : 0 ≤ x ≤ p − 1 } + . Finally, 3 p − 1 2 3 p p 2 3 xn ′ let S = { : 0 ≤ x ≤ p − 1 } . Then I claim 3 p 3 ( ) p − 1 3 ⊔ ′ S \ S i i =0 is well-centered but not decomposable. Well-centered follows from the construction: I only added and n subtracted off regular polygons. To show that its decomposable, consider . Clearly this is in the set, p 1 n n n ′ but isn’t in S . I claim that isn’t in any more regular p -gons. For i ≥ 4, this means that + is i p p p 1 1 i in some set. But this is a contradiction, as we can easily check that all points we added in are multiples e n i of p , while isn’t. i p i e ′ 3 For i = 1, note that 0 was removed by S . For i = 2, note that the only multiples of p that are in 3 ( p − 1) n n 1 n n some S are 0 , , . . . , . In particular, + isn’t in any S . So it suffices to consider the case j j p p p p 1 1 1 2 ( p − 1) n n 3 i = 3, but it is easy to show that + isn’t in any S . So we’re done. i p p 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 next lemma is the key ingredient to the solution. Lemma : Every well-centered subpolygon can be gotten by adding in and subtracting off regular polygons. Note that this is weaker than the problem claim, as the problem claims that adding in polygons is enough. n n pq ( x − 1)( x − 1) Proof. It is easy to verify that φ ( x ) = n n . Therefore, it suffices to check that there exist n p q ( x − 1)( x − 1) integer polynomials c ( x ) , d ( x ) such that n n n n pq x − 1 x − 1 ( x − 1)( x − 1) · c ( x ) + · d ( x ) = . n n n n p q p q x − 1 x − 1 ( x − 1)( x − 1) Rearranging means that we want n n n q 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 − = . Now q p pq sn sn n q q pq x − 1 x − x choose c ( x ) = , d ( x ) = to finish. n n q p x − 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 a p -gon, we could just cancel both p -gons. If they all came from a q -gon, then the sum of those p q -gons would be a pq -gon, which could have been instead written as the sum of q p -gons. So we don’t need subtraction either way. This completes the proof.