Solution. Sandalphon

Description

以下区间均只考虑整数。

给定 $n,k$，将 $1\sim2^n$ 的 $2^n$ 个数划分为两个集合 $A$ 与 $B$，使得 $\forall p\in[0,k]$，有 $\sum_{x\in A}x^p=\sum_{x\in B}x^p$。

$1\le n\le16,0\le k<n$

Solution

经典的等幂和问题，说实话我在考场上觉得多数情况下应该构造不出解，但实际上都是有解的。

我们让 $k$ 始终等于 $n-1$。

首先取 $p=0$，我们有 $|A|=|B|$，所以两个集合的大小都应该是 $2^{n-1}$。

$n=1$ 时只能分成 $\{1\},\{2\}$，同时 $k$ 只能为 $0$，这种情况特判掉。

考虑 $n=2$ 的情形，两个集合应该是 $\{1,4\},\{2,3\}$，如果希望按照类似的方式拓展至 $n=3$，那么等价于将 $\{1,4\},\{2,3\},\{5,8\},\{6,7\}$ 合并为两个集合，需要满足平方之和相等。

容易发现，我们可以错位合并，即合并为 $\{1,4,6,7\},\{2,3,5,8\}$。

事实上，一般的，如果对于 $n=n_0$ 我们构造出 $\{a_i\},\{b_i\}$ 满足题目条件，那么我们同样可以通过错位合并将其拓展到 $n=n_0+1$，即 $\{a_i,b_i+2^{n_0}\},\{b_i,a_i+{2^{n_0}}\}$，考虑证明。

对于 $p\in[0,n_0-1]$，只需证：
$$
\sum_i (a_i+2^{n_0})^p=\sum_i(b_i+2^{n_0})^p
$$
二项式定理展开，
$$
\sum_i\sum_t\binom pta_i^t2^{n_0(p-t)}=\sum_i\sum_t\binom ptb_i^t2^{n_0(p-t)}
$$
交换求和顺序，
$$
\sum_t\binom pt2^{n_0(n-t)}\sum_ia_i^t=\sum_t\binom pt2^{n_0(p-t)}\sum_ib_i^t
$$
显然 $\sum_ia_i^t=\sum_ib_i^t$，于是等式成立。

接下来考虑 $p=n_0$ 的情况，只需证 $\sum_i a_i^{n_0}+\sum_i (b_i+2^{n_0})^{n_0}=\sum_i b_i^{n_0}+\sum_i(a_i+2^{n_0})^{n_0}$。

类似的进行二项式展开后抵消掉相同的部分，相当于仅保留 $t=p=n_0$，我们就得到了：
$$
\sum_i a_i^{n_0}+\sum_i b_i^{n_0}=\sum_i b_i^{n_0}+\sum_i a_i^{n_0}
$$
显然等式成立。

于是对于任意 $n$，我们都可以像这样递推构造出一组解。

Further Reading：Zhihu @陈漱文 等幂和问题系列

Code

namespace Main{
    int n, k;
    vector<int> ans[2];
    void Main(){
        input(n, k);
        puts("1");
        ans[0].push_back(1);
        ans[1].push_back(2);
        if(n > 1){
            for(int i = 0, j = 0; i < n - 1; j += 1 << i, i++){
                for(int k = j + 1; k <= j + (1 << i); k++){
                    ans[0].push_back(ans[1][k-(1<<i)] + (1 << i + 1));
                    ans[1].push_back(ans[0][k-(1<<i)] + (1 << i + 1));
                }
            }
        }
        write(1 << n - 1); putchar(' '); for(int x: ans[0]) write(x), putchar(' ');
        puts("");
        write(1 << n - 1); putchar(' '); for(int x: ans[1]) write(x), putchar(' ');
        return;
    }
} // namespace

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。