自动搬运

查看原文

来自洛谷，原作者为

	Caro23333 Dream Theater 脑残粉

搬运于2025-08-24 22:07:49，当前版本为作者最后更新于2019-02-15 17:17:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这里出题组......来水一下社区贡献

首先考虑一个包含$2^k$个点的图，每个点对应一个任务子集。两个点之间连一条无向边，当且仅当这两个点对应的任务子集大小差为1.

那么，满足条件的一种安排任务的方式，就对应着一条从某个节点开始，经过图中所有边恰好一次再回到这个节点的路径，或者说，一条欧拉回路。

由小学奥数的经典结论（），一个无向图中存在欧拉回路，当且仅当每个点的度数均为偶数。

假设某个点对应的任务子集的大小为$t$，那么它将向所有对应集合大小为$t-1$和$t+1$的点连边。不难发现，这样的边共有$C_{k}^{t-1}+C_{k}^{t+1}$条。

进行简单的推导可以得出，使得每个点的度数均为偶数的$k$会满足将$C_{k}^{0},C_{k}^{1},\dots,C_{k}^{k}$排成一列之后是奇偶相间的。

然后怎么做呢？ 做为一名合格的OIer，我们要拥有良好的打表找规律能力。

于是写一个50pts的暴力，观察一下答案，发现满足条件的$k$必然可以表示为$2^m-2$，其中$m$是一个大于等于2的整数。

提交，AC，皆大欢喜（

为什么这个规律是这样呢？

考虑模2意义下的杨辉三角的第$k$行，不难发现这一行是$10101\dots10101$等价于第$k+2$行是$1000\dots0001$。

下证$k$是$2$的整数次幂且$4\le k$是杨辉三角的第$k$行为$1000\dots0001$的充要条件（以下所有推导中，$k/2$表示其向下取整的值）。

先证充分性：

假设对于所有$k\le 2^m$充分性成立。 当$k=2^{m+1}$时：

由Lucas定理得$C_{2^{m+1}}^{t}=C_{2^m}^{t/2}$ $C_{0}^{t\%2}$，由于对于所有$k\le 2^m$充分性成立，不难发现此式取$1$当且仅当$t=0$或$t=2^{m+1}$，则对于$k\le 2^{m+1}$其充分性成立，由归纳法得证（归纳初条件显然可证）。

再证必要性：

假设对于所有$k\le 2^m$必要性成立。

若存在$2^m<k<2^{m+1}$满足条件，则对于任意$0<t<k$均有$C_{k}^{t}=0$。那么由Lucas定理可得，$C_{k/2}^{t/2}C_{k\%2}^{t\%2}$ 为0，即$C_{k/2}^{t/2}=0$或$C_{k\%2}^{t\%2}=0$.

考虑$k$的奇偶性：

若$k$为偶数，则对于任意一个偶数$t$，$0<t/2<k/2$。又由对于所有$k\le 2^m$必要性成立且$2^{m-1}<k/2<2^m$，则必然存在$t/2$使得$C_{k/2}^{t/2}=1$，矛盾。

若$k$为奇数，则$C_{k/2}^{t/2}=C_{(k-1)/2}^{t/2}$，其中$k-1$是一个偶数。 若$k>2^m+1$，那么由之前$k$为偶数的讨论可以得出上式必不总为$0$，则产生矛盾；若$k=2^m+1$，由上证充分性可推出$k$不满足条件。

综上，对于$k\le 2^{m+1}$必要性，由归纳法得证。

那么，$k$是$2$的整数次幂且$4\le k$是杨辉三角的第$k$行为$1000\dots0001$的充要条件得证，也就是说本题的答案就是所有满足$k=2^t-2$的$2\le k\le n$，其中$k,t$是一个整数。

第一次写长篇数学证明，不足之处请多指教！