一道全国联赛题的另解.doc_第1页
一道全国联赛题的另解.doc_第2页
一道全国联赛题的另解.doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

一道全国联赛题的另解 江苏省徐州高等师范学校(221116)朱允洲 题目设S=1,2,3，100，求最大整数k，使得S有k个互不相同的非空子集，具有性质：对这k个子集中任意两个不同子集，若它们的交非空，则它们交集中的最小元素与这两个子集中的最大元素均不相同。 这是xx年全国高中数学联赛二试第三题，命题组提供的解法是用数学归纳法及抽屉原理进行求解，技巧性较强，不容易想到。本文给出另一种解法。 解:为了叙述的方便，定义集合中元素的序：记A=a1,a2,a3，规定a1 显然，满足性质的S的k个非空子集至少是二元素集；k个子集中必含有集合S。 含有元素1的S的所有至少二元子集共有2991个，它们显然满足题设中的性质，所以kmax2991。下面证明kmax299不可能。 考察S的所有至少二元素子集，共有C2100+C3100+C100100=2100101个，可分为两类： （1）含1的至少二元素子集构成的集合记为M，其元素个数为2991； （2）不含1的至少二元素子集构成的集合记为P，其元素个数为C299+C399+C9999=299100。 从上述分类方法可知：去掉（1）中的所有二元素子集就是含1的至少三元素子集构成的集合，其元素个数为299199=299100，若将这些集合中的元素1去掉，它们就属于集合P，反之亦成立。因此，任一不含1的至少m元素子集与含1的至少m+1元素子集应是一一对应关系，即a1,a2,am?1,a1,a2,，am(2m99)。 显然，M与P中元素个数不可能大于或等于299。由于2,33,4=3，所以对于P中的集合，若满足题设中的性质，其个数应不超过299101，即使将M中的所有集合都添加到P中，此时P中集合个数应不超过299101+99=2992，因此，若kmax299，则必定要从P中至少取一个集合添加到M中，使得此时M中的集合仍满足题设的性质。现从P中任取一集合，记为pr=a1,a2,ar(r2)，则它与M中集合mr=1,a1,a2,ar(r2)对应。又易知集合1,a1M，而1,a1pr=a1，不满足题设中集合的性质。由pr的任意性知P中任一集合均无法添加入M中，即kmax299不可能，因此kmax=2991。 注:运用上述方法，有 1。若将集合S中的元素个数可推广至n(n3)个，则kmax=2n11。 2。如果将原问题题设中的性质改为：“对这k个子集中任意两个不同子集，若它们的交非空，则它们交集中的最大元素与这两个子集中的最小元素均不相同。”结论仍成立，即kmax=2991。 ght:150%;color:r
人人文库> 全部分类> 毕业设计 > 毕业论文

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论