HMMT 二月 2008 · TEAM1 赛 · 第 8 题

英文解析

8. [ 40 ] Show that for positive integers n , n and d ,
   1 2
   f ( n n , d ) ≤ f ( n , d ) + n ( f ( n , d ) − 1) .
   1 2 1 1 2
   Solution: Given a multiset of f ( n , d ) + n ( f ( n , d ) − 1) lattice points, we may select
   1 1 2
   l = f ( n , d ) pairwise disjoint submultisets S , S , . . . , S , each consisting of n points, whose
   2 1 2 l 1
   centroid is a lattice point. Let ϕ map each multiset S to its centroid g . By the definition ofi if ( n , d ), there exists a submultiset T ⊂ { g , g , . . . , g } satisfying | T | = n whose centroid is
   2 1 2 2
   ⋃l − 1
   a lattice point. Then ϕ ( g ) is a multiset of n n lattice points whose centroid is alsoi 1 2
   i ∈ Ta lattice point. a