反转后无限重复不同的最短比特串
Marvin Minsky 在口试期间问了我以下问题：
当蚂蚁行走时，它每走一步都会打印一个二进制数（例如，101）。 二进制数的最小长度是多少，可以在不查看字符串开头或结尾的情况下判断蚂蚁正在行进的方向？ 蚂蚁告诉你二进制数。
示例：蚂蚁的二进制数是 101，因此，蚂蚁留下的痕迹如下所示：101101101101101101101。请注意，无法判断蚂蚁的行进方向。 因此，这个特定的数字不起作用（但可能有一个三位二进制数起作用）。
示例：蚂蚁的二进制数是 011，因此，蚂蚁留下的痕迹如下所示：011011011011011011。同样，如果不查看字符串的末端，就无法判断蚂蚁的行进方向。
这个问题的答案是什么？ 请注意，答案不能只是有效的二进制数的示例。 答案需要包含一个证明，证明长度小于 n-1 的二进制数不会起作用，其中 n 是起作用的示例二进制数的长度。 通过穷举枚举的证明是可以的，但令人不愉快。 :)
Marvin Minsky asked me the following question during my oral exam:
As an ant walks it prints a binary number (e.g., 101) every time it takes a step. What is the minimum length, in digits, the binary number can be for it to be possible to tell which direction the ant is traveling without looking at the beginning or end of the string? The ant tells you the binary number.
Example: The ant's binary number is 101 and, hence, the ant leaves a trail that looks like this: 101101101101101101101. Note that there is no way to tell which way the ant is traveling. Hence, this particular number does not work (but there may be a three digit binary number that does).
Example: The ant's binary number is 011 and, hence, the ant leaves a trail that looks like this: 011011011011011011. Again, there is no way to tell which way the ant is traveling without looking at the ends of the string.
What is the answer to this question? Note that the answer cannot just be an example of a binary number that works. The answer needs to include a proof that no binary number of length less than n-1 will work where n is the length of the example binary number that works. A proof by exhaustive enumeration is ok, but unpleasant. :)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
另一种方法是脱离二进制数。 将问题改写为“如果允许使用任意数量的唯一符号，那么有方向性的最短可能模式是什么？”
这里的答案是 3（例如 A;B;C 或 #;&@），因为 2 不起作用。 因此，当你有了像 ABC 这样的模式时，蚂蚁行走的方向就变得很清楚了。
...CABCABCABCABCAB...（从左到右）
或者...CBACBACBACBACBA...（从右到左）
现在，我们需要多少个二进制数字才能用三进制（基数为3）编写3个符号的模式？
两个二进制数字允许您写入一个四进制（以 4 为基数）数字，即第一个大于或等于 3 的基数。
因此：（每个符号 2 位数字）乘以（3 个符号）= 6 个二进制数字。
Another approach would be to depart from binary numbers. Rephrase the question as "What is the shortest possible pattern which is directional if one is allowed to use any number of unique symbols?"
The answer here is 3 (for example A;B;C or #;&;@) since 2 does not work. So when you have a pattern like ABC is becomes clear in which direction the ant is walking.
Either ...CABCABCABCABCAB... (from left to right)
Or ...CBACBACBACBACBA... (from right to left)
Now, how many Binary digits do we need to write a pattern of 3 symbols in Ternary (base-3)?
Two Binary digits allow you to write a single Quaternary (base-4) digit, which is the first base higher than or equal to 3.
Thus: (2 digits-per-symbol) multiplied by (3 symbols) = 6 Binary digits.
ChssPly76 在上面的评论中有正确的答案（恕我直言）。
6 位数字，例如 100110。
ChssPly76 has the correct answer (IMHO) in the comments above.
6 digits, example 100110.