HMMT 二月 2015 · 冲刺赛 · 第 14 题

英文解析

14. [ 8 ] Find the smallest integer n ≥ 5 for which there exists a set of n distinct pairs ( x , y ) , . . . , ( x , y )
    1 1 n nof positive integers with 1 ≤ x , y ≤ 4 for i = 1 , 2 , . . . , n , such that for any indices r, s ∈ { 1 , 2 , . . . , n }
    i i
    (not necessarily distinct), there exists an index t ∈ { 1 , 2 , . . . , n } such that 4 divides x + x − x andr s ty + y − y .
    r s t
    Answer: 8 In other words, we have a set S of n pairs in ( Z / 4 Z ) closed under addition. Since 2
    1 + 1 + 1 + 1 ≡ 0 (mod 4) and 1 + 1 + 1 ≡ − 1 (mod 4), (0 , 0) ∈ S and S is closed under (additive)
    inverses. Thus S forms a group under addition (a subgroup of ( Z / 4 Z ) ). By Lagrange’s theorem 2
    (from basic group theory), n | 4 , so n ≥ 8. To achieve this bound, one possible construction is 2
    { 1 , 2 , 3 , 4 } × { 2 , 4 } .
    Remark. In fact, S is a finite abelian group. Such groups have a very clean classification; this isclarified by the fact that abelian groups are the same as modules over Z , the ring of integers.