Question

高一集合奥数题

求使这样的集合族存在的最大正整数n.
已知一族集合A1,A2……An具有性质：1.每个Ai含有30个元素；2.对每一对i,j:1≤i＜j≤n,Ai∩Aj都是单元集；3.A1∩A2∩……∩An=空集
求使这样的集合族存在的最大正整数n.
最好讲得浅显易懂一点，谢谢！(答案是871，准确无误，要过程)

Answer 1

我们考虑所有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，…，31）必须同属于互异的31个集合：Bi1，Bi2，…，Bi31。这样As就在31个Bi中出现了，与性质（4）矛盾。

下面来估计。
对二元组（Ai，Aj）计算，一方面，它的数目为n*（n-1）/2。另一个方面，考察每一个|Bi|，它们的和为30n，不难发现，当每一个|Bi|都是30的时候，所有Bi的二元组数目之和最大（即在知道总和的情况下，求|Bi|的所有组合数的和最大）。于是我们有不等式
n*（n-1）/2<=30*29/2*n；
解得n<=871.最大n为871.
构造就不写了。根据等号成立条件就行了。

Answer 2

1\2n(n-1)≤30且 n为整数 ，所以n取8

Answer 3

这个悬赏80--100比较合理，加价吧，O(∩_∩)O~

追问

加价喽，回答到我满意为止才给！！！

追答

答案871。分两步：证明n<=871；构造n=871的例子。

记S为所有A_i的并集。假设S中的元素a在各个A_i中出现次数最多，记这个次数为k。
记U为含有a的那些集合A_i的并集。按条件2，我们有
|U|=29k+1. (*)
记V=S\U. 设m为配对(x,A)的个数，其中A是某个A_i，x是A的一个元素。
一方面，根据条件1，我们有m=30n.
另一方面，那些属于U的元素x对计数m的贡献至多是k|U|。
现在考虑那些属于V的元素x，也就是那些所属集合不含a的元素x。
记x所在的那个集合是A，那么A与每一个含a的元素交于一个非a的元素，
从而A中恰有30-k个元素属于V。也就是说，
每一个属于V的元素x所在的集合对计数m的贡献恰为30-k。
由于不含a的集合恰有n-k个，所以那些属于V的元素x对计数m的贡献恰为(30-k)(n-k)。
于是我们得到两种方法算出来的同一个计数m，即30n<=k|U|+(30-k)(n-k).
把(*)代入上式，化简即得n<=871.

构造：设 a_{i,k} (0<=i<=29, 1<=k<=29) 是30*29=870个两两互异的正数。
为方便起见，对任意 i 和任意 k, 记a_{i+30,k}=a_{i,k+29}=a_{i,k}. 也就是说，
元素a_{i,k}的第一个脚标 i 取自模30的集合Z_{30},
第二个脚标 k 取自模29的集合Z_{29}.
对每个0<=i<=29，令
A_{0,i} = {0} union {a_{i,j} : 1<=j<=29}.
对每个1<=i<=29和每个1<=k<=29，令
A_{i,k} = a_{0,i} union {a_{j,ij+k} : 1<=j<=29}.

现在我们证明上面这30+29*29=871个集合满足题设条件。
字数超了，证明该构造的正确性见评价。