查看数据源：59799b060a41cd000ac58d81
设 $S$ 是一些互不相同的 $4$ 元数组 $(a_1,a_2,a_3,a_4)$ 的集合，其中 $a_i=0$ 或 $1$，$i=1,2,3,4$．已知 $S$ 的元素个数不超过 $15$ 且满足：若 $(a_1,a_2,a_3,a_4),(b_1,b_2,b_3,b_4) \in S$，则$$(\max\{a_1,b_1\},\max\{a_2,b_2\},\max\{a_3,b_3\},\max\{a_4,b_4\}) \in S$$且$$(\min\{a_1,b_1\},\min\{a_2,b_2\},\min\{a_3,b_3\},\min\{a_4,b_4\} ) \in S,$$求 $S$ 的元素个数的最大值．
【难度】
【出处】
2010年全国高中数学联赛甘肃省预赛
【标注】
  • 数学竞赛
    >
    简单组合
    >
    简单组合
  • 题型
    >
    组合数学
    >
    组合极值
【答案】
$12$
【解析】
显然所有可能的 $4$ 元数组有 $16$ 种．
因为至少有一个 $4$ 元数组不在 $S$ 中，所以 $(1,0,0,0)$，$(0,1,0,0)$，$(0,0,1,0)$ 和 $(0,0,0,1)$ 中至少有一个不在 $S$ 中，若不然由题中条件可推出所有那样的 $4$ 元数组都在 $S$ 中，不妨设 $(1,0,0,0)\not \in S$．
此时由题中条件知 $(1,1,0,0)$，$(1,0,1,0)$ 和 $(1,0,0,1)$ 中至少有 $2$ 个不能在 $S$ 中，不妨设 $(1,1,0,0)$ 和 $(1,0,1,0)$ 不在 $S$ 中．
又因为 $(1,1,1,0)$ 和 $(1,0,0,1)$ 不能同时在 $S$ 中，不妨设 $(1,1,1,0)$ 不在 $S$ 中，于是 $S$ 中的元素个数不超过个 $16-4=12$ 个．
现在设 $S$ 是所有可能的 $16$ 个 $4$ 元数组中去掉 $(1,0,0,0)$，$(1,1,0,0)$，$(1,0,1,0)$ 和 $(1,1,1,0)$ 后所组成的集合，我们要证 $S$ 满足题中条件，从而 $S$ 的元素个数的最大值为 $12$．
任取$$(a_1,a_2,a_3,a_4),(b_1,b_2,b_3,b_4) \in S.$$情形一若 $a_1=b_1=0$ 或 $a_4=1$ 或 $b_4=1$，则显然$$(\max\{a_1,b_1\},\max\{a_2,b_2\},\max\{a_3,b_3\},\max\{a_4,b_4\} )$$不等于上述去掉的 $4$ 个 $4$ 元数组中任何一个，从而属于 $S$．
同理$$(\min\{a_1,b_1\},\min\{a_2,b_2\},\min\{a_3,b_3\},\min\{a_4,b_4\} )\in S.$$情形二若 $a_1=1$ 或 $b_1=1$ 且 $a_4=b_4=0$，则$$(\max\{a_1,b_1\},\max\{a_2,b_2\},\max\{a_3,b_3\},\max\{a_4,b_4\} )=(1,\max\{a_2,b_2\},\max\{a_3,b_3\},0),$$由此推出 $(a_1,a_2,a_3,a_4)$ 或 $(b_1,b_2,b_3,b_4)$ 不属于 $S$，这种情况不会出现．
情形三若 $a_1=0$ 或 $b_1=0$ 或 $a_4=b_4=1$，则显然$$(\min\{a_1,b_1\},\min\{a_2,b_2\},\min\{a_3,b_3\},\min\{a_4,b_4\} )$$不等于上述去掉的 $4$ 个 $4$ 元数组中任何一个，从而属于 $S$．
情形四若 $a_1=b_1-1$ 且 $a_4=0$ 或 $b_4=0$，则$$(\min\{a_1,b_1\},\min\{a_2,b_2\},\min\{a_3,b_3\},\min\{a_4,b_4\} )=(1,\min\{a_2,b_2\},\min\{a_3,b_3\},0),$$由此推出 $(a_1,a_2,a_3,a_4)$ 或 $(b_1,b_2,b_3,b_4)$ 不属于 $S$，这种情况也不会出现．
综上所述，$S$ 是满足题目要求的，故 $S$ 的元素个数最大值是 $12$．
答案 解析 备注
0.116706s