Небольшое отступление
Прежде чем мы продолжим наши изыскания, небольшое отступление. В прошлый раз я упомянул о головоломках Реймонда Смаллиана о «рыцарях и лжецах». И хотя мне очень нравятся эти головоломки, самыми любимыми его головками являются шахматные задачи, вторыми идут задачи на комбинаторику. Вот пример второго типа задач (адаптированная задача со страницы 134 книги Satan, Cantor and Infinity).
У нас есть алфавит с буквами S, E, R, M, K и V, из которых можно составлять строки; «строка» является упорядоченной последовательностью символов из этого алфавита; последовательность может содержать любое конечное число символов. Говорят, что некоторые строки «определяют» (name) другие строки.
Я буду использовать «x» и «y» в качестве переменных для строк, и, более того, мы можем сказать, что x и y никогда не содержат пустых строк. (И, как будет говориться в четвертом правиле, y содержит как минимум два символа.) Правила именования следующие:
· SxE определяет x
· Если x определяет y, то Rx определяет yy
· Если x определяет y, то Mx определяет SyE
· Если x определяет y, то Kx определяет строку, созданную путем удаления самого левого символа из y
· Если x определяет y, тогда Vx определяет строку, созданную путем реверсирования символов y
Например, SRME определяет RM, по первому правилу. Поскольку SRME определяет RM, то исходя из второго правила, мы знаем, что RSRME определяет RMRM. И, таким образом, KRSRME определяет MRM.
Судя по комментариям, у некоторых читателей возникли вопросы; обратите внимание, что я не говорю о том, что некоторые строки являются «корректными», а некоторые – нет. Я говорю скорее о том, некоторые строки определяют другие строки. Строка, которая не определяет никакую другую строку остается совершенно «нормальной» строкой; ни одна из строк не является более или менее корректной, чем другая. Например, «RM» не определяет никакую другую строку.
Задача состоит в том (и она едва ли будет слишком сложной для программистов, но довольно хитрой для непрограммистов, которые не прочитали пятнадцать более простых задач перед этим), это найти строку, которая будет определять саму себя. Решение Смаллиана состоит из 18 символов, и он призывает читателя найти более короткое решение. Я нашел решение из 12 символов, и я предполагаю, что 12 символов – это наименьшее решение, но доказать это я не могу. Я дам свое решение, а также решение Смаллиана в комментариях. Удачи!
UPDATE: Существует минимальное решение из девяти символов. Отличная работа!