HMMT 二月 2020 · COMB 赛 · 第 2 题
HMMT February 2020 — COMB Round — Problem 2
题目详情
- How many positive integers at most 420 leave different remainders when divided by each of 5, 6, and 7?
解析
- How many positive integers at most 420 leave different remainders when divided by each of 5, 6, and 7? Proposed by: Milan Haiman Answer: 250 Solution: Note that 210 = 5 · 6 · 7 and 5, 6, 7 are pairwise relatively prime. So, by the Chinese Remainder Theorem, we can just consider the remainders n leaves when divided by each of 5, 6, 7. To construct an n that leaves distinct remainders, first choose its remainder modulo 5, then modulo 6, then modulo 7. We have 5 = 6 − 1 = 7 − 2 choices for each remainder. Finally, we multiply by 2 3 because 420 = 2 · 210. The answer is 2 · 5 = 250.