HMMT 二月 2015 · 代数 · 第 4 题
HMMT February 2015 — Algebra — Problem 4
题目详情
- Compute the number of sequences of integers ( a , . . . , a ) such that the following conditions hold. 1 200 • 0 ≤ a < a < · · · < a ≤ 202. 1 2 200 • There exists a positive integer N with the following property: for every index i ∈ { 1 , . . . , 200 } there exists an index j ∈ { 1 , . . . , 200 } such that a + a − N is divisible by 203. i j
解析
- Compute the number of sequences of integers ( a , . . . , a ) such that the following conditions hold. 1 200 • 0 ≤ a < a < · · · < a ≤ 202. 1 2 200 • There exists a positive integer N with the following property: for every index i ∈ { 1 , . . . , 200 } there exists an index j ∈ { 1 , . . . , 200 } such that a + a − N is divisible by 203. i j Answer: 20503 Let m := 203 be an integer not divisible by 3. We’ll show the answer for general m − 1 such m is m ⌈ ⌉ . 2 Let x, y, z be the three excluded residues. Then N works if and only if { x, y, z } ≡ { N − x, N − y, N − z } (mod m ). Since x, y, z (mod m ) has opposite orientation as N − x, N − y, N − z (mod m ), this is equivalent to x, y, z forming an arithmetic progression (in some order) modulo m centered at one of x, y, z (or algebraically, one of N ≡ 2 x ≡ y + z , N ≡ 2 y ≡ z + x , N ≡ 2 z ≡ x + y holds, respectively). Since 3 ∤ m , it’s impossible for more than one of these congruences to hold (or else x, y, z would have to be equally spaced modulo m , i.e. x − y ≡ y − z ≡ z − x ). So the number of distinct 3-sets corresponding m − 1 to arithmetic progressions is m ⌈ ⌉ (choose a center and a difference, noting that ± d give the same 2 m − 1 arithmetic progression). Since our specific m = 203 is odd this gives m = 203 · 101 = 20503. 2 Remark. This problem is a discrete analog of certain so-called Frieze patterns. (See also Chapter 6, Exercise 5.8 of Artin’s Algebra textbook.)