组合数学, 归纳法（数学归纳法）
数学归纳法是一种证明技术，用于确定一个陈述对所有自然数（或从某个整数开始的无限序列）都成立。它涉及基础情况和归纳步骤。问题需要为公式、属性或陈述构建归纳证明。
-
问题
在仙境里有 `n` 个城市，每两个城市之间都由一条公路连接。公路仅在城市相遇（城市外没有交叉路口）。一个邪恶的巫师想要把所有的公路都变成单行道，使得如果从任何一个城市出发，都不可能再回到该城市。
a. 证明邪恶的巫师可以做到这一点。
b. 证明存在一个城市，可以从该城市到达任何其他城市，并且存在一个城市，根本无法从该城市离开。
c. 证明存在一条穿过所有城市的路径，而且只有一条这样的路径。
-
问题
给定一个正整数N，考虑以下过程：记`S(N)`为N的各位数字之和，取`S(N)`的各位数字之和。重复此操作直到得到一个一位数。称执行上述过程直到得到一位数的次数为N的“深度”。例如，49的深度为`S(49)=13 -> S(13)=4)2`，执行了两次操作（49的深度为2），而45的深度为1。
a) 证明对于任何数N，其深度都是有限的，也就是说，在过程的某个阶段总会得到一个一位数。
b) 记`x(n)`为深度为N的最小数（值最小的数）。求`x(5776)`除以6的余数。请说明你的答案！
c) 求`x(5776) - x(5708)`除以2016的余数。请说明你的答案！
来源： -
问题
在平面上绘制了一些直线和圆。证明可以将平面划分成的区域涂成两种颜色，使得相邻区域（具有公共线段或弧线）涂成不同的颜色。
-
问题
给定一个实数 `a` 使得 `a+1/a` 是一个整数。证明对于所有自然数 `n`，`a^n+1/a^n` 也是整数。
-
问题
黑板上写着数字：`1, 2, 3, …, 2016, 2017`。每次操作可以选择黑板上的两个数字，将它们擦除，然后写上它们的（正）差。经过多次这样的操作后，黑板上只剩下一个数字。这可能为零吗？
-
26 枚硬币
已知有 `26` 枚外观相同的硬币。其中一枚是假币，重量比真币轻。如何用一个无砝码的天平，称三次找出这枚假币？
-
80 枚硬币
现有 `80` 枚外观相同的硬币。其中一枚是假币，重量比真币轻。如何使用无砝码的天平，通过四次称重找出这枚假币？
-
问题
证明以下等式：
`1+3+5+...+(2n-1)=n^2`
-
所有马都有相同的颜色吗？
Shlomi声称他已经通过归纳法证明，在每个马群中，所有的马都是相同的颜色：
如果只有一匹马，那么它的颜色就是它自己的颜色 - 因此我们证明了归纳基础成立。
为了进行归纳步骤，我们将马从`1`编号到`n`。根据归纳假设，编号从`1`到`n-1`的马，它们的颜色都相同。类似地，编号从`2`到`n`的马，它们的颜色也全部相同。并且由于从`2`到`n-1`的马的颜色是固定的，并且不能根据我们将它们分配到这个或那个组的方式而改变，那么马`1`和`n`也必须是相同的颜色。
Shlomi在他的证明过程中是否犯了错误？如果是这样，请找出错误。
-
问题
平面被 n 条直线和圆分割成若干区域，
证明所得的地图可以用两种颜色着色，使得任何两个相邻区域（由一段线段或弧分隔）都被涂成不同的颜色。
来源：