JZTXT

有趣的数列构造问题

发布时间 2023-08-16 14:19:13作者: Arigrain

本文 PDF 下载

能否将 \(1 \sim 2n\) 的整数划分为 \(n\) 对有序数对 \((a_i,b_i)\)，使得 \(\forall 1 \le i \le n\)，有 \(a_i - b_i = i\)？

背景

\(\text{Langford Skolem Pairings}\)

存在性

假设存在这样的划分。则

\[\begin{aligned} \sum_{i=1}^n a_i + \sum_{i=1}^n b_i &= \sum_{i=1}^{2n}i=\dfrac{(1+2n) \times 2n}{2}=n(2n+1)\\ &= \sum_{i=1}^n a_i + \sum_{i=1}^n (a_i + i) = \sum_{i=1}^n 2a_i + \sum_{i=1}^n i = 2\sum_{i=1}^n a_i + \dfrac{n(n+1)}{2} \end{aligned}\\ n(2n+1)=2\sum_{i=1}^n a_i + \dfrac{n(n+1)}{2}\\ n(n-1)\equiv0 \pmod 4\\ \]

则当 \(n\equiv0 \pmod 4\) 或 \(n\equiv 1 \pmod 4\) 时存在这样的划分。

构造

当 \(n=4k\) 时，构造

\(\begin{aligned} &\left(4k + r, 8k − r\right), \qquad & r = 0, 1, \cdots, 2k − 1\\ &\left(2k + 1, 6k\right), \left(2k, 4k − 1\right),\\ &\left(r, 4k − 1 − r\right), \qquad & r = 1, 2, \cdots, k − 1\\ &\left(k, k + 1\right),\\ &\left(k + 2 + r, 3k − 1 − r\right), \qquad & r=0, 1, \cdots, k − 3\\ \end{aligned}\)

当 \(n=4k+1\) 时，构造

\(\begin{aligned} &(4k + 2 + r, 8k + 2 − r) &r = 0, 1, \cdots, 2k − 1,\\ &(2k + 1, 6k + 2), (2k + 2, 4k + 1),\\ &(r, 4k + 1 − r) &r = 1, 2, \cdots , k,\\ &(k + 1, k + 2),\\ &(k + 2 + r, 3k + 1 − r) &r = 1, 2, \cdots , k − 2\\ \end{aligned}\)