题解：P11592 [NordicOI 2024] Chair Game

int_R · 2025-01-22 11:30:35 · 题解

先直接从 IMO2005 预选赛 C7 开始看。

问题：

给定一个长度为 n 的序列 a，保证 n\mid (\sum a_i)。证明存在两个排列 \sigma 与 \tau，使得 \sigma_i+\tau_i\equiv a_i\pmod n。

解：

若存在一个序列 a 和其的一组解 (\sigma,\tau)，同时存在一个序列 b，与 a 有恰好两个位置值不同。考虑通过 a 和 (\sigma,\tau) 得出 b 的一组解 (\sigma',\tau')。如果能够完成这个问题，则证明了原问题。

记两个序列不相同的位置为 i_1,i_2，对于 k\geq 2，i_{k+1} 是唯一满足 \sigma_{i_{k-1}}+\tau_{i_{k+1}}\equiv b_{i_k} 的位置。

引理：记 (p,q) 是 q 最小的，满足 i_p=i_q 的二元组，则一定有 p=1 或 p=2 ^\dagger。

于是我们得到了一组 b 的解 (\sigma',\tau')：

对于 j\neq i_1，\sigma'_j+\tau'_j\equiv b_j 都是根据定义得到的，而 \sum\sigma'_j+\sum\tau'_j=n(n+1)\equiv 0\equiv\sum b_j \pmod n，所以 \sigma'_{i_1}+\tau'_{i_1}\equiv b_{i_1} 自然成立。