Процессы и алгоритмы

Пусть в алфавите жителей Банановой Республики букв. Занумеруем их по порядку. Выпишем на доску слово, содержащее первую букву. Затем выпишем на доску слово, содержащее вторую букву. Затем — третью, и т. д. до тех пор, пока не выпишем на доску слово, содержащее -ю букву. Таким образом мы выпишем на доску слов, в записи которых используется ровно различных букв. Сотрем с доски повторяющиеся слова (т. е. если какое-то слово написано раз, то сотрем такое слово). Вместо стертых слов выпишем на доску новые так, чтобы на доске оказалось написано ровно различных слов. Это можно сделать, поскольку слов больше При этом мы не используем новых букв, так как букв всего и каждая из них где-то записана на доске. В записи этих слов используется ровно различных букв, что и требовалось.

Узники выбирают одного определённого человека (будем называть его “счётчиком”), который будет считать узников по такой системе: если, приходя в комнату, он обнаруживает, что свет включён, то он прибавляет к уже посчитанному числу узников единицу и выключает свет, если же свет не горит, то он, ничего не меняя, возвращается обратно в свою камеру. Каждый из оставшихся узников действует по такому правилу: если, приходя в комнату, он обнаруживает, что свет не горит и он до этого ни разу не включал свет, то он его включает. В остальных случаях он ничего не меняет.

Когда число посчитанных узников становится равным “счётчик” говорит, что все узники уже побывали в комнате.

Действительно, каждый узник, кроме “счётчика”, включит свет в комнате не более одного раза. Когда “счётчик” насчитает он может быть уверен, что все остальные узники уже побывали в комнате хотя бы раз, кроме того он сам уже побывал в комнате. Получается, что к этому моменту все узники заведомо побывали в комнате хоть раз.

Остаётся доказать, что каждый из узников включит свет. Предположим, что это не так — свет будет включён менее раз. Тогда, начиная с некоторого дня свет включаться не будет. Так как никакой заход в комнату не будет для счётчика последним, он побывает в комнате после этого дня (например, на -й день, Если свет при этом горел, он его выключит. Значит, начнная с ()-го дня свет будет всё время выключен. Рассмотрим узника, который свет ещё ни разу не зажигал. Так как и для него никакой заход в комнату не последний, он побывает в комнате после -го дня. Но тогда он должен включить свет — противоречне.

(a) Текущее состояние описанной в задаче системы определяется количеством шариков в каждой коробочке и указанием коробочки, с которой нужно начинать раскладывать шарики в следующий раз. Поэтому возможных состояний системы конечное число. Из каждого состояния можно, раскладывая шарики, перейти в другое состояние системы, которое определено однозначно. Наоборот, зная состояние системы в настоящий момент, можно однозначно определить состояние системы перед последним раскладыванием шариков. Действительно, последнее раскладывание должно было закончиться на выделенной коробочке; поэтому, чтобы восстановить предыдущее состояние, нужно взять один шарик из выделенной коробочки и далее, идя против часовой стрелки, брать по шарику из каждой коробочки, пока это возможно. Когда же мы встретим пустую коробочку, мы положим в неё все собранные шарики и объявим её отмеченной. Если обозначить состояния системы точками, а возможность перехода из одного состояния в другое — стрелкой, соединяющей соответствующие точки (то есть построить граф состояний системы), то из каждой точки будет выходить ровно одна стрелка и в каждую точку будет входить ровно одна стрелка. Начнём двигаться по стрелкам, начиная с заданного состояния Получаем последовательность состояний Поскольку число состояний конечно, в некоторый момент в последовательности возникнет повторение. Пусть, например, где Поскольку в точку входит ровно одна стрелка, из равенства следует Тем самым, через ходов мы вернулись в состояние

(b) В отличие от первого пункта теперь состояние системы определяется лишь тем, как разложены шарики по коробочкам.

Заметим, что если ход ведет из состояния в состояние то, согласно первому пункту, мы можем (за несколько ходов) вернуться из в Если мы можем попасть из состояния в состояние за несколько ходов, то мы можем вернуться из в “откатывая” ходы по одному. Теперь понятно, что если мы научимся попадать из любого состояния в некоторое фиксированное состояние то сможем “путешествовать” между любыми состояниями, “проезжая” через

Обозначим через состояние, когда все шарики собраны в фиксированной коробочке Будем при каждой операции брать шарики из ближайшей (против часовой стрелки) к непустой коробочки. Тогда либо число шариков в увеличится, либо ближайшая к непустая коробочка станет еще ближе. Рано или поздно все шарики соберутся в

Обозначим через количество камней в клетке с номером Тогда последовательность задает конфигурацию — расположение камней по клеткам. Пусть — корень уравнения больший Назовем весом конфигурации число Покажем, что разрешенные действия не меняют веса. Действительно,

Докажем индукцией по — числу камней, что любая последовательность действий завершается. При это верно. Пусть при числе камней, меньшем утверждение верно. Рассмотрим процесс, начинающийся с конфигурации с Наибольший номер непустой клетки при разрешенных действиях не уменьшается, но и расти бесконечно он не может — он не может превысить числа при котором Значит, с какого-то момента наибольший номер непустой клетки перестает изменяться, и с камнями, попавшими в эту клетку, уже ничего не происходит. Выбросим эти камни, и применим предположение индукции к оставшимся.

В конечной конфигурации в каждой клетке не более одного камня, и нет двух непустых клеток подряд. Докажем, что любые две конфигурации и с такими свойствами имеют разные веса. Пусть — наибольший номер, при котором пусть, для определенности, Выбросим из и все камни с номерами, большими (они в и совпадают). Для оставшихся конфигураций и имеем:

Таким образом, для любой конфигурации есть только одна конечная с таким же весом; только к ней и может привести процесс.

У нас могла быть изначально фальшивой любая из 10 монет. Пусть мы справились за 2 действия. Каждым действием весы показывали один из трёх знаков: “”, “”, “”. Таким образом, всего получается комбинаций ответов. По результатам мы должны уметь однозначно определять, какая монета является фальшивой. Но этих результатов 9, а монет 10. Значит, гарантированно определить фальшивую монету за 2 взвешивания невозможно. Тем более это невозможно за одно действие.

Поскольку имеется девять вариантов, первым взвешиванием должны быть положены на весы 6 медалей — по три на каждую чашу. При этом на каждой чаше должно быть поровну как серебряных, так и бронзовых медалей. Единственный способ достичь этого — положить по одной серебряной и две бронзовых медали. Если в результате одна из чаш оказалась легче, то вторым взвешиванием достаточно сравнить между собой те бронзовые медали, которые на ней лежали. Если же весы оказались в равновесии, то вторым взвешиванием нужно найти фальшивую медаль (ФМ) среди трёх оставшихся подозрительными одной бронзовой, одной серебряной и одной золотой. Ясно, что золотую сравнивать не с чем, поэтому на весы её класть нельзя. А вот подозрительные бронзовую и серебряную медали нужно положить на разные чаши, при этом уравновесив настоящими (то есть уже определёнными как нефальшивые после первого взвешивания) медалями из того же материала. Иначе говоря, если после первого взвешивания остались подозрительными медали и , то вторым взвешиванием сравниваем с Если в результате наступило равновесие, то все эти медали настоящие, а фальшивой является если перевесила , то ФМ на другой чаше, то есть это наконец, если перевесила , то ФМ — .