【BICMR 怀新一题】人偶之舞题解

math

analysis

solution

Author

sun123zxy

Published

January 17, 2025

题目出处，官方解答点评．上个月随便做了一下，估出的上界还差了个常数，所以没有提交．放在这里吧．

记 \(m = 100\)．题目等价于：

寻找各人偶速度 \(v_1,\dots,v_m \in \mathbb R / \mathbb Z\)，使得对任意的人偶起始位置 \(a_1,\dots,a_m \in \mathbb R / \mathbb Z\)，存在数列 \(N_k \subseteq \mathbb N\) 使得 Shanghai 人偶旋转 \(N_k\) 圈后，各人偶位置 \(x_{i,N_k} := a_i - N_k v_i\) 满足 \[ \max_{1 \leq i \leq m} |x_{i,N_k}| = O(N_k^{-1/m}), \quad k \to \infty \] 这里 \(| \cdot |\) 表示与 \(0\) 在 \(\mathbb R / \mathbb Z\) 中的距离．

任取 \(p\) 是任意大于 \(2\) 的正整数．对任意 \(1 \leq i \leq m\)，取 \[ v_i = \sum_{k=0}^{+\infty} p^{-(m (2^k-1) + i2^k)} \] 则 Shanghai 人偶旋转 \(n_{i,k} := p^{m(2^k-1)+(i-1)2^k}\) 圈时，第 \(i\) 个人偶的位移量在 \(p,m\) 视为常数，\(i\) 作为参数，\(k \to +\infty\) 时有渐进估计 \[ \begin{aligned} n_{i,k} v_i &= p^{m(2^k-1)+(i-1)2^k} p^{-(m (2^k-1) + i2^k)} + \dots \\ &= p^{-2^k} + O(p^{-2^k}) \\ &= p^{(i-1)2^k/m-1} n_k^{-1/m} + O(n_k^{-1/m}) \\ &= \Theta (n_{i,k}^{-1/m}) \end{aligned} \] 对任意 \(1 \leq j \leq m\) 使得 \(j \neq i\)，第 \(j\) 个人偶的位移量也有渐进估计 \[ |n_{i,k} v_j| = |p^{m(2^k-1)+(i-1)2^k} v_j| \leq 2 p^{m(2^k-1)+(i-1)2^k} p^{-(m (2^k-1) + (i+1)2^k)} = 2 p^{-2 \cdot 2^k} = O(n_{i,k}^{-2/m}) \]

现在，只需 Shanghai 人偶旋转至多 \(n'_{i,k} := \left\lceil \frac{1}{n_{i,k}v_i} \right\rceil n_{i,k} = O(n_{i,k}^{1/m + 1})\) 圈，就可使第 \(i\) 个人偶的位移量 \(n'_{i,k} v_i\) 满足 \(|a_i - n'_{i,k} v_i| = O(n_{i,k}^{-1/m})\)，而其它人偶的位移量 \[ n'_{i,k} v_j = \left\lceil \frac{1}{n_{i,k}v_i} \right\rceil n_{i,k} v_j = O(n_{i,k}^{1/m}) O(n_{i,k}^{-2/m}) = O(n_{i,k}^{-1/m}) \]

故我们让 Shanghai 人偶旋转 \(N_k := \sum_{1\leq i \leq m} n'_{i,k}\) 圈．此时对任意 \(1 \leq i \leq m\)， \[ \begin{aligned} x_{i,N_k} &= a_i - N_k v_i \\ &= a_i - n'_{i,k} v_i - \sum_{j \neq i} n'_{j,k} v_i \\ &= O(n_{i,k}^{-1/m}) + \sum_{j \neq i} O(n_{j,k}^{-1/m}) \\ &= O\left( \left(\min_{1 \leq j \leq n} n_{j,k}\right)^{-1/m} \right) \end{aligned} \] 注意到 \[ \begin{aligned} \frac {N_k^{m/(2m-1)}} {\min_{1 \leq j \leq n} n_{j,k}} &\leq \frac{(m n_{i,m})^{m/(2m-1)}}{n_{i,1}} \\ &= O \left( \frac{p^{(m(2^k-1)+(m-1)2^k) \cdot m/(2m-1)}}{p^{m(2^k-1)}} \right) \\ &= O ( 1 ) \end{aligned} \] 故 \[ x_{i,N_k} = O(N_k^{(-1/m) \cdot m/(2m-1)}) = O(N_k^{-1/(2m-1)}) \] 此估计与 \(i\) 无关，故 \[ \max_{1 \leq i \leq m} |x_{i,N_k}| = O(N_k^{-1/(2m-1)}) \]