algorithm - 袋子里的代币

Question

我们有 n 个标记。每个 token 都是红色、蓝色或绿色。这n个 token 在一个袋子里

重复以下操作直到袋子变空:

1) 如果包里有两个以上的 token 。从包中取出两个随机 token 。否则，清空袋子。

2)根据我们在步骤1)得到的两个token，我们做了以下事情:

* 情况 1:如果其中一个标记为红色，则什么都不做。

* 情况 2:如果两个 token 都是绿色的，我们放回一个绿色 token 和 2 个蓝色 token 放进袋子里。

* 情况 3:如果我们得到一个蓝色标记，而另一个标记不是红色，那么我们将 3红色代币放回袋中。

假设我们总是有足够的 token 放回袋子，通过归纳法证明这个过程总是终止。

---

因此，对于我的基本情况，我将 n = 1，因为我们的 token 少于 2 个，所以我们只需清空袋子，过程就终止了。

我不知道从那里去哪里。

这是我在思考问题时在笔记本上写下的:

R = 红色，B = 蓝色，G = 绿色

如果我们取出 RR，我们什么都不做，袋子现在包含 n=n-2 个 token

如果我们取出 RB，我们什么都不做，袋子现在包含 n=n-2 个 token

如果我们取出 RG，我们什么都不做，袋子现在包含 n=n-2 个 token

如果我们取出 BB，我们放回 3 个红色标记，现在包中包含 +1 个标记(因为我们取出 2 个并放回 3 个)

如果我们取出BG，和上面一样做

如果我们取出 GG，1 个绿色和 2 个蓝色会返回，现在包中包含 +1 个 token

我想我可以从中看到的是，最终袋子会装满或几乎装满红色标记，因为只有一种情况我们放回非红色标记，两种情况放回 3红色标记。每当我们取出一个红色 token 时，我们什么都不做，只是缩小袋子中的 token 大小，直到袋子变空。

相对于蓝色和红色代币的数量，绿色代币的数量会减少。我们想要提取红色或蓝色 token ，而不是绿色。

我不确定如何通过归纳来证明这一点。任何帮助将不胜感激

编辑:谢谢，我想我现在明白了

Answer 1

这是一个提示。而不是红色、蓝色和绿色，想想便士、角钱和 25 美分硬币。对包中元素的值(value)进行归纳。