杂题选做

2024.12.?

你有 的格子和 个挡板。合理设置挡板使得从方格左上角走到右下角的最短路径最长（走路时不可以穿过挡板）。

2025.3.31

从去年省集 slides 里找到的题

一个 的有序划分定义为有序数组 使得 。

求 的含偶数个偶数的划分的数量。

sol

这个有点太牛了。

考虑求含奇数个偶数的划分的数量。

发现好像是等难的。

所以直接由对称性猜他们相等

尝试构造 无不动点对合

定义一个操作 为，对于任意一个划分，若第一项为 ，则把第一项和第二项合并起来，否则把第一项拆成 和第一项减

发现 ，我们称这样的映射为 对合

同时发现，我们刚刚构造的 是没有不动点的。

因此 相当于把原状态空间中的点两两配对，并且配对中的两个点恰好含偶数的个数的奇偶性不同。

显然有含偶数个偶数的划分和含奇数个偶数的划分的数量相同。

2025.4.1

求

sol

组合意义天地灭，代数推导保平安。

sly 给出了一个代数做法，挺可爱的。

但是这个的组合意义证明真的非常牛！

首先注意到这个 不太好找组合意义，不妨给她乘上 ，变为 ，最后除掉即可。

2025.4.3

给出 的组合意义证明。

sol

考虑原式等于

发现原问题等价于证明 中大小为奇数和大小为偶数的子集数量相等。

trivial

这个也可以构造无不动点对合。

考虑每个集合 ，定义映射 为：若 ，则把 去掉，否则把 加入进去。

容易发现这个也是无不动点对合。

可爱捏。

upd 2025.5.15

bonus: 有集合 ，求

组合证法焕发魅力。

先前我希望找到 的组合意义证法的时候，大家都骂我唐。

那个这好像只能组合证明了。

证明过程几乎是完全一样的，因为加入 也会恰好改变和的奇偶性。

2025.4.?

构造。

点数为 的完全图，求最多有多少个边不相交的生成树。

去年的我为啥不会这个？

为什么 xhr 都能场切的题我都不会？？？

先考虑解出一个上界。

发现答案

因为每棵生成树要消耗 条边，总的边数为

考虑归纳， 时的情况是显然的。那么仅需证明每次加入两个元素后能够增加一棵生成树。

首先，增加两个点 后增加的边为原先所有点到 的边以及原先

2024.4.13

不等式。

已知 且

2025.4.14

已知 且

证明有无限个 使得

2025.4.16

可爱奶龙。

的网格上放有箭头。

只能沿着当前网格上放置的箭头移动。

每次移动后，所有的箭头将会顺时针转动 。

定义一个格子是好的，当且仅当从她出发后能够经过所有点恰好一次，并且回到这个格子。

求怎样使好的格子最多？

2025.4.18

构造 (?)

证明大小为 的集合的所有子集一定可以排成一行，使得任意相邻的两项大小相差 。

感觉像 “所有子集”，“完全图”，“链” 这样的组合结构特别适合归纳。因为新加入的元素的贡献是容易统计的(?)

2025.5.?

你有 这些数。

找出 个三元组，使得每个数恰好出现在一个三元组中。