每日一题[4268]算两次

一份由 $n$ 道判断题($n\in\mathbb N^{\ast}$)构成的试卷,用 $(x_1,x_2,\cdots,x_n)$ 表示作答,其中 $x_i\in \{-1,1\}$($i=1,2,\cdots,n$),$1$ 表示 $\checkmark$,$-1$ 表示 $\times$,若作答 $\boldsymbol x=(x_1,x_2,\cdot,x_n),\boldsymbol y=(y_1,y_2,\cdots,y_n)$,定义\[\boldsymbol x\cdot \boldsymbol y =x_1y_1+x_2y_2+\cdots+x_ny_n,\]并用 $\boldsymbol x\cdot \boldsymbol y$ 来刻画作答的一致性,当 $\boldsymbol x\cdot \boldsymbol y=0$ 时,认为这两个作答无关.

1、当 $n=4$ 时,试给出 $4$ 个两两无关的作答;

2、当 $n=6$ 时,求证:不存在 $3$ 个两两无关的作答;

3、当 $n=96$ 时,若 $8$ 个作答两两无关,求证:至多有 $12$ 道题,这 $8$ 个作答给出的判断一致.

解析

1、$(1,1,1,1),(1,1,-1,-1),(1,-1,1,-1),(1,-1,-1,1)$;

2、用 $m$ 行 $n$ 列的数表 $a_{ij}$ 表示 $m$ 个同学对包含 $n$ 道判断题的的作答,设当 $m=n=6$ 时,$6$ 个作答两两无关,则

① 将其中的某一列全部取相反数不影响作答两两无关;

② 将其中任意两列交换位置不影响作答两两无关. 因此可以将数表的前 $2$ 行调整为\[\begin{bmatrix}1&1&1&1&1&1 \\ 1&1&1&-1&-1&-1 \end{bmatrix}\]设第 $3$ 行的前 $3$ 列中有 $x$ 个 $1$,后 $3$ 列中有 $y$ 个 $1$,则分别由第 $3$ 行与第 $1,2$ 行作答无关可得\[\begin{cases} x-(3-x)+y-(3-y)=0,\\ x-(3-x)-y+(3-y)=0,\end{cases}\iff \begin{cases} x+y=3,\\ x-y=0,\end{cases} \]该方程组没有整数解,因此命题得证.

3、用 $m$ 行 $n$ 列的数表 $a_{ij}$ 表示 $m$ 个同学对包含 $n$ 道判断题的的作答,设第 $j$ 列($j=1,2,\cdots,n$)的各数之和为 $p_j$,则第 $j$ 题所有同学作出的判断一致等价于 $|p_j|=m$,且\[\begin{split} \sum_{j=1}^np_j^2&=\sum_{j=1}^n\left(\sum_{i=1}^ma_{ij}\right)^2\\ &=\sum_{j=1}^n\left(\sum_{i=1}^ma_{ij}^2+2\sum_{1\leqslant i_1<i_2\leqslant m}(a_{{i_1}j}a_{{i_2}j})\right)\\ &=\sum_{j=1}^nm+2\sum_{j=1}^n\sum_{1\leqslant i_1<i_2\leqslant m}(a_{{i_1}j}a_{{i_2}j})\\ &=mn+2\sum_{1\leqslant i_1<i_2\leqslant m}\sum_{j=1}^n(a_{{i_1}j}a_{{i_2}j}),\end{split}\]而第 $i_1,i_2$ 行的作答无关等价于\[\sum_{j=1}^n(a_{i_1j}a_{i_2j})=0,\]因此这 $m$ 个同学对 $n$ 道判断题的作答两两无关,那么有\[\sum_{j=1}^np_j^2=mn.\]当 $m=8$,$n=96$ 时,若有 $x$ 道题所有同学作出的判断一致,则\[96\cdot 8=\sum_{j=1}^{96}p_j^2\geqslant x\cdot 8^2\implies x\leqslant 12.\]接下来进行构造,利用递推构造 $H_{2^n}$,其中\[H_2=\begin{bmatrix} 1&1\\ 1&-1 \end{bmatrix},\quad H_{2^{n+1}}=\begin{bmatrix} H_n&H_n\\ H_n&-H_n \end{bmatrix},\]然后得到\[\left[\underbrace{H_8,H_8,\cdots,H_8}_{12~\text{个}}\right],\]就得到了 $x=12$ 的例子.

综上所述,命题得证.

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表回复