algorithm - 袋子里的代币

Question

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

重复以下操作，直到袋子为空：

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

2）根据我们在步骤1）中得到的两个token，我们做以下事情：

∗ 案例 1：如果其中一个标记是红色的，什么也不做。

∗ 案例 2：如果两个代币都是绿色的，我们将 1 个绿色代币和 2 个蓝色代币放回袋子。

∗ 案例 3：如果我们得到一个蓝色令牌，而另一个令牌不是红色，那么我们将 3 个红色令牌放回袋子中。

假设我们总是有足够的令牌放回包中，通过归纳证明这个过程总是终止。

---

所以对于我的基本情况，我设置 n = 1 并且由于我们有少于 2 个令牌，我们只需清空袋子并终止过程。

我不知道从那里去哪里。

这是我在笔记本上写下的，只是想着这个问题：

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

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

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

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

如果我们取出BB，我们放回3个红色代币，现在袋子里有+1代币（因为我们取出了2个，又加了3个）

如果我们取出BG，同上

如果我们取出 GG，1 个绿色和 2 个蓝色又放回去，现在袋子里有 +1 代币

我想我可以从中看出，最终，袋子将装满或几乎装满红色代币，因为只有一种情况是我们放回不是红色的代币，而两种情况是我们放回 3 个红色代币。每当我们拿出一个红色令牌时，我们什么都不做，只是缩小袋子里的令牌大小，直到袋子空了。

绿色代币的数量将相对于蓝色和红色代币的数量减少。我们想拉一个红色或蓝色的令牌，而不是绿色。

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

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

标签： algorithmproofinduction

Answer 1

这是一个提示。而不是红色，蓝色和绿色认为便士，一角硬币和四分之一。继续归纳袋子里东西的价值。