返回题库

HMMT 二月 2020 · 冲刺赛 · 第 22 题

HMMT February 2020 — Guts Round — Problem 22

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

题目详情

英文原题

  1. [12] Let A be a set of integers such that for each integer m , there exists an integer a ∈ A and positiveninteger n such that a ≡ m (mod 100). What is the smallest possible value of | A | ?
解析

英文解析

  1. [12] Let A be a set of integers such that for each integer m , there exists an integer a ∈ A and positiveninteger n such that a ≡ m (mod 100). What is the smallest possible value of | A | ?
    Proposed by: Daniel Zhu
    Answer: 41
    ∼
    Solution: Work in R = Z / 100 Z Z / 4 Z × Z / 25 Z .
    Call an element r ∈ R type ( s, t ) if s = ν ( r ) ≤ 2 and t = ν ( r ) ≤ 2. Also, define an element r ∈ R to=
    2 5
    be coprime if it is of type (0 , 0), powerful if it is of types (0 , 2), (2 , 0), or (2 , 2), and marginal otherwise.
    Then, note that if if r ∈ R is marginal, then any power of r is powerful. Therefore all marginal elementsmust be in A .
    We claim that all powerful elements are the cube of some marginal element. To show this take apowerful element r . In modulo 4 or 25, if r is a unit, then since 3 is coprime to both the sizes of
    × ×
    ( Z / 4 Z ) and ( Z / 25 Z ) , it is the cube of some element. Otherwise, if r is zero then it is the cube of 2
    or 5, respectively (since this case happens at least once this means that the constructed cube root ismarginal).
    We now claim that 4 additional elements are needed to generate the coprime elements. To see this,
    ×
    ∼
    note that R Z / 2 Z × Z / 20 Z since there are primitive roots mod 4 and 25. Under this isomorphism,
    ×=
    one can show that (1 , 1), (1 , 2), (1 , 4), and (0 , 1) generate anything, and that no element in R hasmore than one of these as a multiple.
    To wrap up, note that there are 100 − (20 + 1)(2 + 1) = 37 marginal elements, so 41 elements areneeded in total.