注册
登录

匹配在组合数学中的应用

作者: 憂い桜

简介: 魔法猫咪

最后修改: 2025-06-19 18:10:55.601171

文章状态: 已发布

标签:

数学
你需要和一个 AI  进行多轮游戏，每轮游戏 的流程 如下 系统给定一个 n × m 的网格 4≤ n , m ≤ 10 ，你需要把 1 ∼ nm 中所有数字不重不漏地 填进去 . 你和 AI  轮流选数（ AI  先选） 要求：除了第一轮外，每 轮选出 的格子 必须和 之前选 出过的 至少一 个格子 有公共 边 .  最后游戏结束，你需要 保证自己选出的数之和比 AI  小。 首先我们 考虑 n × m 为奇 数 的情况， 可以 注意到如 果 AI   是先 手的话 ，我们一 定可 以让 AI   选择到 nm 这个数 ， 对于剩下的 nm − 1 个数，我们可以通过这种 配对 (1,2),(3 ,4), ⋯ ,( nm − 2, nm − 1) 使得每次当 AI  选择其中一个组的 其中一个时，我们立即选 择另一 个，这 样每次 回合博 弈结束 后我们 只会损 失 1 , 又因为 AI  一定会拿到 nm ,  我 们总数之和一定小于 AI 。 ( 如图 ) 我们 先考虑 4 × 4 的情况，两两配对的缺 点在于 先手才 是有优 势的一 方，然 而我们 并不是 先手， 所以我 们考 虑一种新的配对方式 : T 字形配对，如图。 通过 这样三个大数包围一 个小数 的配对 “陷阱” ， AI 在第一步一定会选择某个 T 格组，我们需要做的就 是在 这个格组选择我们的格子 ，经过 若干步 骤后， AI 一定会 先不能 在格组 内选择 （因为 格组内 格子数 量有限 而且 是偶数），那么 AI 一定会走 向另一 个 T 格组 , 并且我们可以注意到 ，每个 格组边 界一定 是大数 ，所以 AI 在走 向另一个格组的第一个格 子一定 是一个 大数， 随后我 们立即 选择格 组内唯 一的小 数。当 然我们 可以注 意到 在新的格组时，同样也是 AI 先进入 ，那么 我们依 然可以 按照上 面的策 略使得 AI 先手 出格组 ，然后 再次获 得小 数的优势！ 我们可以发现 T 形格组的目的是增加我们的 优势， 但是在 一些 n × m 中我们不能像在 4 × 4 中那样正好放 下 T 形格组。很自然的回想起 在奇数 情况中 的那样 ，我们 可以利 用一些 T 形格组 来获得像 nm 的优势，然后 利用经典的多米诺配对来 稳固我 们的优 势。比 如下面 的构造 浅谈匹配在博弈游戏中的应用 背景介绍 在组合博弈中匹配的思想 经常被 用到， 匹配在 组合博 弈中 的 动机 类 似于 “ 等 招 ” ，具 体来说 ， 通过一定广义上 的 “ 分组 ” ，使得对于对 方的操 作，可 以通过 跟分组 有关的 操作去抵消对方的行动！ 可以说 匹配的 动机其 实很简 单，但 是往往 在不同 的局面 或 情况下，我们需要构造不 同的分 组。这 也让匹 配这种 思想变 得很精 彩。当 然，分 组 本身这种思想也是组合数 学中的 重要 技巧 ! 喵呜 ~ ，当还没了解匹配思想 的学 生们 看到了 那些 复杂 的博 弈游 戏时， 一定 会说 ，“啊 ！， 怎么 才能抵 达胜 利啊 ！我 好伤 心！” 。啊哈 哈哈 ！， 最近 喵呜 酱在 经过一 些题 目的 训 练下，已经逐渐了解了一 些配对 的作 用， 现在 喵呜 酱就来 利用 一些 题目 分享 给大 家！ 波奇酱和凉酱需要玩一个游戏来决定凉还不还钱，现有 1, ⋯ ,2 n −1 ， 波奇酱和凉酱要依次选择一个数，凉酱让波奇酱先 选 。 波 奇酱赢得 比赛当且仅当波奇酱的任意回合 k 结束后 ,  所有前 k 次选择的数的 和是 n 的倍数。 我们可以注意到波奇酱的第一次选择只能是 n ,  随后我们进行分 组 ( 1,2 n − 1) ,(2,2 n − 2) ⋯ ,( k ,2 n − k ). 其中 k < n . 波奇酱在凉酱选了一个组 的另一个的时候，随后把这个组的另一个也选中即可。不难验证这 样可以保证波奇酱的每次选择都是满足题目的胜利条件的。 凉酱真是糊涂了啊！喵呜 ~ 考虑一个足够大的 n × m  的网格，其中有些格子是水，有些格子是陆地 . 高松灯因为唱的太 拼命了从而被传送到一个陆地格子上，爱音和立希轮流在陆地上移动高松灯 ( 不能移动到 之前移动的陆地，边相邻移动，不能移动到水里 ). 如果爱音先开始移动，无法继续操作的 人输掉高松灯，那么在什么样的陆地局面下 ,  爱音有必胜策略 。 有可能看到这里的学生们会觉得无从下手，呜呜呜。补药担心！喵呜酱来帮助你！ 结论： An on  必胜当且仅当任意最大匹配包含起点 证明：若任意最大匹配包含起点，说明起点在一个多米诺 L 内，那么 An on  先手必然可以 走到 L 的除了起点的另一个格点内。我们只需要证明每次立希走到的位置 x 一定是在一个 全新的多米诺 L ′ 。因为这样的话 An on  就可以走 L ′ 的另一个格点，重复此类操作，因为多 米诺有限，所以最后立希一定无处可走，即 An on  必胜。现在来证明立希走到的位置 x 一 定是在一个全新的多米诺。我们利用反证法 , 假设立希走到了一个空地 x ，即 x 不在一个多 米诺内，现在考察 An on  和立希走过的所有格点，那么一定存在一个从起点出发 ,  终点 为 x 的路径 l ，并且根据之前提到的 An on  的策略， l 中的除了 x 的其他格点都处在某个多 米诺内。我们设 l 路径中的多米诺的个数为 n , 那么存在一个新的多米诺配对使得整个路径 内的多米诺数量为 n 并且包含 x ,  不包含起点。这样的话我们构造出了一个最大匹配并且 不包含起点，矛盾。所以 B  走到的位置 x 一定是在一个全新的多米诺内。 喵呜酱 :  希望 An on  酱意识到这一点吧！ 喵呜注 :  最大匹配是指多米诺数量最大的匹配方法，多米诺是指两个相邻格子为一组 。 喵 ~ ，我们 已经 了 解 到如 何 利用 配 对和 分 组 的思 想 来构 造 必 胜局 面 ！， 现 在 来看 一 看配 对 思想 是 如 何在 组 合证 明 中 发挥 作 用的 吧 ！ 现在让我们来思考一个简 单的例 子 ~ 让我们再来 思考 一 个难 一 点的 例 子 ~ 可恶！ 展望和总结   在这一年 里面，有 幸接触了 很多的组 合问题， 组合数学 是一个非 常有意思 的数学分 支，每次 在苦思冥 想之后， 知道解法后都会恍然大悟，并且惊叹 于那种 巧妙的 方法。 很多组 合问题 并不要 求很多 前置知 识，往 往只需 要 一些灵感，我认为组合数学中的思想 或者技 巧是很 有助于 在其他 数学分 支进行 推广的 ，比如 说在构 造一般 情 况的时候，我们可以考虑一些简单的 情况， 然后在 简单情 况中构 造一个 满足的 结构， 然后通 过观察 这个结 构 的一些特点去推广到更普遍的情况。 还让我 感到很 有意思 的事情 是，很 多等势 的结构 都可以 找到组 合意义 上 的对应，有很多很巧妙的构造双射的 方法（   BIJE C TIVE  PR OO F  PR OB LE MS ，   Richar d  P .  St anle y  ） 学习数学带给我最大的快乐就是那个 经过自 己的思 考，然 后构造 出了某 个东西 ，然后 经过验 证，发 现一切 都 对了的时刻，我希望我可以保持热爱 。 Zhe nting  Liu Mento r   Ben   L iu 在此由衷感谢刘犇老师的指导以及指明 的 方向 , 感谢 S u n n y 同学提供的 Q3, 感谢父母一直的支持 " I w ou ld  lik e   t o e xp r e s s  m y  sin ce r e  gr a ti tude   t o  Ment or  L iu   Ben   f or  h is  in v alu ab le  guid ance  an d   d ir e ctio n .  My  than k s  also   g o  t o  Su n n y  f or p r ovi d i n g   Q - 3 ,  and   t o m y p ar e n ts  f or  the ir  u n w a v e rin g  su p p ort. "
创建一个文章