Marvin Minsky在我的口语考试中问了我以下问题:
当蚂蚁走路时,它每走一步就会打印一个二进制数(例如,101)。二进制数的最小长度是多少,以数字为单位,可以在不查看字符串的开头或结尾的情况下判断蚂蚁的行进方向?蚂蚁告诉你二进制数。
示例:蚂蚁的二进制数是 101,因此蚂蚁留下的轨迹如下所示:101101101101101101101。请注意,无法判断蚂蚁的行进方向。因此,这个特定的数字不起作用(但可能有一个三位数的二进制数)。
示例:蚂蚁的二进制数是 011,因此蚂蚁留下的轨迹如下所示:011011011011011011。同样,如果不查看字符串的末端,就无法判断蚂蚁的行进方向。
这个问题的答案是什么?请注意,答案不能只是一个有效的二进制数示例。答案需要包含一个证明,证明长度小于 n-1 的二进制数不会起作用,其中 n 是起作用的示例二进制数的长度。详尽列举的证明是可以的,但令人不快。:)