返回题库

HMMT 二月 2020 · COMB 赛 · 第 2 题

HMMT February 2020 — COMB Round — Problem 2

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

题目详情

英文原题

  1. How many positive integers at most 420 leave different remainders when divided by each of 5, 6, and
    7?
解析

英文解析

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