Table of Contents
题目
Women in Action, Inc.的几位主管坐在一张长桌旁，面朝股东。不幸的是，按照会议组织者手里的座位表，她们每个人都坐错了位置。
组织者可以劝说两位主管交换座位，但只有在下面两个条件同时满足时才行：
- 她们当前坐在相邻的位置；
- 她们两人此刻都还没有坐在自己的正确座位上。
问：组织者能否安排一系列这样的交换，最终使每个人都坐到自己的正确座位上？
分析
答案是：能，总能做到。
下面用归纳法证明。
把座位从左到右编号为\(1,2,\cdots,n\)，并且把“本来应该坐在第\(i\)个座位的人”也称作第\(i\)位主管。
我们要证明：只要一开始每个人都坐错了位置，就一定可以通过题目允许的交换，把所有人都送回正确座位。
归纳地说，只要我们能在“左边那些人仍然全都没坐对”的前提下，把某一段最右侧的人都安置好，那么剩下的更左边部分就是一个同类型但规模更小的问题。
因此，关键只在于说明：总能先把第\(n\)位主管送到最右边的第\(n\)个座位上，同时不破坏左边部分“都还没坐对”这一性质。
归纳步骤
观察第\(n\)位主管当前坐在哪里。由于她不在正确位置，所以她一定不在最右端。于是我们尝试把她不断向右移动：每次都和右边紧邻的人交换。
通常这一步是合法的，因为第\(n\)位主管显然还没坐对，而她右边那个人如果也没坐对，就满足题意条件。
但有时会遇到障碍。
假设第\(n\)位主管向右移动时，遇到了第\(i\)位主管坐在第\(i+1\)个位置上。此时如果继续把两人交换，那么第\(i\)位主管就会被换回自己的正确座位\(i\)，这是题目不允许的。
而且更一般地，可能出现如下连续情形：
- 第\(i\)位主管坐在第\(i+1\)个位置；
- 第\(i+1\)位主管坐在第\(i+2\)个位置；
- 第\(i+2\)位主管坐在第\(i+3\)个位置；
- 依此类推。
我们把这样一串连续的人称为一个“封锁段”。它至少包含第\(i\)位主管。
两种情况
情况一：封锁段一直延伸到最右端
如果这个封锁段一直到达第\(n\)个位置，那么我们就直接继续交换。
结果是：第\(i,i+1,\cdots,n\)位主管会依次被送回自己的正确座位，而更左边的人仍然都没坐对。
这样，我们就一下子把最右边一整段都处理完了，归纳即可继续。
情况二：封锁段在中途结束
如果封锁段没有延伸到最右端，设它右边紧挨着的是第\(j\)位主管。
这时我们不让第\(n\)位主管和封锁段最左边的人直接交换，而是改为把第\(j\)位主管一路向左交换，直到她和第\(n\)位主管交换为止。
为什么这一串交换始终合法？
因为第\(j\)位主管一路向左进入的，都是原本属于封锁段成员的位置；这些位置都不是她自己的正确位置，所以她在这个过程中始终不会坐对。另一方面，与她交换的人也都在封锁段里，本来也都没坐对，因此每一步都符合题目规则。
做完这一轮后，第\(n\)位主管就等于又向右前进了一格。于是我们继续把注意力放在第\(n\)位主管身上，重复上面的讨论。
每当再次遇到新的“封锁段”，就同样处理。
如此继续下去，第\(n\)位主管终究会到达最右端的第\(n\)个座位。
而在此过程中，左边尚未处理的人始终都没有被提前送到自己的正确座位上，所以剩下的左边部分仍然是一个规模更小的同类问题。
这就完成了归纳步骤。
结论
由归纳法可知，对于任意\(n\)，只要开始时所有人都坐错了位置，就总能通过题目允许的交换，把所有人最终安排到正确座位上。
因此答案是：可以。
交换次数上界
这个证明还顺便给出了一个交换次数的上界。
在处理第\(n\)位主管的过程中，每一位第\(i\)位主管不可能两次出现在某个封锁段中。因为她一旦处在封锁段里，就会先被向右挪一格，然后又会被第\(n\)位主管超过；之后她就不可能再次构成同样的障碍。
所以，在安置第\(n\)位主管时，相关交换次数不超过\(2(n-1)\)次。
于是总交换次数至多为\(2(1+2+\cdots+(n-1))=n(n-1)\)。也就是说，最多经过\(n(n-1)\)次合法交换，就能让所有人回到自己的正确座位。