题目

查看数据源：5cac2d7a210b28193dc2e901

给定正整数 $n\left( n\geqslant 3 \right)$ 。对于 $1\text{,}2\text{,}\cdots \text{,}n$ 的任意一个排列 $P\text{=}\left( {{x}_{1}}\text{,}{{x}_{2}}\text{,}\cdots \text{,}{{x}_{n}} \right)$，若 $i$ < $j$ < $k$，则称 ${{x}_{j}}$ 介于 ${{x}_{i}}$ 和 ${{x}_{k}}$ 之间（如在排列 $\left( 1\text{,}3\text{,}2\text{,}4 \right)$ 中，$3$ 介于 $1$ 和 $4$ 之间，$4$ 不介于 $1$ 和 $2$ 之间）。设集合 $S\text{=}\left\{ {{P}_{1}}\text{,}{{P}_{2}}\text{,}\cdots \text{,}{{P}_{m}} \right\}$ 的每个元素 ${{P}_{i}}$ 是 $1\text{,}2\text{,}\cdots \text{,}n$ 的排列。已知 $\left\{ 1\text{,}2\text{,}\cdots \text{,}n \right\}$ 的任意三个不同数中都有一个数，它在每个 ${{P}_{i}}\left( 1\leqslant i\leqslant m \right)$ 中都不介于另外两个数之间。求 $m$ 的最大值。

【难度】

【出处】

2010第9届CGMO试题

【标注】

知识点
>
二试组合部分

【答案】

${{2}^{n-1}}$

【解析】

首先，用数学归纳法证明：$m\leqslant {{2}^{n-1}}$ 。当 $n\text{=}3$ 时，由条件知在1、2、3种必然存在一个数（不妨设为1），它在每个 ${{P}_{i}}$ 中国年都不介于另外两个数之间。因此排列（1，2，3）与排列（3，1，2）都不能出现。于是，可能出现的排列至多有 $3\text{!}-2\text{=}4$ 个，结论成立。假设 $m\leqslant{{2}^{n-1}}$ 对 $n\text{=}k-1$ 成立，考虑 $n\text{=}k$ 的情况。对 $m$ 个 $1,2,\cdots ,k$ 的排列中的每一个，把 $k$ 从排列中去掉，得到一个 $1,2,\cdots,k-1$ 的排列。这样的排列必然满足原题在 $n\text{=}k-1$ 时的条件，由归纳假设知这样的排列最多只有 ${{2}^{k-2}}$ 个。下面只需证明：最多只有两个 $1\text{,}2\text{,}\cdots\text{,}k$ 的排列可能对应同一个 $1,2,\cdots ,k-1$ 的排列。从而，所有排列至多有 ${{2}^{k-2}}\times2\text{=}{{2}^{k-1}}$ 个。假设不然，则存在三个 $1\text{,}2\text{,}\cdots\text{,}k$ 的排列对应同一个 $1,2,\cdots ,k-1$ 的排列。由对称性不妨设这个 $1,2,\cdots ,k-1$ 的排列就是 $1,2,\cdots,k-1$，而在三个 $1\text{,}2\text{,}\cdots \text{,}k$ 的排列 ${{P}_{1}}$、${{P}_{2}}$、${{P}_{3}}$ 中，$k$ 分别在第 $a$、$b$、$c$ $\left( 1\leqslant a \right.$ < $b$ < $c\leqslant \left. n \right)$ 位。考虑 $a$、$b$、$k$ 三个数。在排列 ${{P}_{1}}=\left\{1,2,\cdots ,a-1,k,a,a+1,\cdots k-1 \right\}$ 中，这三个数的顺序为 $k$、$a$、$b$，$a$ 介于其他两个数之间；在排列 ${{P}_{2}}=\left\{1,2,\cdots ,b-1,k,b,b+1,\cdots k-1 \right\}$ 中，这三个数的顺序为 $a$、$k$、$b$，$k$ 介于其他两个数之间；在排列 ${{P}_{3}}=\left\{1,2,\cdots ,c-1,k,c,c+1,\cdots k-1 \right\}$ 中，这三个数的顺序为 $a$、$b$、$k$，$b$ 介于其他两个数之间。于是，这三个数中的每个数都曾经介于其他两个数之间，与题目条件矛盾。因此，假设不成立，即当 $n\text{=}k$ 时，也有 $m\leqslant{{2}^{n-1}}$ 成立。至此证明了 $m\leqslant {{2}^{n-1}}$ 。其次，给出一个 $m\text{=}{{2}^{n-1}}$ 的例子。用如下方法构造 $1,2,\cdots,n$ 的排列：先放置1，当 $1,2,\cdots ,r\left( 1\leqslant r\leqslant n-1 \right)$ 都放置好后，将 $r+1$ 放置在前 $r$ 个数的最左侧或者最右侧，这样，2到 $n$ 中的每个正整数都有两个可选择的位置。由乘法原理知，这样的排列共有 ${{2}^{n-1}}$ 个。对于 $1,2,\cdots,n$ 中任意三个数 $a$ < $b$ < $c$，有构造知在每个排列中，$c$ 或者在 $a$ 和 $b$ 的左侧，或者在 $a$ 和 $b$ 的右侧，永远不会介于 $a$ 和 $b$ 之间。故这样的 ${{2}^{n-1}}$ 个排列满足题目条件。综上，$m$ 的最大值为 ${{2}^{n-1}}$ 。

