题目

查看数据源：599165b82bfec200011de732

已知集合 ${S_n} = \left\{ X \left| \right.X = \left({x_1},{x_2}, \ldots ,{x_n}\right),{x_i} \in \left\{ 0,1\right\} ,i = 1,2, \cdots ,n\right\} \left(n \geqslant 2\right)$，对于 $A = \left({a_1},{a_2}, \cdots , {a_n} \right)$，$B = \left({b_1},{b_2}, \cdots {b_n},\right) \in {S_n}$，定义 $ A $ 与 $ B $ 的差为 $A - B = \left(|{a_1} - {b_1}|,|{a_2} - {b_2}|, \cdots ,|{a_n} - b_n|\right)$；$ A $ 与 $ B $ 之间的距离为 $\displaystyle d\left(A,B\right) = \sum\limits_{i = 1}^{n} |{a_i} - {b_i}|$．

【难度】

【出处】

无

【标注】

证明：$\forall A,B,C \in {S_n}$，有 $A - B \in {S_n}$，且 $d\left(A - C,B - C\right) = d\left(A,B\right)$；
标注
答案

解析

设\[A = \left({a_1},{a_2}, \cdots ,{a_n}\right) , B = \left({b_1},{b_2},\cdots,{b_n}\right) , C = \left({c_1},{c_2},\cdots,{c_n}\right) \in {S_n}, \]因为 ${a_i} , {b_i} \in \left\{ {0,1} \right\}$，所以\[|{a_i} - {b_i}| \in \left\{ {0,1} \right\} , \left(i = 1,2,\cdots,n\right),\]从而\[A - B = \left(|{a_1} - {b_1}|,|{a_2} - {b_2}|,\cdots,|{a_n} - {b_n}|\right) \in {S_n}.\]又\[d\left(A - C,B - C\right) = \sum\limits_{i = 1}^n {||{a_i} - {c_i}|} - |{b_i} - {c_i}||,\]由题意知\[{a_i} , {b_i} , {c_i} \in \left\{ {0,1} \right\} \left(i = 1,2,\cdots,n\right).\]当 ${c_i} = 0$ 时，\[||{a_{i }}-{c_i}| - |{b_i} - {c_i}|| = |{a_i} - {b_i}| ;\]当 ${c_i} = 1$ 时，\[||{a_{i }}-{c_i}| - |{b_i} - {c_i}|| = |\left(1 - {a_i}\right) - \left(1 - {b_i}\right)| = |{a_i} - {b_i}|,\]所以\[d\left(A - C,B - C\right) = \sum\limits_{i = 1}^n {|{a_i} - {b_i}|} = d\left(A,B\right).\]
证明：$\forall A,B,C \in {S_n}$，$ d\left(A,B\right)$，$d\left(A,C\right)$，$d\left(B,C\right)$ 三个数中至少有一个是偶数；
标注
答案

解析

设\[A = \left({a_1},{a_2},\cdots,{a_n}\right) , B = \left({b_1},{b_2},\cdots,{b_n}\right) , C = \left({c_1},{c_2},\cdots,{c_n}\right) \in {S_n},\]\[d\left(A,B\right) = k , d\left(A,C\right) = l , d\left(B,C\right) = h .\]记 $O = \left(0,0,\cdots,0\right) \in {S_n}$，由（1）可知
$d\left(A,B\right) = d\left(A - A,B - A\right) = d\left(O,B - A\right) = k$，
$d\left(A,C\right) = d\left(A - A,C - A\right) = d\left(O,C - A\right) = l$，
$d\left(B,C\right) = d\left(B - A,C - A\right) = h$，
所以 $|{b_i} - {a_i}|\left(i = 1,2,\cdots,n\right)$ 中 $ 1 $ 的个数为 $k$，$|{c_i} - {a_i}|\left(i = 1,2,\cdots,n\right)$ 中 $ 1 $ 的个数为 $l$．
设 $t$ 是使 $|{b_i} - {a_i}| = |{c_i} - {a_i}| = 1$ 成立的 $i$ 的个数，则 $h = l + k - 2t$．
由此可知，$k,l,h$ 三个数不可能都是奇数，
即 $d\left(A,B\right)$，$d\left(A,C\right)$，$d\left(B,C\right)$ 三个数中至少有一个是偶数．
设 $ P \subseteq {S_n}$，$ P $ 中有 $ m\left(m\geqslant 2\right) $ 个元素，记 $ P $ 中所有两元素间距离的平均值为 $\overline d \left(P\right)$．证明：$\overline d \left(P\right)\leqslant \dfrac{mn}{2\left(m - 1\right)}$．
标注
答案

解析

$\displaystyle \overline d \left(P\right) = \dfrac{1}{{\mathrm {C}}_m^2}\sum\limits_{A,B \in P} {d\left(A,B\right)} $，其中 $\displaystyle \sum\limits_{A,B \in P} {d\left(A,B\right)} $ 表示 $P$ 中所有两个元素间距离的总和，
设 $P$ 中所有元素的第 $i$ 个位置的数字中共有 ${t_i}$ 个 $ 1 $，$m - {t_i}$ 个 $ 0 $，则\[\sum\limits_{A,B \in P} {d\left(A,B\right)} = \sum\limits_{i = 1}^n {t_i} \left(m - {t_i}\right).\]由于\[{t_i} \left(m - {t_i}\right) \leqslant \dfrac{m^2}{4}\left(i = 1,2,\cdots,n\right),\]所以\[\sum\limits_{A,B \in P} {d\left(A,B\right)} \leqslant \dfrac{{n{m^2}}}{4} ,\]从而\[ \overline d \left(P\right) = \dfrac{1}{{{\mathrm {C}}_m^2}}\sum\limits_{A,B \in P} {d\left(A,B\right)} \leqslant {\dfrac{nm^2}{4{\mathrm {C}}_m^2}} = \dfrac{mn}{2\left(m - 1\right)} . \]