Конкурс для программистов - 3^n, димеры и статистика циклов

[Zealint]

Модераторам: форум dxdy указан на странице конкурса в качестве информационного спонсора.

Предлагаю принять участие в моём новом конкурсе для программистов-математиков. На этот раз никакого призового фонда не будет, зато задачи попроще и моего участия не предвидится.

Подробные условия задач на странице конкурса. Здесь лишь кратко обозначу постановку задач.

Задача 1. $3^n$.

Задано натуральное число $n$, требуется отыскать такое минимальное натуральное число $k$, что $3^k$ содержит не менее $n$ подряд идущих нулей. Например, для $n=1$ ответ $k=10$, а для $n=2$ ответ $k=35$.

В энциклопедии уже есть ответы для аналогичной задачи, но для $2^n$ (A006889), а для $3^n$ есть только поиск подряд идущих девяток (A131544), восьмёрок, семёрок, ..., а нулей нет! Торопитесь исправить это недоразумение.

Задача 2. Димеры на цилиндре.

Вспомним классическую задачу про "паркет" (изначально - это задача о димерах). Задана прямоугольная шахматная доска размером $n\times n$. Сколькими способами можно замостить доску костяшками домино размером $1\times 2$? Костяшки не могут выходить за края доски, накладываться друг на друга. Вся доска должна быть замощена. Например, для $m=n=2$ ответ 2, то есть всего два способа.

Теперь усложняем условие: сворачиваем доску в цилиндр, соединяя левую и правую границы. В этом случае, если костяшка "вылезает" за левую границу, то её половинка появляется справа, и наоборот. Сколько существует замощений квадратного шахматного цилиндра размером $2n\times 2n$? Если $n=1$ (цилиндр $2\times 2$), то ответ 5. Если $n=2$, то ответ 121.

Задача 3. Статистика циклов на решётке.

Задана решётка размером $n\times n$. В ней можно обнаружить простые циклы (без самопересечений) длиной 4, 6, 8, и т. д. Требуется для заданного натурального $n>1$ сказать, сколько на решётке $n\times n$ простых циклов всех возможных чётных длин (нечётных там нет). Например, для $n=1$ ответом будет один цикл длиной 4. Для $n=2$ имеем циклы длиной 4, 6 и 8 в количестве 4, 4 и 5 соответственно. Для $n=3$ ответом будет последовательность [9,12,26,52,76,32,6]. (9 циклов длиной 4, 12 циклов длиной 6, ..., 6 циклов длиной 16).

Удачи!

[Zealint]

Конкурс завершён. Можно ознакомиться с итогами.
Всем спасибо за явное и неявное участие.

[cepesh]

Тема перемещена из форума «Программирование» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.