答案解析

首先，用数学归纳法证明：$m\leqslant {{2}^{n-1}}$ 。 当 $n\text{=}3$ 时，由条件知在1、2、3种必然存在一个数（不妨设为1），它在每个 ${{P}_{i}}$ 中国年都不介于另外两个数之间。因此排列（1，2，3）与排列（3，1，2）都不能出现。于是，可能出现的排列至多有 $3\text{!}-2\text{=}4$ 个，结论成立。假设 $m\leqslant{{2}^{n-1}}$ 对 $n\text{=}k-1$ 成立，考虑 $n\text{=}k$ 的情况。对 $m$ 个 $1,2,\cdots ,k$ 的排列中的每一个，把 $k$ 从排列中去掉，得到一个 $1,2,\cdots,k-1$ 的排列。这样的排列必然满足原题在 $n\text{=}k-1$ 时的条件，由归纳假设知这样的排列最多只有 ${{2}^{k-2}}$ 个。 下面只需证明：最多只有两个 $1\text{,}2\text{,}\cdots\text{,}k$ 的排列可能对应同一个 $1,2,\cdots ,k-1$ 的排列。从而，所有排列至多有 ${{2}^{k-2}}\times2\text{=}{{2}^{k-1}}$ 个。 假设不然，则存在三个 $1\text{,}2\text{,}\cdots\text{,}k$ 的排列对应同一个 $1,2,\cdots ,k-1$ 的排列。由对称性不妨设这个 $1,2,\cdots ,k-1$ 的排列就是 $1,2,\cdots,k-1$，而在三个 $1\text{,}2\text{,}\cdots \text{,}k$ 的排列 ${{P}_{1}}$、${{P}_{2}}$、${{P}_{3}}$ 中，$k$ 分别在第 $a$、$b$、$c$ $\left( 1\leqslant a \right.$ < $b$ < $c\leqslant \left. n \right)$ 位。 考虑 $a$、$b$、$k$ 三个数。在排列 ${{P}_{1}}=\left\{1,2,\cdots ,a-1,k,a,a+1,\cdots k-1 \right\}$ 中，这三个数的顺序为 $k$、$a$、$b$，$a$ 介于其他两个数之间；在排列 ${{P}_{2}}=\left\{1,2,\cdots ,b-1,k,b,b+1,\cdots k-1 \right\}$ 中，这三个数的顺序为 $a$、$k$、$b$，$k$ 介于其他两个数之间；在排列 ${{P}_{3}}=\left\{1,2,\cdots ,c-1,k,c,c+1,\cdots k-1 \right\}$ 中，这三个数的顺序为 $a$、$b$、$k$，$b$ 介于其他两个数之间。 于是，这三个数中的每个数都曾经介于其他两个数之间，与题目条件矛盾。因此，假设不成立，即当 $n\text{=}k$ 时，也有 $m\leqslant{{2}^{n-1}}$ 成立。至此证明了 $m\leqslant {{2}^{n-1}}$ 。 其次，给出一个 $m\text{=}{{2}^{n-1}}$ 的例子。用如下方法构造 $1,2,\cdots,n$ 的排列：先放置1，当 $1,2,\cdots ,r\left( 1\leqslant r\leqslant n-1 \right)$ 都放置好后，将 $r+1$ 放置在前 $r$ 个数的最左侧或者最右侧，这样，2到 $n$ 中的每个正整数都有两个可选择的位置。由乘法原理知，这样的排列共有 ${{2}^{n-1}}$ 个。 对于 $1,2,\cdots,n$ 中任意三个数 $a$ < $b$ < $c$，有构造知在每个排列中，$c$ 或者在 $a$ 和 $b$ 的左侧，或者在 $a$ 和 $b$ 的右侧，永远不会介于 $a$ 和 $b$ 之间。 故这样的 ${{2}^{n-1}}$ 个排列满足题目条件。综上，$m$ 的最大值为 ${{2}^{n-1}}$ 。