巧思题随记
巧思题随记
Mikasa收集一些平时遇到的小巧思题，不限于题目背景。
翻转杯子
题面
圆桌上放4个相同的杯子，初始时开口朝向未知。玩家蒙眼（无法分辨正反）同时翻转任意数量杯子：如果让所有杯子都朝向相同，那么游戏结束；否则圆桌旋转随机角度，然后继续上述过程。问：有无一种策略，能使得能在有限步内结束游戏？
题解
开口方向视为0/1，翻转视为异或，每次操作后的旋转圆桌视为对原01序列循环右移。
首先考虑操作的所有情况：
- 翻转一个杯子，由对称性，有一种情况
xor 0001 - 翻转两个杯子，由对称性，一共有两种不同的情况：
xor 0101和xor 0011 - 翻转三个杯子等价于翻转一个杯子
- 翻转四个杯子等价于不翻转
所以一共只有三种有效操作，分别是对原序列异或上: 0001 0101 0011
记序列1为 0001， 序列2为 0011，序列3为 0101。
然后考虑序列的所有情况：
同上，所有不重复的状态有 0001， 0011， 0101 和 0000
多记一个序列0为 0000
那么能得到下面的状态机表（由于xor的交换律，只算一半即可）：
| 操作 | |||
|---|---|---|---|
| 原状态 | xor 1 | xor 2 | xor 3 |
| 1 | 0/2/3 | 1 | 1 |
| 2 | —— | 0/3 | 2 |
| 3 | —— | —— | 0 |
依次进行操作 3231323 一定能变为序列 0，所以最多操作 7 次。
拉姆齐定理
题面
给一个有 6 个点的完全图（所有点两两之间都有一条边），给每条边随机染上红色或者蓝色，证明：至少会有一个同色三角形。
gcd问题
题面
已知一个正整数序列 $a_1,a_2,\dots a_n$，满足 $\gcd{(a)}\times \text{lcm}(a) = \prod_{i = 1}^{n} a_i$。问：这个序列有什么性质?
题解
序列 $a$ 要么满足 $n\leq 2$，要么所有元素两两互质。
埃尔德什–塞凯雷什定理
题面
证明：对于 $n\times m + 1$ 个互不相同实数组成的数列 ，一定存在长为 $n+1$ 的递增子列或长为 $m+1$ 的递减子列.
2/4形不定积分
题面
求: $\int{1+x^2\over 1+x^4}dx$
数列嵌套
题面
已知 $a_n \in \mathbb{N}^{+}, a_{a_n} = n$，求通项公式。
ex：如果 $a_{a_n} = kn (k\in \mathbb {N}^+)$?
end.
