AMC 8 1998 Problem 24
AMC8 1998 年第 24 题
余数与同余★★★★☆
A rectangular board of 8 columns has squares numbered beginning in the upper left corner and moving left to right so row one is numbered 1 through 8, row two is 9 through 16, and so on. A student shades square 1, then skips one square and shades square 3, skips two squares and shades square 6, skips 3 squares and shades square 10, and continues in this way until there is at least one shaded square in each column. What is the number of the shaded square that first achieves this result?
一块有 8 列的矩形板，方格从左上角开始从左到右编号，第一行为 1 到 8，第二行为 9 到 16，以此类推。一个学生涂黑了方格 1，然后跳过一个方格涂黑方格 3，跳过两个方格涂黑方格 6，跳过 3 个方格涂黑方格 10，并继续按此方式操作，直到每一列至少有一个涂黑的方格。首次达到此结果时涂黑的方格编号是多少？
- A.36
- B.64
- C.78
- D.91
- E.120
正确答案 · Correct Answer
E
解析 · Solution
解法1
常规解法 · 列三角形数看余数
被涂的是三角形数 ：1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120。它们除以 8 的余数要把 0 到 7 集齐；最后才出现的余数是 0，首次出现在 120，故答案 120。
巧解 · 何时被 8 整除
被 8 整除须 被 16 整除。 与 n+1 一奇一偶，2 的因子全在偶数那个里，故须 或 ，最小 n=15（n+1=16），对应三角形数 120。此前没有三角形数被 8 整除，故第 8 列到 120 才首次被填。
Solution 1
Elementary · list triangular numbers' remainders
The shaded squares are the triangular numbers : 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120. Their remainders mod 8 must cover all of 0 through 7; the last residue to appear (remainder 0) shows up only at 120, so 120 is the answer.
Slick · when divisible by 8
is divisible by 8 iff is divisible by 16. Since and n+1 have opposite parity, all factors of 2 lie in one of them, so we need or ; the smallest is n=15 (n+1=16), giving 120. No earlier triangular number is divisible by 8, so column 8 is first filled at 120.
继续练习