HMMT 二月 2019 · COMB 赛 · 第 8 题
HMMT February 2019 — COMB Round — Problem 8
题目详情
- For a positive integer N , we color the positive divisors of N (including 1 and N ) with four colors. A coloring is called multichromatic if whenever a , b and gcd( a, b ) are pairwise distinct divisors of N , then they have pairwise distinct colors. What is the maximum possible number of multichromatic colorings a positive integer can have if it is not the power of any prime?
解析
- For a positive integer N , we color the positive divisors of N (including 1 and N ) with four colors. A coloring is called multichromatic if whenever a , b and gcd( a, b ) are pairwise distinct divisors of N , then they have pairwise distinct colors. What is the maximum possible number of multichromatic colorings a positive integer can have if it is not the power of any prime? Proposed by: Evan Chen Answer: 192 First, we show that N cannot have three distinct prime divisors. For the sake of contradiction, suppose pqr | N for three distinct primes p, q, r . Then by the problem statement, ( p, q, 1), ( p, r, 1), and ( q, r, 1) have three distinct colors, so ( p, q, r, 1) has four distinct colors. In addition, ( pq, r, 1), ( pq, pr, p ), and ( pq, qr, q ) have three distinct colors, so ( pq, p, q, r, 1) has five distinct colors, contradicting the fact that there are only four possible colors. 3 2 3 2 Similarly, if p q | N for some distinct primes p and q , then ( p, q, 1), ( p , q, 1), ( p , q, 1), ( p , pq, p ), 3 3 2 2 2 3 ( p , pq, p ), and ( p , p q, p ) are all triples with distinct colors, so (1 , q, p, p , p ) must have five distinct 2 2 colors, which is again a contradiction. In addition, if p q | N for some distinct primes p and q , then 2 2 2 2 2 2 ( p, q, 1), ( p , q , 1), ( p , q, 1), and ( p, q , 1) are all triples with pairwise distinct colors, so (1 , p, q, p , q ) must have five distinct colors, another contradiction. We are therefore left with two possibilities: • Case 1: N = pq In this case, the only triple of factors that must have pairwise distinct colors is ( p, q, 1). We have 4 · 3 · 2 = 24 choices for these three, and 4 choices for pq itself, giving 4 · 24 = 96 multichromatic colorings. 2 • Case 2: N = p q 2 2 In this case, the triples of pairwise distinctly colored factors are ( p, q, 1), ( p , q, 1), and ( p , pq, p ). 2 From this, we see that (1 , p, q, p ) must have four distinct colors, and the color of pq must be 2 distinct from p and p . There are 4 · 3 · 2 · 1 = 24 ways to assign the four distinct colors, 2 ways to 2 assign the color of pq after that, and 4 ways to color p q after that, giving a total of 24 · 2 · 4 = 192 monochromatic colorings. Therefore, there can be at most 192 multichromatic colorings.