HMMT 二月 2015 · 代数 · 第 4 题

英文解析

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
   Answer: 20503 Let m := 203 be an integer not divisible by 3. We’ll show the answer for generalm − 1
   such m is m ⌈ ⌉ .
   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 }2
   (mod m ). Since x, y, z (mod m ) has opposite orientation as N − x, N − y, N − z (mod m ), this isequivalent to x, y, z forming an arithmetic progression (in some order) modulo m centered at one ofx, 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 tobe equally spaced modulo m , i.e. x − y ≡ y − z ≡ z − x ). So the number of distinct 3-sets correspondingm − 1
   to arithmetic progressions is m ⌈ ⌉ (choose a center and a difference, noting that ± d give the samem − 12
   arithmetic progression). Since our specific m = 203 is odd this gives m = 203 · 101 = 20503.
   Remark. This problem is a discrete analog of certain so-called Frieze patterns. (See also Chapter 6,2
   Exercise 5.8 of Artin’s Algebra textbook.)