不可能搜索算法面试问题

Question

你将如何解决这个问题？

您可以从一个盒子开始，其中包含x个红色弹珠，y个绿色弹珠和z个蓝色弹珠，以及盒子外无限供应的红色、绿色和蓝色弹珠。其中一步是选择两种不同的颜色，从盒子里拿出两个弹珠(你选择的两种颜色中的每一个)，然后从你的供应中添加第三种颜色的弹珠到盒子里。例如，如果选择红色和绿色，则移除一个红色和一个绿色大理石，然后放回一个蓝色大理石。对于什么起始条件(表示为对x，y，z的约束)，您可以通过执行零个或多个移动来获得盒子中的一个大理石？

Answer 1

如果满足以下条件，它将收敛为1：

1)在三个(x，y，z)中，只有两个是偶数或奇数。也就是说，这三个不能都是偶数或奇数，其中一个必须不同。

它们中的任何一个都可以是偶数或奇数，对颜色没有限制。

编辑：正如@onelyner最初指出的那样，(3，0，0)不会工作，尽管遵循了第一个规则。概括地说，

2)如果第三个不等于1，则(x，y，z)中的任何两个最初都不能为零。

即它不能看起来像(0，0，n)，其中n不等于1。

这里要注意的是，我们可以从(2，1，1)到达(3，0，0)，它应该收敛到1，因为它遵循这两个规则。如果处理得当，它肯定会收敛到一个

(2，1，1) -> (1，2，0) -> (0，1，1) -> (1，0，0)

Answer 2

为了解释revealed的奇偶校验问题，我们可以将状态视为总和分为三个部分的分区。在每个阶段，总和减1 (-2 + 1)，这意味着总和的奇偶校验翻转。对于奇数，有两种方法将其表示为三(奇数+奇数+奇数)或(偶数+偶数+奇数)的和，而对于偶数，也有两种方法，(奇数+奇数+偶数)或(偶数+偶数+偶数)。

我们还知道，在每一步，所有三个部分都会翻转奇偶校验，因为其中两个是递减的，一个是递增的。所以我们要么在(奇数，奇数，奇数)和(偶数，偶数，偶数)之间移动，要么在(奇数，奇数，偶数)和(偶数，偶数，奇数)之间移动。因为我们知道最终状态是(even，even，odd)，所以我们知道状态变化必须介于(odd，odd，even)和(even，even，odd)之间。

但这是否足以知道任何起始值(明显的{x, 0, 0}, x > 1除外)都会起作用？

Answer 3

向后工作...

从{0,0,1}开始，我们可以通过重复选择要递减的1来获得任意k >= 0的{0,1，k}。

从{0,1，k}，k>=1，我们可以通过在k和1之间交替递减来得到{2x,1，k)。

从{ 2x ,1，k}，k>=1，我们可以通过在2x和k之间交替递减来得到{2x,2y+1，k)。

因此，任何至少有一个偶数、至少一个奇数和至少两个大于零的三重奏都可以从反面的单个大理石中到达。