HMMT 二月 2008 · TEAM1 赛 · 第 7 题
HMMT February 2008 — TEAM1 Round — Problem 7
题目详情
英文原题
- [ 35 ] Show that for positive integers n and d ,
d d
( n − 1)2 + 1 ≤ f ( n, d ) ≤ ( n − 1) n + 1 . 1
解析
英文解析
- [ 35 ] Show that for positive integers n and d ,
d d
( n − 1)2 + 1 ≤ f ( n, d ) ≤ ( n − 1) n + 1 .
Solution: Note that taking the set of points to be a multiset does not affect f ( n, d ) asadding multiples of n to any of the coordinate values does not change the result. The lowerbound is obtained by considering the multiset consisting of n − 1 copies of each of the 2 d
0 , 1-vectors of length d , as it contains no submultiset of size n whose centroid is also a latticedpoint. By the pigeonhole principle, any multiset of ( n − 1) n + 1 lattice points must containn points whose coordinates are congruent modulo n . The centroid of these n points is also alattice point, thus proving the upper bound.