HMMT 二月 2008 · TEAM1 赛 · 第 8 题

HMMT February 2008 — TEAM1 Round — Problem 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 a

解析

[ 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 of i i f ( 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 also i 1 2 i ∈ T a lattice point. a