[Архив!] Чистая математика, физика, химия и т.п.: задачки для тренировки мозгов, никак не связанные с торговлей - страница 476

Осталось доказать, что расстановка символов в закольцованной ленте 00111 - единственная. Ну например, ни при каких сдвигах и ни при каких поворотах нам не встречается последовательность - 01011

Прикольная задачка про расстановку единиц в матрице. Ну, надо с чего-то начать. Попытка подбора хотя бы одной такой матрицы приводит напимер к такому результату:

1 0 0 1 1

1 1 0 0 1

1 1 1 0 0

0 1 1 1 0

0 0 1 1 1

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

Честно говоря, мне кажется что лента имеет единственную последовательность следования символов, а именно: 00111, где первый ноль и последняя единица - это два соседних символа закольцованной ленты. Если это допущение верно (о единственности последовательности), то число комбинаций просчитать не трудно.

Понятно, что если сдвигается верхняя лента по горизонтали, то должны сдвинуться и все прочие горизонтальные ленты в том же направлении и на такое же число позиций. Итак мы имеем 5 вертикальных и 5 горизонтальных сдвигов всего поля карты. И при этом на каждый вертикальный сдвиг приходится 5 горизонтальных. Итого это 5*5. НО! Но при этом мы имеем возможность поле квадрата поворачивать. Подкрасим верхнюю строку синим цветом. Сколько положений квадрата будем иметь? Синяя сверху, синяя справа, синяя снизу, синяя слева. Итого 4 положения. Следовательно у нас 5*5*4 = 100 способов построить данную карту Карно.

Осталось доказать, что расстановка символов в закольцованной ленте 00111 - единственная. Ну например, ни при каких сдвигах и ни при каких поворотах нам не встречается последовательность - 01011

Вы получили один из вариантов заполнения матрицы. Теперь можно поменять местами любые столбцы и результат тоже будет удовлетворять условиям задачи. Также можно поменять местами любые строки. Таким образом имеем:

<Количество перестановок столбцов> * <количество перестановок строк>

drknn:

Осталось доказать, что расстановка символов в закольцованной ленте 00111 - единственная. Ну например, ни при каких сдвигах и ни при каких поворотах нам не встречается последовательность - 01011

Не докажете. Расстановок много больше. Например перестановка произвольных столцов или строк "правильной" матрицы создаёт правильную матрицу.

Пример навскидку:

зы: ))

PapaYozh опередил.