– Первое условие исключает из числа возможных состояния АВ и АБВ. Второе исключает БГ и БВГ. Третье исключает АГ. Четвертое условие исключает ВГ. Пятое исключает переход А → *. Шестое исключает переход Б → *.

Я понял, что рассказ будет длинным.

– Далее, АБВГ → АВГ или АБГ. Однако АВГ → АВ, АГ или ВГ, а все эти комбинации исключены. Поэтому АБВГ → АБГ. Поскольку АБГ → АГ и АБГ → БГ исключены, мы должны принять АБГ → АБ. Но АБ → А бессмысленно, потому что А не в состоянии выйти наружу, если никого рядом нет. Так что АБ → Б. Однако Б после этого не может выйти, поэтому какая-то другая кошка должна будет войти. Но в варианте Б → АБ возвращаться придется А, которая только что вышла, а вариант Б → Г исключен, так что Б → БВ. Далее БВ → В → *.

– То же самое можно показать визуально, что в некоторых отношениях даже проще, – добавил он и набросал небольшую схему. – На этом рисунке показаны все 16 возможных комбинаций с кошками, а тонкие линии представляют возможные переходы между ними, когда кто-то из кошек выходит или входит. Черные точки исключены, два крестика исключают две линии перехода. Жирная линия – это единственный путь от АБВГ к * с использованием только разрешенных точек и линий и без возвратов.

Вскоре после этого я воссоединился со своими пушистыми друзьями.

– Сомс, как я смогу вас отблагодарить? – воскликнул я, радостно прижимая животных к своей груди.

Он взглянул на свой пиджак.

– Сможете, Ватсап, если станете почаще вычесывать своих кошек.

Блинные числа

1. Нет, не любую.

2. Некоторые стопки из четырех блинов требуют четырех переворачиваний; пример вы видите на рисунке. На рисунке вы можете найти еще две такие комбинации. Никакая стопка из четырех блинов не требует больше четырех переворачиваний.

А вот систематический способ доказать эти утверждения. На схеме показана требуемая конечная конфигурация 1234, где размеры блинов указаны сверху вниз. Мы будем двигаться от нее в обратном порядке. Во второй строке показаны конфигурации, которые можно получить из 1234 одним переворотом. Одновременно это те конфигурации, которые можно упорядочить (то есть из которых можно получить 1234) одним переворотом. (Один и тот же переворот, повторенный дважды, возвращает стопку к первоначальной конфигурации.) В третьей строке показаны все конфигурации, которые можно получить из конфигураций первой строки одним переворотом. Они же – конфигурации, которые можно упорядочить до 1234 двумя переворотами. Обратите внимание: ровно одну конфигурацию третьей строки можно получить из двух конфигураций второй строки; это 1324. Поэтому схема в этом месте выглядит слегка асимметрично.

Строки 1, 2, 3 содержат 21 из 24 возможных конфигураций стопки. Не хватает трех: 2413, 3142 и 4231. В строке 4 показано, как их можно получить из строки 3 при помощи еще одного переворота – или, рассматривая переворот в обратном порядке, как из них можно получить 1234 за четыре переворота. (Остальные связи, ведущие к строке 4, опущены, поскольку они сильно усложняют схему и не нужны нам.) На рисунке выше наглядно показаны перевороты конфигурации 2413, необходимые для ее упорядочивания.

3. Наибольший блин либо находится на самом верху, либо нет. Если нет, вставляем лопаточку под него и переворачиваем все, что выше. Теперь самый большой блин находится на самом верху. Вставляем лопаточку под самый низ стопки и всю ее переворачиваем.