返回题库

HMMT 二月 2019 · COMB 赛 · 第 8 题

HMMT February 2019 — COMB Round — Problem 8

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 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?
解析

英文解析

  1. 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.