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. Acoloring is called multichromatic if whenever a , b and gcd( a, b ) are pairwise distinct divisors of N , thenthey have pairwise distinct colors. What is the maximum possible number of multichromatic coloringsa 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. Acoloring is called multichromatic if whenever a , b and gcd( a, b ) are pairwise distinct divisors of N , thenthey have pairwise distinct colors. What is the maximum possible number of multichromatic coloringsa 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, supposepqr | 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 multichromaticcolorings.
• Case 2: N = p q 2
2 2
In this case, the triples of pairwise distinctly colored factors are ( p, q, 1), ( p , q, 1), and ( p , pq, p ).
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 = 1922
monochromatic colorings.
Therefore, there can be at most 192 multichromatic colorings.