环形奇偶元素分划的必需要块数证明及一般化问题

咱们先把问题的核心规则再明确一遍：

• 分划的每个块里只能全是奇数或全是偶数，不能混放；
• 任意两个块不能交叉（也就是不存在四个数按环形顺序a,b,c,d，其中a,c在一个块，b,d在另一个块）；
• 给定奇数的分划后，偶数的分划要尽可能把相邻偶数合并成最大的块（也就是不能再合并更大的块了）。

从具体例子入手理解 #

比如你提到的1到12的例子：

• 奇数分划成{1,7,9}, {3}, {5}, {11}（共4块）；
• 对应的最优偶数分划是{2,4,6}, {8}, {10,12}（共3块）；
• 总块数4+3=7，正好是6+1（这里6是奇数/偶数的数量，即n=6，2n=12）。

再看两种极端情况：

1. 所有奇数合并成1块：此时偶数无法合并（任何两个偶数之间都隔着奇数块的部分，合并会导致交叉），所以每个偶数单独成块，总块数1+6=7；
2. 每个奇数单独成块：此时所有偶数可以合并成1块，总块数6+1=7。

不管怎么调整奇数的分划，总块数都是7，这不是巧合，而是有普遍规律的。

一般化问题的核心：Kreweras补的性质 #

题目里提到，偶数的最优分划其实是奇数分划的Kreweras补，这是组合数学中非交叉分划的一个关键概念。对于n个元素的环形非交叉分划P，它的Kreweras补Q也是一个非交叉分划，并且有一个固定的性质：

分划P的块数 + 分划Q的块数 = n + 1

这里的n就是奇数（或偶数）的数量，对应到1到2n的全部分划，总块数就是n+1。

为什么这个性质成立？ #

我们可以用归纳法简单验证：

• 基例n=1：2个数1和2，奇数分划只能是{1}（1块），偶数分划是{2}（1块），1+1=2=1+1，成立；
• 归纳假设：假设对于n=t，任意环形非交叉分划P的块数k，其Kreweras补Q的块数m满足k+m=t+1；
• 归纳步骤：对于n=t+1，取环形排列中的任意一个奇数块，把其中相邻的两个奇数合并成一个“超级奇数”，得到t个元素的环形非交叉分划P'，块数k'=k-1。根据归纳假设，P'的Kreweras补Q'的块数m'=t+1 -k'。而原分划Q的块数m=m'+1（因为合并的两个奇数之间的偶数会单独成一个块），所以k+m=(k-1)+(m'+1)=k'+m'=t+1，对应n=t+1时，总块数是(t+1)+1=t+2，符合规律。

换句话说，不管怎么分奇数，对应的最优偶数分划的块数都会和奇数块数互补，加起来正好是n+1，所以总块数是固定的。

结论 #

对于1到2n的环形分划，满足题目三个规则的总块数一定是n+1。回到1到12的情况，n=6，所以总块数是7，和例子完全一致。

备注：内容来源于stack exchange，提问作者Bart