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
because 420 = 2 · 210. The answer is 2 · 5 = 250.3