设正整数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/11/19 11:28:47
设正整数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)
xݒj@_%ۄz)%C{3!Ri (ZҔB1FHև)x:6}aYvg*t8X25&14f^8y&Jڰ"!A@ZުsKkK E1*h`jԭ"~zoVcR.hɘ9P5ݘ:mvoKX0лfz֓Bc(Gzax{TC+I̧Üw/5v\Z'jM!|HNqǜ4%ʐ&P̈fr=8qh rkN7WԌ'~akOї]2+9V A3  G/-kt`yepwɈ.1p!ZEȟ}2(U

设正整数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)).