bitstring Shortest có sự lặp lại vô hạn là khác nhau sau khi đảo ngược

Question

Marvin Minsky hỏi tôi những câu dưới đây trong thi vấn đáp của tôi:

Như một con kiến ​​đi nó in một số nhị phân (ví dụ, 101) mỗi khi phải mất một bước. Độ dài tối thiểu, bằng chữ số, số nhị phân có thể là gì để có thể biết được hướng mà con kiến ​​đang di chuyển mà không nhìn vào đầu hoặc cuối của chuỗi? Con kiến ​​cho bạn biết số nhị phân.

Ví dụ: Số nhị phân của kiến ​​là 101 và, do đó, kiến ​​để lại một đường nhỏ như sau: 101101101101101101101. Lưu ý rằng không có cách nào để biết con kiến ​​đang di chuyển. Do đó, con số cụ thể này không hoạt động (nhưng có thể có một số nhị phân gồm 3 chữ số).

Ví dụ: Số nhị phân của kiến ​​là 011 và, do đó, kiến ​​để lại một đường nhỏ trông giống như sau: 011011011011011011. Một lần nữa, không có cách nào để cho biết con kiến ​​đang di chuyển mà không nhìn vào đầu của chuỗi .

Câu trả lời cho câu hỏi này là gì? Lưu ý rằng câu trả lời không thể chỉ là một ví dụ về một số nhị phân hoạt động. Câu trả lời cần bao gồm một bằng chứng rằng không có số nhị phân nào có độ dài nhỏ hơn n-1 sẽ làm việc trong đó n là độ dài của số nhị phân ví dụ hoạt động. Một bằng chứng bằng cách liệt kê đầy đủ là ok, nhưng khó chịu. :)

Answer 1

cách tiếp cận khác sẽ được khởi hành từ số nhị phân. Đặt lại câu hỏi là "Mẫu có thể ngắn nhất là hướng nào nếu được phép sử dụng bất kỳ số lượng ký hiệu duy nhất nào?"

Câu trả lời ở đây là 3 (ví dụ A; B; C hoặC#; &; @) vì 2 không hoạt động. Vì vậy, khi bạn có một mô hình như ABC là trở nên rõ ràng trong đó hướng kiến ​​là đi bộ.

Hoặc ... CABCABCABCABCAB ... (từ trái sang phải) Hoặc ... CBACBACBACBACBA ... (từ phải sang trái)

Bây giờ, có bao nhiêu chữ số nhị phân sao chúng ta cần phải viết một mô hình 3 biểu tượng trong Ternary (base-3)?

Hai chữ số nhị phân cho phép bạn viết một Đệ tứ duy nhất (base-4) chữ số, đó là cơ sở đầu tiên cao hơn hoặc bằng 3.

Do đó: (2 chữ số mỗi ký hiệu) nhân với (3 ký hiệu) = 6 Chữ số nhị phân.

Answer 2

ChssPly76 có câu trả lời đúng (IMHO) trong các nhận xét ở trên.

6 chữ số, ví dụ 100110.