组合学/激励示例和问题

一个 8x8 的城市网格，其中一条从 A 到 B 的路径突出显示。

1. 想象一下一个小型城镇中心，街道形成一个 8x8 的正方形网格，如示意图所示。从城镇中心的某个角落 (A) 到对角线上的另一个角落 (B) 有多少种旅行方式？

2. 在一个棋盘上，有多少种方式可以放置 8 个车，使它们彼此之间不攻击？

3. 一个讲座班至少需要多少名学生才能确保至少有两名学生生日相同的概率至少为 1/2？

4. 给定 n 个信件和 n 个已贴地址的信封，有多少种方式可以将信件放入信封中，使没有一个信件在正确的信封中？ (答案是最接近 ${\frac {n!}{e}}$ 的整数).

5. 柯克曼女学生问题：15 个女学生每天分成 5 个小组，每组 3 人。为女学生安排一周的步行路线，使在这段时间内，每对女学生只在小组中一起步行一次。^[1] (一个解决方案提供这里.)

6. 欧拉军官问题：给出 36 名军官，他们属于 6 个团，并担任 6 个军衔。(没有两个军官拥有相同的军衔和团，如果他们的军衔相同，那么他们的团就不同，反之亦然。)这些军官是否可以排列成一个 6x6 的阵列，使在阵列的任何一行中，每个团和每个军衔都恰好出现一次？(答案是不可以。)^[2]

7. 拉姆齐游戏：这个两人游戏需要在一张空白纸上画出 6 个点(其中没有 3 个点在同一条线上)，然后为玩家提供不同颜色的铅笔。玩家现在轮流通过画线连接点来连接点。第一个形成单色三角形的玩家输掉。问题是：这个游戏是否可以永远以平局结束？(答案是不可以。参见这里.)