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 回答