level 1
对某些正整数n,存在A1,A2,…,An为集合{1,2,…,n}的n个不同子集,满足下列条件:对任意不大于n的正整数i,j,① i不属于Ai,且每个Ai至少含有三个元素;② i属于Aj的充要条件是j不属于Ai,其中i不等于j. 为了表示这些子集,作n行n列的数表,规定第i行第j列的数为 aij={ 0,当i不属于Aj 1,当i属于Aj(Ⅰ)求该数表中每列至少有多少个1;(Ⅱ)用n表示该数表中1的个数,并证明n≥7;(Ⅲ)请构造出集合{1,2,…,7}的7个不同子集A1,A2,…,A7,使得A1,A2,…,A7满足题设(写出一种答案即可).
2005年11月07日 10点11分
1
level 1
第四行与第五行是对aij分两种情况aij={ 0,当i不属于Aj 1,当i属于Aj
2005年11月07日 10点11分
2
level 1
(I)根据①每个Ai,至少含有三个元素得:作出的数表每列至少有3个1;…2分 (II)①中的 ,表明数表的一条对角线上数字都是0,②表明除这条对角线以外,aij和aji恰好一个为1,而另一个为0,即数表中除此对角线以外,0和1各占一半,故数表中共有 (n^2-n)/2个 考察数表中的1的总数:一方面1的总数为 ,另一方面因为数表每列至少有三个1,所以整个数表(共n列)至少有3n个1,因此可以列出不等式 9n^2-n)/2 ≥3n,解得n≥7 (III)可以构造A1={2,3,4},A2={3,5,6},A3={4,5,7},A4={2,6,7},A5={1,4,6},A6={1,3,7},A7={1,2,5}.
2008年04月26日 07点04分
3