【笔记】神仙思路之非构造性证明

· · 个人记录

今天集训讲课的时候讲到了这个……感觉很妙，拿出来分享一下。

非构造性证明即证明某个命题时，不举例而只是证明语句正确的方式，对于避开某些棘手的部分有着很好的效果。

例题 1：证明存在无理数的无理数次方为有理数。

证明：

考虑 \sqrt{2}^{\sqrt{2}}，若其为有理数，则命题得证；若其为无理数，则有 \left({\sqrt{2}^{\sqrt{2}}}\right)^{\sqrt{2}}=2 为有理数，命题得证。

例题 2：一个 n\times m 的网格，两个人轮流选择网格 (x,y)，选择 (x,y) 后所有满足 i\le x 且 j\le y 的格子 (i,j) 都不能被选择。当一个人不能继续选择时，此人获胜。问先手是否有必胜策略。

解：显然 n=m=1 时，先手必败。考虑当 n,m≥1 时的情况。

发现无论选取哪个格子，(1,1) 都不能再被选取了。于是发现选取 (1,1) 对答案没有影响。考虑若当前情况先手有必胜策略，则先手必胜；若当前局面为后手必胜，则先手可以选取 (1,1)，此时他变为了上一个局面的后手，因此他有必胜策略。由以上分析可知，在n,m≥1 时，先手必胜。

这样我们就证明了先手有必胜策略，但无需构造出先手的真正必胜策略。这就是非构造性证明的优点。

例题 3：两个人轮流写下 [1,2000] 内的整数，已经写下的数的因子不能再被写下。问先手是否有必胜策略。

证明：先手有必胜策略。

这道题的思路与例题 2 十分相似，考虑无论写下什么数， 1 永远不能再被写下。因此若当前局面为先手必胜，则先手显然有必胜策略；若当前局面后手必胜，则先手只需要写下 1 即可使他变为刚刚游戏里的后手，这样就证明了先手有必胜策略。