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

HMMT February 2015 — Guts Round — Problem 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 n of 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 and r s t y + y − y . r s t

解析

[ 8 ] Find the smallest integer n ≥ 5 for which there exists a set of n distinct pairs ( x , y ) , . . . , ( x , y ) 1 1 n n of 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 and r s t y + y − y . r s t 2 Answer: 8 In other words, we have a set S of n pairs in ( Z / 4 Z ) closed under addition. Since 1 + 1 + 1 + 1 ≡ 0 (mod 4) and 1 + 1 + 1 ≡ − 1 (mod 4), (0 , 0) ∈ S and S is closed under (additive) 2 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 { 1 , 2 , 3 , 4 } × { 2 , 4 } . Remark. In fact, S is a finite abelian group. Such groups have a very clean classification; this is clarified by the fact that abelian groups are the same as modules over Z , the ring of integers.