设正整数m,n满足m大于等于n大于1,F1,F2,...,Fk是集合{1,2,...,m}的n元子集,且对1小于等于i小于j小于等于k,Fi交集Fj中至多有1个元素,证明:k小于等于m(m-1)/n(n-1)

来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/24 08:57:04
设正整数m,n满足m大于等于n大于1,F1,F2,...,Fk是集合{1,2,...,m}的n元子集,且对1小于等于i小于j小于等于k,Fi交集Fj中至多有1个元素,证明:k小于等于m(m-1)/n(

设正整数m,n满足m大于等于n大于1,F1,F2,...,Fk是集合{1,2,...,m}的n元子集,且对1小于等于i小于j小于等于k,Fi交集Fj中至多有1个元素,证明:k小于等于m(m-1)/n(n-1)
设正整数m,n满足m大于等于n大于1,F1,F2,...,Fk是集合{1,2,...,m}的n元子集,且对1小于等于i小于j小于等于k,Fi交集Fj中至多有1个元素,证明:k小于等于m(m-1)/n(n-1)

设正整数m,n满足m大于等于n大于1,F1,F2,...,Fk是集合{1,2,...,m}的n元子集,且对1小于等于i小于j小于等于k,Fi交集Fj中至多有1个元素,证明:k小于等于m(m-1)/n(n-1)
证明:集合{1,2,...,m}有m个元素,可知其有C(m,2) = m(m-1)/2个2元子集.
而对于n元集合F[i],可知其有C(n,2) = n(n-1)/2个2元子集.
由于i ≠ j时F[i]与F[j]至多有一个公共元素,二者没有相同的2元子集.
于是k个n元集合共有kn(n-1)/2个不同的2元子集.
由它们都是{1,2,...,m}的2元子集,得kn(n-1)/2 ≤ m(m-1)/2,即k ≤ m(m-1)/(n(n-1)).