第八周作业
first half
基础部分
A1
解：（1）由题，矩阵表示为：
$$
\begin{bmatrix}
1&1&1&1&1&1&1&1\
0&1&0&1&1&1&0&1\
0&0&1&0&1&0&1&1\
0&0&0&1&0&1&0&1\
0&0&0&0&1&0&0&1\
0&0&0&0&0&1&0&0\
0&0&0&0&0&0&1&0\
0&0&0&0&0&0&0&1\
\end{bmatrix}
$$
（2）
$$
记(1)中的矩阵为M，则关系R的对称闭包为M\vee M^T\
既包含R又具有对称性的二元关系即以R的对称闭包为基础\
矩阵M中主对角线上方共有11处0,选某几处0改为1，再做对称闭包即可\
这样便能得到符合题意的矩阵，共C^0_{11}+C^1_{11}+…+C^{11}_{11}=2^{11}种\
故共有2^{11}个符合题意的二元关系。
$$
A2
解：
$$
分为三种情况:\
1)两个1均在主对角线上，则该矩阵必然是对称矩阵，舍去\
2)两个1只有一个在主对角线上，则有C^1_3C^1_6=18个\
3)若两个1都不在主对角线上，则有C^2_6-C^1_3=12个\
综上，共有18+12=30个可能的R\
$$
进阶部分
B1
解：
$$
对于等价关系，考虑关系的矩阵表示中的分块矩阵\
对于1\times1的子矩阵，显然只有一个元素并且元素为1即可\
对于2\times2的子矩阵，则有两种情况\
\begin{bmatrix}
1&&0\0&&1
\end{bmatrix}或\begin{bmatrix}
1&&1\1&&1
\end{bmatrix}\
对于3\times3的子矩阵，则有五种情况\
\begin{bmatrix}1&0&0\0&1&0\0&0&1\end{bmatrix}
\begin{bmatrix}1&1&0\1&1&0\0&0&1\end{bmatrix}
\begin{bmatrix}1&0&0\0&1&1\0&1&1\end{bmatrix}
\begin{bmatrix}1&0&1\0&1&0\1&0&1\end{bmatrix}^{()}
\begin{bmatrix}1&1&1\1&1&1\1&1&1\end{bmatrix}\
对于更高阶的矩阵，考虑其子矩阵里出现低阶的等价关系矩阵\
对于4\times4的矩阵，我们做如下讨论:\
1)不含2\times2及以上的子矩阵:2种(即单位矩阵或类似于矩阵^{()})\
2)只含一个2\times2及以上的非单位子矩阵:3\times(2-1)+2\times(5-1)+1=12种\
3)只含两个2\times2及以上且不重合的非单位子矩阵:1种\
对于5\times5的子矩阵，我们做如下讨论:\
1)不含2\times2及以上的子矩阵:2种\
2)只含一个2\times2及以上的非单位子矩阵:\4\times(2-1)+3\times(5-1)+2\times(15-1)+1=45种\
3)只含两个2\times2及以上的非单位子矩阵:3+2\times2=7种\
4)只含三个2\times2及以上的非单位子矩阵:因为3\times2>5,故不存在\
综上共有54种。
$$
B2
解：
$$
显然,A,B,C构成了集合{1,2,…,n}的一个划分\
1)若有两个集合是空集，那另外一个集合必然是{1,2,…,n}:C^1_3=3个\
2)若只有一个集合是空集:C^1_3\times(C^1_n+C^2_n+…+C^{n-1}n)=3(2^n-2)个\
3)若三个集合都不是空集:\C^1_n(C^1{n-1}+…+C^{n-2}{n-1})+C^2_n(C^1{n-2}+…+C^{n-3}_{n-2})+…+C^{n-2}_n(C^1_2)\
=C^1_n(2^{n-1}-2)+C^2_n(2^{n-2}-2)+…+C_n^{n-2}(2^2-2)\
=C^1_n2^{n-1}+C^2_n2^{n-2}+…+C^{n-2}_n2^2-2(C^1_n+C^2_n+…+C_n^{n-2})\
=(2+1)^n-C^0_n2^n-C^{n-1}_n2^1-C^n_n2^0-2(2^n-2-n)\
=3^n-3\cdot2^n+3\
综上，共有3+3(2^n-2)+3^n-3\cdot2^n+3=3^n个
$$
second half
基础部分
A3
证明：考虑集合${1,2,3,…,2p}$的p个互不相交的子集，分别记为$P_1,P_2,…,P_p$，其中$p_i={2i-1,2i}$ ，显然$P_i$中的两个元素为一奇一偶，故两元素互质，并且有$P_1\cup P_2\cup…\cup P_p={1,2,3,…,2p}$。
下面，我们从集合${1,2,3,…,2p}$中任取$p+1$个元素，由鸽巢原理，必然有两个元素落在了同一个子集$P_j$内，则有这两个元素互质，命题得证。
A4
证明：考虑正整数集合按模$2p$划分的$p+1$个互不相交的子集，分别记为$P_0,P_1,…,P_p$，其中$P_0={n|n\equiv 0(mod; 2p)}$，$P_p={n|n\equiv p(mod;2p)}$，$P_i={n|n\equiv i(mod;2p)\cup n\equiv 2p-i(mod;2p)},1\leqslant i\leqslant p-1$，显然有$P_0\cup P_1\cup…\cup P_p=N_+$。
下面，我们从正整数集合中任取$p+2$个正整数，由鸽巢原理，必然有两个元素a和b落在了同一个子集$P_j$内，特别地，若这两个元素都落在了$P_0$或$P_p$内，那么显然有$2p|a+b$，若这两个元素落在了子集$P_i(1\leqslant i\leqslant p-1)$内，如果两元素模p同余，则有$2p|a-b$，如果两元素模p不同余，则不妨$a\equiv i(mod;2p)$ 并且$b\equiv 2p-i(mod;2p)$，则有$2p|a+b$。命题得证。
进阶部分
B3
参考DeepSeek，证明如下：
集合S含有10个元素，则其非空子集的数量为$2^{10}-1=1023$个，而S的子集中元素之和的最大值为91+92+93+94+95+96+97+98+99+100=955，元素之和最小值为1，子集中的元素之和只有955种可能，那么由鸽巢原理，在这1023个非空子集中，必然有两个子集A与B的元素之和是相等的。若集合A与集合B不相交，则命题得证，若集合A与集合B有公共元素，取$A’=A-B,B’=B-A$，那么$A’,B’$两集合不相交并且两集合中元素之和相等，满足题意，命题得证。
B4
证明：不妨，10个人选一个人A，对剩余的九人按是否认识A来分类，由抽屉原理，至少有一方有五个人，此时另外一方有四人。
若这五人皆认识A，分两种情况：1）五人中至少存在一对人相互认识，此时再加上A，就有三个相互认识的人，符合题意。2）五人中两两都不认识，那必然有四个人相互不认识，也符合题意。
若这五人皆不认识A，而另外一方的四人认识A，分两种情况：1）四人中至少存在一对人相互认识，此时再加上A，就有三个相互认识的人，符合题意。2）四人中两两都不认识，也符合题意。
综上，命题成立。