2018-北京卷理-20 解-新定义运算

本题导读

本题考查新定义运算。核心在于新定义理解法、分类讨论法的灵活运用。

📌【题干】

Question

（2018年北京卷理）设 $n$ 为正整数，集合 $A=\{\alpha \mid \alpha =(t_1,t_2,\dots ,t_n),t_k\in \{0,1\},k=1,2,\dots ,n\}$.

对于集合 $A$ 中的任意元素 $\alpha =(x_1,x_2,\dots ,x_n)$ 和 $\beta =(y_1,y_2,\dots ,y_n)$，记：

$M(\alpha ,\beta )=\frac{1}{2}{\sum }_{i=1}^n(x_i+y_i-|x_i-y_i|)$

(1) 当 $n=3$ 时，若 $\alpha =(1,1,0)$，$\beta =(0,1,1)$，求 $M(\alpha ,\alpha )$ 和 $M(\alpha ,\beta )$ 的值；

(2) 当 $n=4$ 时，设 $B$ 是 $A$ 的子集，且满足：对于 $B$ 中的任意元素 $\alpha ,\beta$，当 $\alpha ,\beta$ 相同时，$M(\alpha ,\beta )$ 是奇数；当 $\alpha ,\beta$ 不同时，$M(\alpha ,\beta )$ 是偶数.求集合 $B$ 中元素个数的最大值；

(3) 给定 $n\ge 2$，设 $B$ 是 $A$ 的子集，且满足：对于 $B$ 中的任意两个不同的元素 $\alpha ,\beta$，$M(\alpha ,\beta )=0$.写出一个集合 $B$，使其元素个数最多，并说明理由.

🔍【思路分析】

破题导航

1. 透析新定义：

注意到 $\frac{1}{2}(x+y-|x-y|)$ 实际上是 $\min (x,y)$。

所以 $M(\alpha ,\beta )$ 的本质是：向量 $\alpha$ 和 $\beta$ 在相同位置上同时为 1 的次数总和。

• $M(\alpha ,\alpha )$ 就是向量 $\alpha$ 中 1 的个数。

2. 第二问（奇偶性约束）：

• $M(\alpha ,\alpha )$ 为奇数 $⟹$ 向量 $\alpha$ 中 1 的个数为 1 或 3。

• $M(\alpha ,\beta )$ 为偶数 $⟹$ $\alpha$ 和 $\beta$ 不能在两个以上的位置同时为 1（因为 $n=4$，交集只能是 0, 2, 4，而 4 是相向，所以不同元素交集只能是 0 或 2）。

• 这是一个搜索与排除的过程，利用分组矛盾法证明最大值为 4。

3. 第三问（互斥构造）：

• $M(\alpha ,\beta )=0$ 意味着任意两个不同的向量不能在同一个位置同时为 1。

• 想象 $n$ 个位置，每个位置“名花有主”，再加上一个全 0 向量。

✅【答案】

点击查看答案

(1) $M(\alpha ,\alpha )=2$，$M(\alpha ,\beta )=1$

(2) 最大值为 $4$

(3) 最大值为 $n+1$

✍【详细解析】

Abstract

(1)解：

根据定义 $M(\alpha ,\beta )=\sum \min (x_i,y_i)$：

• $\alpha =(1,1,0)$，则 $M(\alpha ,\alpha )=\min (1,1)+\min (1,1)+\min (0,0)=1+1+0=2$。

• $\beta =(0,1,1)$，则 $M(\alpha ,\beta )=\min (1,0)+\min (1,1)+\min (0,1)=0+1+0=1$。

(2)解：

设 $\alpha \in B$，则 $M(\alpha ,\alpha )=\sum x_i$ 为 $\alpha$ 中 1 的个数。

由题意，$M(\alpha ,\alpha )$ 是奇数，故 $\alpha$ 中 1 的个数为 1 或 3。

若 $n=4$，满足此条件的元素共有 $C_4^1+C_4^3=4+4=8$ 个。

我们将这 8 个元素配对：

• $G_1=\{(1,0,0,0),(1,1,1,0)\}$, $M=1$ (奇)

• $G_2=\{(0,1,0,0),(0,1,1,1)\}$, $M=1$ (奇)

• $G_3=\{(0,0,1,0),(1,0,1,1)\}$, $M=1$ (奇)

• $G_4=\{(0,0,0,1),(1,1,0,1)\}$, $M=1$ (奇)

由于每组中两个元素的 $M$ 值为 1（奇数），不满足“不同元素 $M$ 为偶数”的条件，故每组至多选一个。

因此 $|B|\le 4$。

取 $B=\{(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)\}$，任意两个不同元素 $M=0$（偶数），符合题意。

故最大值为 4。

(3)解：

要使 $M(\alpha ,\beta )=0$，即任意两个不同向量在相同位置不能同时为 1。

构造集合 $B$ 如下：

• $e_1=(1,0,0,\dots ,0)$

• $e_2=(0,1,0,\dots ,0)$

• $\dots$

• $e_n=(0,0,0,\dots ,1)$

• $e_{n+1}=(0,0,0,\dots ,0)$

此时 $|B|=n+1$。

理由：

对于 $B$ 中任意两个不同元素，要么其中一个是全 0 向量（此时 $M=0$），要么是两个不同的单位向量（此时在每个位置上 $\min (x_i,y_i)$ 至少有一个是 0，故 $M=0$）。

证明最大性：

若 $|B|>n+1$，根据抽屉原理，除去全 0 向量外，至少有 $n$ 个向量。若其中有两个向量在某位置 $k$ 同时为 1，则 $M\ge 1$。要使 $M=0$，每个位置 $k\in \{1,\dots ,n\}$ 最多只能被一个向量占用。

因此，最多只能有 $n$ 个“含 1 向量”和 1 个“全 0 向量”。

最大元素个数为 $n+1$。

💡【考点归纳与避坑指南】

Danger

1. 翻译新定义是第一关：如果死磕 $\frac{1}{2}(x+y-|x-y|)$ 这个公式，计算量会爆炸。将其识别为 $\min (x,y)$ 是解题的“题眼”。

2. 单位向量的妙用：在处理这类 0-1 向量问题时，标准的基向量（只有一个位置为 1）通常是构造最优解的核心。

3. 北京卷的压轴逻辑：从具体 ($n=3$) 到局部 ($n=4$) 再到一般化推广 ($n$)，这是非常经典的科学思维路径。

📖【试题探源与推广】

Tip

在 Obsidian 笔记中，可以建立一个【信息论基础】的关联：

• 汉明距离 (Hamming Distance)：两个等长字符串之间相同位置上不同字符的个数。

• 本题联系：本题的 $M(\alpha ,\beta )$ 实际上与汉明距离 $d(\alpha ,\beta )$ 有关：$d(\alpha ,\beta )=M(\alpha ,\alpha )+M(\beta ,\beta )-2M(\alpha ,\beta )$。

• 编码理论：这种构造“互斥”集合的问题，在计算机纠错码设计中非常关键。

🔗【关联脉络】

Multi column

知识锚点 (Nodes)

• 01.01集合的含义、表示与基本运算

• 22.01 计数原理、排列与组合

类题演练 (Links)

• 2001-上海卷理-10 填-新定义运算

• 2003-全国卷理-22乙

• 2005-湖北卷理-01 单-集合的新定义运算