一道全国联赛题的另解

  • 投稿答完
  • 更新时间2015-08-30
  • 阅读量529次
  • 评分4
  • 29
  • 0

江苏省徐州高等师范学校(221116)朱允洲

题目设S={1,2,3,…,100},求最大整数k,使得S有k个互不相同的非空子集,具有性质:对这k个子集中任意两个不同子集,若它们的交非空,则它们交集中的最小元素与这两个子集中的最大元素均不相同。

这是2014年全国高中数学联赛二试第三题,命题组提供的解法是用数学归纳法及抽屉原理进行求解,技巧性较强,不容易想到。本文给出另一种解法。

解:为了叙述的方便,定义集合中元素的序:记A={a1,a2,a3,…},规定a1<a2<a3<…。

显然,满足性质的S的k个非空子集至少是二元素集;k个子集中必含有集合S。

含有元素1的S的所有至少二元子集共有299-1个,它们显然满足题设中的性质,所以kmax≥299-1。下面证明kmax≥299不可能。

考察S的所有至少二元素子集,共有C2100+C3100+…+C100100=2100-101个,可分为两类:

(1)含1的至少二元素子集构成的集合记为M,其元素个数为299-1;

(2)不含1的至少二元素子集构成的集合记为P,其元素个数为C299+C399+…+C9999=299-100。

从上述分类方法可知:去掉(1)中的所有二元素子集就是含1的至少三元素子集构成的集合,其元素个数为299-1-99=299-100,若将这些集合中的元素1去掉,它们就属于集合P,反之亦成立。因此,任一不含1的至少m元素子集与含1的至少m+1元素子集应是一一对应关系,即{a1,a2,…,am}?{1,a1,a2,…,am}(2≤m≤99)。

显然,M与P中元素个数不可能大于或等于299。由于{2,3}∩{3,4}={3},所以对于P中的集合,若满足题设中的性质,其个数应不超过299-101,即使将M中的所有集合都添加到P中,此时P中集合个数应不超过299-101+99=299-2,因此,若kmax≥299,则必定要从P中至少取一个集合添加到M中,使得此时M中的集合仍满足题设的性质。现从P中任取一集合,记为pr={a1,a2,…,ar}(r≥2),则它与M中集合mr={1,a1,a2,…,ar}(r≥2)对应。又易知集合{1,a1}∈M,而{1,a1}∩pr={a1},不满足题设中集合的性质。由pr的任意性知P中任一集合均无法添加入M中,即kmax≥299不可能,因此kmax=299-1。

注:运用上述方法,有

1。若将集合S中的元素个数可推广至n(n≥3)个,则kmax=2n-1-1。

2。如果将原问题题设中的性质改为:“对这k个子集中任意两个不同子集,若它们的交非空,则它们交集中的最大元素与这两个子集中的最小元素均不相同。”结论仍成立,即kmax=299-1。