"pick the number up game"的算法

Question

我正在努力寻找解决方案，但我对此一无所知。

RobotA 和 RobotB 选择 N 个数字的排列作为开始。 RobotA先挑，他们交替挑。每一轮，机器人只能从排列中选择任何一个剩余的数字。当剩余数字形成递增序列时，游戏结束。选择最后一个回合的机器人(之后顺序增加)赢得比赛。

假设双方都发挥最佳，谁赢了？

示例 1:

 The original sequence is 1 7 3. 
 RobotA wins by picking 7, after which the sequence is increasing 1 3.

示例 2:

 The original sequence is 8 5 3 1 2.
 RobotB wins by selecting the 2, preventing any increasing sequence.

有没有已知的算法可以解决这个问题？请给我任何关于在哪里查看的提示或想法，将不胜感激!

Answer 1

给定一个不同数字的序列w，令N(w) 为w 的长度并令L(w ) 是w 中最长递增子序列的长度。例如，如果

w = 3 5 8 1 4

然后 N(w) = 5 和 L(w) = 3。

游戏在 L(w) = N(w) 时结束，或者等价地，N(w) - L(w) = 0。

逆向进行游戏，如果轮到 RobotX N(w) - L(w) = 1，那么最佳玩法是移除不在最长递增子序列中的唯一字母，从而获胜游戏。

例如，如果 w = 1 7 3，则 N(w) = 3 和 L(w) = 2最长的递增子序列是 1 3。移除 7 会导致顺序递增，确保移除 7 的玩家获胜。

回到前面的例子，w = 3 5 8 1 4，如果 1 或 4 被移除，那么对于生成的排列 u 我们有 N(u) - L(u) = 1，所以移除 1 或 4 的玩家 肯定会输给有能力的对手。然而，任何其他游戏都会导致胜利，因为它会迫使下一位玩家移动到失败的位置。在这里，最佳玩法是删除 3、5 或 8 中的任何一个，之后 N(u) - L( u) = 2，但在下一步之后 N(v) - L(v) = 1。

沿着这些思路进行进一步分析应该会为任何一方得出最佳策略。

---

我所知道的最接近的数学游戏是单调序列游戏。在单调序列游戏中，两个玩家交替地从某个固定的有序集合(例如 1,2,...,N)中选择序列的元素。当结果序列包含长度为 A 的升序子序列或长度为 D 的降序子序列时，游戏结束。这个游戏起源于 Erdos 和 Szekeres 的定理，可以在 MONOTONIC SEQUENCE GAMES 中找到一个很好的说明。 ，还有这个 slide presentation Bruce Sagan 的著作也是一个很好的引用。

如果您想了解更多关于一般博弈论的知识，或者特别是这类博弈，那么我强烈推荐 Berlekamp、Conway 和 Guy 的《Winning Ways for Your Mathematical Plays》。我相信，第 3 卷解决了这类游戏。