Задача о фамилии Тьюринга
Мы посвящаем следующую задачу Алану Тьюрингу (1912–1954) – английскому математику и криптографу, который, помимо других замечательных достижений, сыграл ведущую роль в развитии теоретической информатики.
Эта задача – четвёртый эпизод нашего сериала головоломок. После описания задачи идёт ответ на вчерашнюю головоломку об острове хамелеонов.
Задача о фамилии Тьюринга
Условие. Если мы сгенерируем список всех «слов», составленных из букв G, I, N, R, T и U в лексикографическом порядке, начиная с GINRTU и заканчивая UTRNIG, какую позицию в списке займёт TURING?
Альтернативный подход 🌟. Если вы не знаете, как подступиться к задаче аналитически, но можете решить программно, предложите в комментариях вариант решения общего случая с помощью кода. На входе – строка фамилии, на выходе – её номер в списке «слов», составленных из букв фамилии.
Идеи и ответы можно обсудить в комментариях. Первого человека, указавшего правильное решение, мы выделим при публикцаии следующей задачи.
Ответ и решение – в следующей задаче.
Решение задачи об острове хамелеонов
В комментариях на сайте Библиотеки программиста пользователь matuseho первым дал правильный ответ и описал разгадку. Нам остаётся только процитировать:
После каждого обмена между двумя хамелеонами, количество хамелеонов соответствующих цветов изменяется следующим образом: -1, -1, +2. То есть остатки при делении кол-ва хамелеонов на 3 меняются одинаково. Исходный набор {10, 14, 15} соответствует набору остатков {1, 2, 0}, а желаемый финальный набор {0, 0, 39} (в любом порядке) соответствует набору остатков {0, 0, 0}. Из набора разных остатков мы не можем получить набор одинаковых, так что вывод: нет, нельзя добиться единого цвета для всех.