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 ) as adding multiples of n to any of the coordinate values does not change the result. The lower d bound is obtained by considering the multiset consisting of n − 1 copies of each of the 2 0 , 1-vectors of length d , as it contains no submultiset of size n whose centroid is also a lattice d point. By the pigeonhole principle, any multiset of ( n − 1) n + 1 lattice points must contain n points whose coordinates are congruent modulo n . The centroid of these n points is also a lattice point, thus proving the upper bound.