Pigeonhole principle: Hang out my socks

對於成對物件A,B，能夠證明N對物件之中，每個物件A和B之間，同時的最大間距是N-1嗎？

問題與距離定義

• 有 $N$ 對物件，記為 $1A,1B,2A,2B,\dots ,NA,NB$，將這 $2N$ 個物件按某種順序排成一列。
• 對於同一號的兩個物件（例如 $iA$ 和 $iB$），定義它們的「間距」為中間隔了多少個物件：若兩者在位置 $x_i<y_i$，則距離 $d_i:=y_i-x_i-1$，相鄰時 $d_i=0$。
• 問題是：在所有可能排列中，能否讓所有 $d_i$ 同時都「至少」某個值 $L$？此時最大的可行 $L$ 是多少？

證明：最大的這個 $L$ 就是 $N-1$。

構造一個使每對距離都為 $N-1$ 的排列

直接給一個排列即可達到 $L=N-1$：

$$1A,2A,3A,\dots ,NA,1B,2B,3B,\dots ,NB.$$

設 $iA$ 在第 $i$ 個位置，$iB$ 在第 $N+i$ 個位置，則

$$d_i=(N+i)-i-1=N-1.$$

因此對於每個 $i=1,\dots ,N$，這個排列都讓 $d_i=N-1$，說明「同時至少 $N-1$」是可以做到的。

為什麼不可能同時讓所有距離 ≥ N？

接下來證明：不可能有任何排列讓所有對的距離都滿足 $d_i\ge N$。

即，不可能有排列使下式成立。

$$\text{對於所有 }i，y_i-x_i-1\ge N$$

由於 $y_i\le 2N$，上式給出

$$x_i\le 2N-(N+1)=N-1.$$

其中 $x_i$ 是第 $i$ 對物件中「靠左」的那一個成員的位置。

這表示：對每一對物件而言，那個「比較左邊」的成員必須出現在位置集合 $\{1,2,\dots ,N-1\}$ 之中。 但一共有 $N$ 對物件，因此有 $N$ 個「靠左的成員」，卻只有 $N-1$ 個位置可以放它們。

這顯然不可能，因為同一個位置不能同時放兩個物件。這是一個典型的抽屜原理（pigeonhole principle）式的矛盾：$N$ 個「物件」要放進 $N-1$ 個「抽屜」，必然有某個抽屜要放至少兩個物件，而我們的排列不允許這樣的情況。

因此假設「所有 $d_i\ge N$」是錯的，也就是說在任何排列中，至少有一對滿足

$$d_i\le N-1.$$

換句話說，「同時最小距離」不可能超過 $N-1$。

與抽屜原理的關係

上述證明的關鍵步驟就是把「每一對的比較左邊成員」看成 $N$ 個「鴿子」，把前 $N-1$ 個位置看成 $N-1$ 個「鴿巢」，然後用抽屜原理得出矛盾。

• 若強迫每一對的距離都至少為 $N$，則每對的較左成員必須塞進前 $N-1$ 個位置。
• 但有 $N$ 對，卻只有 $N-1$ 個位置，必有至少兩個較左成員重疊，違反排列的基本條件。

因此綜合來看：

• $N-1$ 是可以同時達到的距離下界（用排列 $1A,2A,\dots ,NA,1B,2B,\dots ,NB$）。
• 任何企圖把所有距離同時抬到至少 $N$ 都會與抽屜原理矛盾。

所以對於 $N$ 對物件，所有 $A,B$ 之間「同時」能保證的最大最小間距（Maximin Distance），恰好是 $N-1$。