super ez problem series 1

· · 学习·文化课

我没有这些题的标准答案，如果你找到了我的做法中的错谬，请及时指点！

感谢反物质维度群群主提供了这些有趣的题，目前计划是一个 series 发五个题。

一

无限大的棋盘上，把 n^2 个棋子摆成 n \times n 的方阵，玩法如下：每个棋子可以跳过紧邻（横/竖）的棋子，且落地的位置没有子，则可以吃掉被跳过的棋子（即类似跳棋），问哪些 n 可以让棋盘上仅剩下一个子。

::::info[solution]

接下来构造 $3 \nmid n$ 的情况，$n=1,n=2$ 的情形容易，下证我们可以把 $n$ 规约到 $n-3$ 的情形。 先做一个 case，若 $(x,y),(x,y+1),(x,y+2),(x+1,y)$ 上都有棋子，$(x-1,y)$ 上无棋子，则我们令 $(x,y),(x,y+1),(x,y+2),(x+1,y)$ 上面的棋子分别为 ABCD，D 往上跳 C 往左跳 D 往下跳就能在不移动 $(x+1,y)$ 的情况下把 $(x,y),(x,y+1),(x,y+2)$ 干掉，下称 $(x+1,y)$ 为跳板。 我们先把上述策略转置，前三行删一下最后几列直到前三行个数都是三的倍数，再用第二行作跳板把第一行干掉，用第三行作跳板把第二行干掉，用第四行作跳板把第三行干掉，用相仿的办法把前三列也干掉，就只剩下了一个 $(n-3) \times (n-3)$ 的矩形。 :::: ### 二 佩勒有 $100$ 个垃圾堆，每堆垃圾有 $100$ 个垃圾。每天早上，佩勒执行两个操作之一： 1. 在每堆垃圾中清除 $1$ 个垃圾 2. 清空某个垃圾堆 但是，每天晚上，邪恶的垃圾天神潜入佩勒的房子，执行两个操作中的任意一个： 1. 在每个非空的垃圾堆里扔一块垃圾 2. 在空地上扔一块垃圾，形成一个新的垃圾堆 佩勒为了保证清除所有垃圾，至少需要多少天？ ::::info[战败声明 & 答案] 我被这个题击败了，答案应该是 199，这个题就留作练习了！ :::: ### 三 $p$ 是一个奇质数，在 $1$ 到 $2p$ 这 $2p$ 个数的集合中，能选出多少个 $p$ 元素子集，其元素之和能被 $p$ 整除。 ::::info[solution] 取 $\omega=e^{2\pi i/p}$，对问题施单位根反演有答案为 $N=\frac1p\sum_{j=0}^{p-1}[x^p]\prod_{a=1}^{2p}(1+x\omega^{ja})$， 在 $1,2,\dots,2p$ 中，模 $p$ 的每个剩余类都恰好出现两次。因此，当 $j\neq 0$ 时，$\prod_{a=1}^{2p}(1+x\omega^{ja})=\left(\prod_{r=0}^{p-1}(1+x\omega^r)\right)^2$，又因为 $p$ 为奇质数，有 $\prod_{r=0}^{p-1}(1+x\omega^r)=1+x^p$，因此 $[x^p]\prod_{a=1}^{2p}(1+x\omega^{ja})=[x^p](1+x^p)^2$。$j=0$ 的情况平凡，整理后可得答案为 $\frac1p\left(\binom{2p}{p}+2(p-1)\right)$。 :::: ### 四 有序正整数 $(a,b,c)$ 满足 $a,b,c \leq 3^6$，且 $a^3+b^3+c^3$ 为 $3^7$ 的倍数，求满足条件的有序组数数。 ::::info[solution] 考察 $i^3 \bmod 9$ 只能是 $0,1,-1$，则三个数要么都 $\bmod 3=0$，要么恰有两个 $\bmod 3\neq 0$。 考虑一个很变态的结论：对于 $k\geq 2 i=1 \sim 3^{k-1}$ 中 $\bmod 3 \neq 0$ 的 $i$，$i^3\bmod k$ 恰好各取一次所有满足 $r \equiv \pm 1 \pmod 9$ 的剩余类。 1. 恰有两个 $\bmod 3 \neq 0$：不妨钦定 $c\bmod 3=0$，再选一个 $\bmod 3\neq 0$ 的 $b$，$a$ 被唯一确定，$3\times 243\times 486=354294

  1. 三个数都 \bmod 9=0：令 (u,v,w)=(a,b,c)/9，有 u,v,w\leq 81，有 u^3+v^3+w^3 \equiv u+v+w \equiv 0\pmod 3，(u+v+w) \bmod 3 分布均匀，81^3/3=177147

  2. 三个数都 \bmod 3=0 但不都 \bmod 9=0：令 (x,y,z)=(a,b,c)/3，则 x^3+y^3+z^3\equiv 0\pmod {81}，此时 x,y,z 恰有两个不被 3 整除，转化为类似于第一类的情形，不妨钦定 z\bmod 3=0，确定了 y,z 以后 1\leq x\leq 243 在 \bmod 27 剩余类中各出现 9 次，这种的方案数是 3\times 81\times 162\times 9=354294。

加起来是 885735。

五

在一个正八面体上分别写上 1\sim 8 这八个数，任意两个相邻的面上数字都不连续的概率是多大？（8 和 1 视为连续）

::::info[solution] 正八面体对偶多面体是立方体，问题转化为立方体的点染色，要求边两端的点颜色不相邻，这等价于 1-2-3-4-5-6-7-8-1 是立方体补图的一个子图。

立方体补图是两个 K4 对位连边，不难用经过对位边的量分类计数得到它的哈密顿环个数为 30，将哈密顿环染色有 8\times 2=16 种方案，因此总合法染色方案数为 30\times 16=480，原题答案为 \frac{480}{8!}=\frac{1}{84}。