以下、\(A_n, B_n\) が任意の高々 \(n\) 次の \(f(x)\) に対して問題文中の条件を満たすように帰納的に構築していきます。便宜上、\(A_n, B_n\) は集合として扱います。

まず、\(A_0 = \{0\}, B_0 = \{1\}\) は条件を満たします。

\(f(x)\) が高々 \(k+1\) 次であるとします。\(g(x) = f(2x + 1) - f(2x)\) によって \(g(x)\) を定めると、\(g(x)\) は高々 \(k\) 次であるので、\(A_k, B_k\) が条件を満たすとき、

\[\begin{aligned} \sum_{x \in A_k} g(x) &= \sum_{x \in B_k} g(x) \\ \sum_{x \in A_k} (f(2x + 1) - f(2x)) &= \sum_{x \in B_k} (f(2x + 1) - f(2x)) \\ \sum_{x \in A_k} f(2x + 1) + \sum_{x \in B_k} f(2x) &= \sum_{x \in B_k} f(2x + 1) + \sum_{x \in A_k} f(2x) \end{aligned}\]

よって、\(A_{k + 1} = \{2x + 1 \, | \, x \in A_k\} \cup \{2x \, | \, x \in B_k\}, B_{k + 1} = \{2x + 1 \, | \, x \in B_k\} \cup \{2x \, | \, x \in A_k\}\) とすると、\(A_{k + 1}, B_{k + 1}\) の要素は distinct であり、\(\sum_{x \in A_{k + 1}} f(x) = \sum_{x \in B_{k + 1}} f(x)\) を満たします。

この手順で \(A_{10}, B_{10}\) を構築すると問題文中の条件を全て満たします。

実装例 (C++)

解答 (Text)