组合数学, 不变量
不变量是系统或数学对象在应用变换或操作时保持不变的属性。识别不变量是解决关于过程或证明不可能性的问题的关键。问题涉及寻找此类常量或属性。
-
问题
圆周上给定一些蓝色和红色的点。允许添加一个红点并改变其相邻点的颜色，或者移除一个红点并改变其先前相邻点的颜色（不允许在圆周上留下少于 2 个点）。证明仅通过这些操作不可能将具有两个红点的圆周转换为具有两个蓝点的圆周。
来源：
K. Kazarnovski -
狼和羊
游戏在一个无限平面上进行。一个玩家移动狼，另一个玩家移动 50 只羊。狼走一步后，一只羊走一步，然后狼再走，以此类推。一步中，狼或羊最多只能向任何方向移动一米。在任何初始状态下，狼都能抓住至少一只羊吗？
来源： -
骑士与龙
一位骑士在路上遇到一条有三个头的龙，他们开始了一场战斗。每当骑士砍掉龙的一个头，就会长出三个新头来。龙有可能最终变成一千个头吗？
-
阿里巴巴和四十大盗
阿里巴巴在一张纸上写下了数字`17`。 四十大盗将纸张互相传递，每个人要么给现有数字加上`1`，要么减去`1`，直到每个人都执行了一次，然后将纸张还给阿里巴巴。
纸上现在是否有可能写着数字`40`？
来源： -
与巧克力玩游戏
约西和丹尼玩以下游戏。他们有一块 `5xx7` 格的巧克力，放在桌子上。 每个人轮流沿着直线打破桌子上的一块巧克力，然后将产生的碎片放回桌子上。 也就是说，第一轮打破原始巧克力，在接下来的回合中，从那时起产生的碎片中选择一个并打破它。 只能沿着格子线打破，并且每次断裂都是从一边到另一边。 无法移动的人输。 赢家吃掉所有的巧克力。
如果约西先走，他们中的哪一个能保证自己获胜？
-
石头堆游戏
两个人玩以下游戏。桌子上有三堆石头。第一堆有 `10` 块石头，第二堆有 – `15` 块，第三堆有 – `20` 块。每个人轮流选择当前桌上的一堆石头，并将其分成两堆较小的石头。无法移动者输。
哪个玩家有制胜策略，是什么？
来源： -
问题
一个国际象棋的马从 `a1` 格出发，经过若干步后回到了同一格。
马有可能走了奇数步吗？
-
问题
一个骑士从 `a1` 格出发，到达 `h8` 格。是否可能它在途中恰好访问了棋盘上的每个格子一次？
-
问题
游戏在一个无限的平面上进行。一个玩家移动狼，另一个玩家移动 K 只羊。狼走一步后，一只羊走一步，然后狼再走，以此类推。每一步，狼或羊最多只能向任何方向移动一米。在任何初始状态下，狼是否总能抓住至少一只羊？
来源： -
问题
在一个无限的方格纸上标记了 6 个方格，如图所示。一些方格上有石头。一次操作中，如果一个石头上方和右侧都没有相邻的石头，则可以移除该石头，并在其上方和右侧的位置放置 2 个石头。如果在初始状态下石头位于以下位置，我们是否可以通过此操作移除所有标记位置的石头：
A. (8 分) 在所有标记的方格中。
B. (8 分) 仅在最底部和最左侧标记的方格中。O
O O
O O OM. Kontsevich'
来源：