娱乐 一种存在性证明的思路和三道类似的“算法挑战”

[reflectK]

大家好，这里是reflectK。

 

我们首先看这样一道题目：

证明或证伪：无理数的无理数次方必为无理数。

显然（e，ln2）为一组反例，但是我们也有更巧妙的做法。

考虑（sqrt（2），sqrt（2）），如果它是有理数则题设立被证伪，否则考虑（（sqrt（2），sqrt（2）），sqrt（2）），它是无理数的无理数次方，而结果等于2。就这样我们在没有给出一组确定的具体实例的情况下解决了该问题。

 

这种思想可以帮助我们解决以下三道问题：

问题1：Alice和Bob在玩一个游戏，给出1到N是所有整数，每次取掉一个整数和它的所有因数，谁取最后一个谁获胜，Alice先取。问什么情况下Alice有必胜策略，什么情况下Bob有必胜策略。

问题2：有一块n*m的巧克力，其中（1，1）位置的巧克力是芥末味的，Cindy和David用这块巧克力比赛，每人轮流从一个可吃的块*开始，吃掉一个长方形区域，谁吃掉（1，1）这个区域，谁就失败了，Cindy先吃。问什么情况下双方有必胜策略。

*这里指，如果一个位置的巧克力右方和正上方都没有任何巧克力，那么称它为可吃的。

 

问题3：考虑一个简化版的国际象棋，没有吃过路兵/王车易位规则，双方马的位置用车代替，且黑方出兵只能走两步（否则不能移动这个兵），现在Eric执白先行对阵Frank。试证明Eric有必不败策略。

[reflectK]

刚刚，月晓说道:

甚至可以在sstm学数学

置顶就有算法挑战（）

[reflectK]

2 小时前，Dzero说道:

感觉都属于，动态规划可解

如果要找胜利方法确实是dp

不过这里只需要证明解的存在性 所以有更简单的方法

[reflectK]

3 小时前，浮游小黑兔说道:

dp？我怎么感觉是SG啊……这不是决策DAG上的多个子问题吗

问题1，有一个十分简单的解法：

首先当N=1时，显然先手胜

当N>=2时有：

由于1是任何数的因数，所以选取[2,N]的任何一个数，1都会被选走，那么提取 subproblem X：同原问题，在区间[2,N]上做博弈

对于 subproblem X 有两种结果：先手必胜，先手必败。

1. 若 X 为先手必胜，那么先手按照X的方法选取，博弈结果同原问题（[1,N]上的博弈），即先手必胜（因选取任何一个数a \in [2, N]，1必被选走）。

2. 若 X 为先手必败，那么对于原问题，先手第一步选1，此时问题规约为X，后手必败，即先手必胜。

综上，对于任意的N>=1，问题1存在先手必胜策略。

问题2（1，1）跟（n，m）位置没指明，即（1，1）是在左下还是左上？

问题3不清楚国际象棋具体规则，不做评论。

求获胜方案应该确实是dp吧（）

第一问的解法是正确的，在没有给出具体的方法下证明了必胜法的存在性。

按照正常坐标来，在左下。

在左上的解法过于显然了（）

第二题发现有点小问题，好像是只能从（n，m）开始吃起（）不过主楼的题目要找出规律倒也不难就是了（）

二月 1, 2023，由reflectK修改

[reflectK]

1 小时前，l1ll5说道:

1和2的思路本质上是一样的：用一个“无影响”的操作交换先后手从而实现先手必胜。

对于1来说这个无影响的操作是取1，对于2来说这个无影响的操作是取右上角的1*1块。

这两个操作都满足它包含于任何其他有效操作，所以可以用来交换先后手。

 

这两个问题比较关键或者说有趣的地方其实在于先手可以任意选择先后手，并且在博弈论中证明这两个游戏中存在先/后手必胜策略是平凡的。

从这个思路解决问题的话其实和引入的题目的解题思路没什么关系...

 

从这个角度考虑3的话也很容易有一个思路，就是通过一个兵连续走两次一步来替代一次走两步，从而实现交换先后手。但具体分析会复杂一些。没有马应该是为了限制第一步必须走兵。但我不会国象，所以摸了。

 

顺便... 感觉都不算算法题。

正确的ww

所以说打了引号嘛w

不过可能引入的还是不太好w 下次再加油（？）

[reflectK]

22 分钟前，浮游小黑兔说道:

 

为什么问题2 任意步能包含(n,m)点？题目不是从right-up corner开始选一个矩形吗？除了第一步，之后操作不一定包含(n,m)。

例如一个4*3的矩阵，用X表示没选的块，O表示选过的块

那么对于选了(n,m)状态为：

XXXO

XXXX

XXXX

后手可以选left-down(2, 2), right-up(3,3)的矩形，结果为：

XOOO

XOOX

XXXX

此时，后手操作不一定包含(4,3)点

先手如何选取(n,m)来交换先后手呢？

唔 所以才说之前出错了（）

18 小时前，reflectK说道:

第二题发现有点小问题，好像是只能从（n，m）开始吃起（）不过主楼的题目要找出规律倒也不难就是了（）

不过主楼的那个变种先手有比较显然的必胜策略（）

[reflectK]

1 小时前，浮游小黑兔说道:

 

为什么问题2 任意步能包含(n,m)点？题目不是从right-up corner开始选一个矩形吗？除了第一步，之后操作不一定包含(n,m)。

例如一个4*3的矩阵，用X表示没选的块，O表示选过的块

那么对于选了(n,m)状态为：

XXXO

XXXX

XXXX

后手可以选left-down(2, 2), right-up(3,3)的矩形，结果为：

XOOO

XOOX

XXXX

此时，后手操作不一定包含(4,3)点

先手如何选取(n,m)来交换先后手呢？

例如这样的情况 可以看成后面那种情况 先手吃（n,m）,后手吃（n，m）到（2,2）

而且与此同时先手还多了一个只吃（4,2）的选择 所以如果原来的游戏先手必胜，变种游戏也先手必胜。

 

大概是这样的吧，半夜脑子有点乱