10

Marvin Minsky在我的口语考试中问了我以下问题：

当蚂蚁走路时，它每走一步就会打印一个二进制数（例如，101）。二进制数的最小长度是多少，以数字为单位，可以在不查看字符串的开头或结尾的情况下判断蚂蚁的行进方向？蚂蚁告诉你二进制数。

示例：蚂蚁的二进制数是 101，因此蚂蚁留下的轨迹如下所示：101101101101101101101。请注意，无法判断蚂蚁的行进方向。因此，这个特定的数字不起作用（但可能有一个三位数的二进制数）。

示例：蚂蚁的二进制数是 011，因此蚂蚁留下的轨迹如下所示：011011011011011011。同样，如果不查看字符串的末端，就无法判断蚂蚁的行进方向。

这个问题的答案是什么？请注意，答案不能只是一个有效的二进制数示例。答案需要包含一个证明，证明长度小于 n-1 的二进制数不会起作用，其中 n 是起作用的示例二进制数的长度。详尽列举的证明是可以的，但令人不快。:)

4

2 回答 2

6

另一种方法是从二进制数出发。将问题改写为“如果允许使用任意数量的唯一符号，那么具有方向性的最短模式是什么？”

这里的答案是 3（例如 A;B;C 或 #;&;@），因为 2 不起作用。所以当你有一个像 ABC 这样的模式时，蚂蚁在哪个方向行走就变得很清楚了。

要么 ...CABCABCABCABCAB...（从左到右）或 ...CABCBACBACBACBA...（从右到左）

现在，我们需要多少个二进制数字才能用三进制（base-3）编写一个由 3 个符号组成的模式？

两个二进制数字允许您编写一个四进制（以 4 为基数）数字，即大于或等于 3 的第一个基数。

因此：（每个符号 2 个数字）乘以（3 个符号）= 6 个二进制数字。

于 2009-07-22T14:56:59.730 回答
2

ChssPly76 在上面的评论中有正确的答案（恕我直言）。

6 位数字，例如 100110。

于 2009-07-21T18:58:29.753 回答