HMMT 二月 2020 · 冲刺赛 · 第 22 题
HMMT February 2020 — Guts Round — Problem 22
题目详情
- [12] Let A be a set of integers such that for each integer m , there exists an integer a ∈ A and positive n integer n such that a ≡ m (mod 100). What is the smallest possible value of | A | ?
解析
- [12] Let A be a set of integers such that for each integer m , there exists an integer a ∈ A and positive n integer 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 elements must be in A . We claim that all powerful elements are the cube of some marginal element. To show this take a powerful 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 is marginal). 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 has more 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 are needed in total.