高一设置奥数题。
我们考虑所有Ai的并集,设* *有m个元素,记为b1,b2,…,bm。定义集:B1,B2,…Bm,满足,若bj∈Ai,则Ai∈Bj。即我们构造原集合的对偶集合。
这些B1,B2,…,Bm,不难发现如下性质:
(1)任意两个之间最多只有一个共同元素。(2)每个Bj不包含所有的A1,A2,…,An。(3)每个二元群(Ai,Aj)恰好在某个Bk中。(4)每个Ai属于30个不同的bj。
让我们证明任何Bj最多有30个元素。利用反证法,假设一个B1包含31个元素。设这个集合是B1,这31个元素是A1,A2,…A31。根据性质(3),这31个元素中的任意两个不能同时出现在另一个Bi中。从性质(2)中可以找到一个不同于这31个元素的As,而从性质(3)中,这个As必须与A1,A2,…A31相匹配,也就是说二元群(As,Al)(l=1,2),这样,As就出现在31 Bi中,与性质(4)相矛盾。
我们来估算一下。
对于二元群(Ai,Aj),一方面,它的个数是n*(n-1)/2。另一方面,考虑每个|Bi|,它们的和为30n,不难发现,当每个|Bi|为30时,所有Bi的二元群的和最大(即如果和已知,则|Bi|的所有组合的和最大)。所以我们有不平等。
n *(n-1)/2 & lt;= 30 * 29/2 * n;
解决
结构我就不写了。根据等号,条件就满足了。